Bubble Sort Complexiteit

[Energyfellow]

Hey,

Bubble sort, het alom bekende algortime, daarvan zou ik graag eens berekenen willen hoeveel keer de als lus wordt aangeroepen (regel 4).

Ik heb getracht dit een som te plaatsen en dit is mijn resultaat:

\(\sum_{i=1}^{n-1}\sum_{i=1}^{n-1} = \sum_{i=1}^{n-1} (n-1)\)

.

Ik vermoed dat ik hier ergens te kort door de bocht ga maar ik weet niet precies waar.

Volgens Wolfram Alpha zou het dit moeten zijn: http://tinyurl.com/w...amalphauitkomst

Bubble sort 935 keer bekeken

Iemand die me kan helpen?

Dank bij voorbaat,

Roger

[EvilBro]

Waarom zijn de grenzen bij het tweede somteken niet afhankelijk van i? (dat zijn ze in de pseudocode immers wel.)

[Energyfellow]

Maakt dat iets uit of ik nu de lus uitvoer door iedere keer mijn j min 1 te doen of gewoon van i + 1 naar j gaan? Komt dat niet op hetzelfde neer?

[Math-E-Mad-X]

Je pseudocode is niet duidelijk omdat je nergens aangeeft hoe i en j veranderen. Ik neem aan dat je in de buitenste lus telkens i met 1 verhoogt, terwijl je in de binnenste lus telkens j met 1 verlaagt?

[Xenion]

Je pseudocode is niet duidelijk omdat je nergens aangeeft hoe i en j veranderen. Ik neem aan dat je in de buitenste lus telkens i met 1 verhoogt, terwijl je in de binnenste lus telkens j met 1 verlaagt?

Dat is toch duidelijk?

Opmerking moderator

Verplaatst naar programmeren.

[Energyfellow]

Inderdaad, maar om op EvilBro zijn vraag verder te gaan, ik weet niet of het mogelijk is om bij een sommatie j--; te doen, vandaar dat ik ze heb omgewisseld, naar mijn mening zal dit geen verschil uitmaken, of sla ik hier de bal mis?

[Xenion]

Die

\(\sum_{i=1}^{n-1}\sum_{i=1}^{n-1}\)

klopt niet, maar je kan het veel intuïtiever afleiden.

Algemeen loopt de binnenste loop van i+1 tot n, dus n-i herhalingen zoals je zelf al doorhad. Die doe je voor i = 1 tot n.

Zet dat in een som en reken uit:

\(\sum_{i=1}^n (n-i) = \sum_{i=1}^n n - \sum_{i=1}^n i = ...\)

[Energyfellow]

Ik heb het eventjes volledig uitgewerkt:

\(n^{2} - \frac{n*(n + 1)}{2} = \frac{2n^{2} - (n^{2} -n))}{2} = \frac{n^{2} - n}{2} = \frac{n*(n-1)}{2}\)

.

Ik snap niet goed waarom je gaat tot n en niet (n - 1). In de pseudo-code staat toch beschreven dat je moet gaan tot (n-1)?

[EvilBro]

Pseudocode naar som (volgens mij gewoon een kwestie van de grenzen lezen in de code):

\(\sum_{i = 1}^{n-1} \left(\sum_{j = i+1}^{n} 1 \right)\)

Zoals je ziet is hier de tweede som afhankelijk van i. Dit was bij jou niet het geval (en dat is hetgeen ik aanstipte, maar jij had dat kennelijk niet helemaal goed begrepen).

Een andere manier om het te benaderen: Stel dat je een rij gaat sorteren die precies verkeerd om begint. Je begint dan bij het achterste element (= het kleinste element). Dit element wordt dan dus met alle andere elementen vergeleken om zo uiteindelijk op de eerste plek uit te komen. Dit zijn (n-1) vergelijkingen. Vervolgens wordt het nieuwe achterste element (het op een na kleinste element) met alle andere elementen vergeleken (behalve de eerste) om uiteindelijk op de tweede positie te komen. Ga zo door met alle andere elementen. Hopelijk is het niet lastig om in te zien dat zo alle elementen precies 1x met elkaar vergeleken worden.

