Komplexität BubbleSort / SelectionSort



  • Hallo zusammen,

    ich vergleiche gerade den BubbleSort mit dem SelectionSort. Der BestCase des BubbleSort lautet n. Der Worst Case lautet $$ \frac{n(n-1)}{2} $$. So wie ich Wikipedia verstehe ist der BestCase beim SelectionSort gleich dem WorstCase. Beide sind $$ \frac{n(n-1)}{2} $$. Warum? Ist der BestCase nicht auch einfach n? Wenn nicht, warum?

    Vielen Dank
    lg, freakC++



  • freakC++ schrieb:

    Warum? Ist der BestCase nicht auch einfach n? Wenn nicht, warum?

    Du mußt in jedem Schleifendurchlauf deine gesamte Restliste durchlaufen, um das Minimum zu bestimmen.
    (beim BubbleSort ist der BestCase eine bereits sortierte Liste - da läufst du einmal durch, stellst fest daß du keine Vertauschungen benötigt hast und bist fertig)



  • Das hört sich richtig an. Ich kann es dennoch nicht an meiner Implementierun nachvollziehen, die ich eben gemacht habe:

    void BubbleSort()
    {
    	for(int i = n-1; i > 0; i--)
    		for(int j = 0; j < i; j++)
    			if(arr[j] > arr[j+1])
    				std::swap(arr[j],arr[j+1]);
    }
    
    void SelectionSort()
    {
    	int min;
    	for(int i = 0; i < n; i++)
    	{
    		min = i;
    		for (int j = i+1; j < n; j++)
    			if(arr[j] < arr[min])
    				min = j;
    		std::swap(arr[i],arr[min]);
    	}
    }
    

    Selbst wenn das Array bereits sortiert wäre, würden beide Schleifen im BubbleSort durchlaufen. Es würde halt nichts vertauscht. Bedeutet dies, dass ich noch ein break reinmachen müsste, damit der BestCase wirklich n ist?

    Vielen Dank
    lg, freakC++



  • Klar, wenn man die üblichen Optimierungen außer acht lässt, wird es langsamer und du machst dir unnötig Arbeit 😉
    Hier eine kleine Verbesserung mit großer Wirkung:

    void BubbleSort()
    {
        bool vertauscht = false;
        for(int i = n-1; (i > 0) && vertauscht; i--)
        {
            vertauscht=false;
            for(int j = 0; j < i; j++)
                if(arr[j] > arr[j+1])
                {
                    vertauscht = true;
                    std::swap(arr[j],arr[j+1]);
                }
        }
    }
    


  • Ahhhh. Muchas gracias por la ayuda!!

    Das werde ich schleunigst bei mir ändern. Wenn Du jetzt "vertauscht" auf true setzt, dann funktioniert deine Version sogar :D. Ich weiß aber natürlich was Du meinst.

    lg, freakC++



  • freakC++ schrieb:

    Wenn Du jetzt "vertauscht" auf true setzt, dann funktioniert deine Version sogar :D.

    Er setzt es doch 😕



  • vertauscht muss am Anfang mit true initialisiert werden, sons gehts gar nicht erst in dir for -Schleife rein.


Log in to reply