ik denk dat de beste manier om de bubble sort bespreken is met een voorbeeld . Ik zal een overzicht van het algoritme te geven , en dan gaan we door middel van een voorbeeld stap-voor - stap om u een idee van hoe het werkt te geven werken . Dus eerst , het idee .

Bubble sort 2 wordt gebruikt om een ​​lijst van items sorteren in oplopende of aflopende volgorde . Laten we aannemen dat voor dit soort dat je de lijst wilt zetten in oplopende volgorde ( 1,2,3 , enz. ) . Het soort werkt door het passeren van elk element in de lijst en te vergelijken met het volgende element in de lijst . Als het eerste element is dan het tweede element , worden de twee geschakeld . Als het eerste element kleiner is dan of gelijk is aan de tweede , gebeurt er niets . Na het kijken naar dit element , wordt het volgende element keek , en het proces wordt herhaald .
3

Als de soort heeft gekeken naar elk element , heeft een 'voldoende ' afgerond . Na een keer , weet je zeker dat een nummer moet in de juiste positie . In onze oplopende volgorde , de grootste waarde zal ' bubble ' aan het einde van de lijst . Helaas , je weet niet of de rest van de lijst is gesorteerd , dus je moet nog een keer nemen . Echter , op deze pas , kunt u een element stoppen voordat het einde , omdat je weet dat nummer al in de juiste positie .

Bubble sort 4 ( meestal ) vereist een aantal passes te voltooien . De passen zij nodig is gelijk aan het aantal elementen in de lijst minus 1 . Dus als je 10 elementen in uw lijst , kan het 9 passen nemen om de soort te voltooien . Laten we gaan door middel van een voorbeeld om beter uit te leggen
5

Laten we gebruik maken van de volgende gesorteerde lijst : . 6 , 3 , 1 , 8 , 2 , 4

We willen de lijst om er als volgt uit : 1 , 2 , 3 , 4 , 6 , 8

op de eerste pas , zullen we de nummers een vergelijk in een tijd , en we weten dat na een keer moeten we het grootste aantal hebben helemaal naar rechts , dus in dit geval , dat zal worden 8 . Voor ons voorbeeld , zal het ^ teken wijzen op de plek in de lijst die we nu onderzoeken .
6

6 , 3 , 1 , 8 , 2 , 4

Pass
1 , Stap 1 ) Vergelijk de 6 en de 3 . 6 groter is dan 3 , dus we zullen ruilen them.3 , ^ 6 , 1 , 8 , 2 , 4

Pass
1 , stap 2 ) Vergelijk de 6 en de 1 . 6 groter is dan 1 , dus we zullen ruilen them.3 , 1 , ^ 6 , 8 , 2 , 4

Pass
1 , stap 3 ) Vergelijk de 6 en de 8 . 6 is kleiner dan of gelijk aan 8 , dus niets happens.3 , 1 , 6 , 8 ^ , 2 , 4

Pass
1 , Stap 4 ) Vergelijk de 8 en 2 . 8 groter is dan 2 , dus swap them.3 , 1 , 6 , 2 , ^ 8 , 4

Pass
1 , Stap 5 ) Vergelijk de 8 en de 4 . 8 is groter dan 4 , dus swap them.3 , 1 , 6 , 2 , 4 , 8

En je klaar bent de eerste pas !
7

3 , 1 , 6 , 2 , 4 , 8 is nauwelijks een gesorteerde lijst , maar je kunt zien , zoals beloofd , de 8 is op het einde . Ik ga nu schrijven wat de lijst eruit ziet na elke pass. Probeer het zelf , en kijk of de jouwe overeenkomt met de mijne : Pass 2 : 1 , 3 , 2 , 4 , 6 , 8 ( op zoek naar beter ) Pass 3 : 1 , 2 , 3 , 4 , 6 , 8 (gedaan ) Pass 4 : 1 , 2 , 3 , 4 , 6 , 8 ( umm ... waren we niet al gedaan ? ) Pass 5 : ( ! nog gedaan ) 1 , 2 , 3 , 4 , 6 , 8
8

Zoals je kunt zien , is de lijst gesorteerd na 3 passes , maar de bubble sort bleef gaan . Waarom is dat ? Nou , de basis- bubble sort -algoritme is behoorlijk dom . Het wil er zeker van dat het zal werken in het ergste geval ( dat is een lijst die is volledig achterwaarts zoals 9 , 8 , 7 , 6 , 5 ) . U kunt een snelheid toe te voegen aan uw bubble sort een beetje sneller lopen . Op elke pas, een vlag die wordt ingesteld op true alleen als je daadwerkelijk overschakelen twee nummers . Voordat je de volgende pas , controleren om te zien of de vlag waar of onwaar is . Als het waar is , je verwisseld twee nummers , en je moet nog een keer doen . Als het vals is, wordt de lijst gesorteerd , en je kan worden gedaan . In ons voorbeeld , ook al is de lijst gesorteerd was na 3 passes , zouden we moeten nog een 4e pas te maken, omdat we een swap in de 3e pass.
9

Nu je weet hoe je een doen bubble sort . Laat reacties met eventuele vragen die u heeft . Bedankt voor het lezen !