Hoeveel vergelijkingen zijn er met n elementen? Elk element wordt met (n-1) andere elementen vergeleken, dus:

\(n \cdot (n-1)\)

Maar nu maak je geen onderscheid tussen de vergelijking (1 met 2) en (2 met 1). Je telt alle paren dus dubbel. Dit leidt tot:

\(\frac{n \cdot (n-1)}{2}\)

[Energyfellow]

Ik verstond zoals je zegt niet goed hoe je die afhankelijkheid in een som moest zetten.

Ter volledigheid:

\(\left(\sum_{j = i+1}^{n} 1 \right) =\)

[/size]

\(= \sum_{j=m}^{n}1\)

waarbij

\(m = i+1\)

, dat zal ons opleveren:

\( = n + 1 - m\)

\(= n + 1 -(i + 1)\)

\(= n - i\)

Dan krijgen we:

\(\sum_{i=1}^n (n-i)\)

[/color][/size]

\((n-1)^{2} - \frac{(n-1)*((n-1) + 1)}{2} \)

\(= \frac{2(n-1)^{2} - (n*(n-1))}{2}\)

\(= \frac{2*(n^{2}-n+1)-n^{2}-n}{2}\)

\(= \frac{n^{2}-3*(n+1)}{2}\)

[/color][/size]

\(= \frac{n^{2}-3*n+2}{2}\)

Dit is echter heel iets anders als ik n neem in plaats van (n-1).[/color][/size]

[Xenion]

Ik snap niet goed waarom je gaat tot n en niet (n - 1). In de pseudo-code staat toch beschreven dat je moet gaan tot (n-1)?

Dat heb ik dan even fout gelezen

[Energyfellow]

Maar het rare is dat jouw antwoord het correcte is ... namelijk:

\(\frac{n \cdot (n-1)}{2}\)

.

[Xenion]

Dan zullen we eens naar de berekening kijken he. Met de juiste grenzen wordt het:

\(\sum_{i=1}^{n-1} (n-i) = \sum_{i=1}^{n-1} n - \sum_{i=1}^{n-1} i\)

De eerste som valt weer makkelijk uit te rekenen, voor de volgende pas ik een trucje toe. Ik laat de som gaan tot n en trek compenseer dan buiten de som die extra term:

\(= (n-1) n - \sum_{i=1}^{n} i + n\)

\(= n^2- n - \frac{1}{2}n(n+1) + n\)

\(= n^2- \frac{1}{2}n(n+1)\)

\(= n^2- \frac{1}{2}n(n+1)\)

\(= \frac{1}{2}n(n-1)\)

Merk op dat dit ook gewoon logisch is, waaraan is de term voor i=n gelijk?

[EvilBro]

Nog een keertje proberen:

\(\sum_{i=1}^n (n-i) = \sum_{i=1}^n n - \sum_{i=1}^n i = \cdots\)

[/color][/size]

Edit: ah, ik zie dat die suggestie al gedaan is...

[Energyfellow]

@Xenion, ik snap je manier van redeneren en is uiteindelijk ook logisch (een trucje om zeker te onthouden ).

@EvilBro:

\(\sum_{i=1}^{n-1} (n-i)\)

\(n \cdot (n-1) - \frac{(n-1)\cdot((n-1) + 1)}{2}\)

\(= \frac{(2 \cdot n^2 -2\cdot n + 2) - n \cdot (n-1)}{2}\)

\(= \frac{(2\cdot n^2 - 2 \cdot n - n^2 + n)}{2}\)

\(= \frac{n^2 - n}{2}\)

\(= \frac{n \cdot (n - 1)}{2}\)

Bedankt voor alles EvilBro en Xenion .