[Powered by Google Translate] [Bubble sort]
[JACKSON Steinkamp HARVARD UNIVERSITY]
[DIT IS CS50. CS50TV]
Bubble Sort is een voorbeeld van een sorteer-algoritme -
dat is, een procedure voor het sorteren van een reeks elementen in
oplopende of aflopende volgorde.
Bijvoorbeeld, als je wilde een array sorteren bestaande uit de getallen
[3, 5, 2, 9], zou een correcte implementatie van Bubble Sort terugkeer van de
gesorteerde array [2, 3, 5, 9] in oplopende volgorde.
Nu, ik ga uitleggen in pseudocode hoe het algoritme werkt.
>> Laten we zeggen dat we een lijst van 5 integers sorteren - 3, 2, 9, 6 en 5.
Het algoritme begint met te kijken naar de eerste twee elementen, 3 en 2,
en controleren of ze uit de orde ten opzichte van elkaar.
Ze zijn - 3 groter is dan 2.
Om in oplopende volgorde, moeten zij omgekeerd.
Dus, we ruilen.
Nu is de lijst ziet er als volgt uit: [2, 3, 9, 6, 5].
>> Vervolgens kijken we naar de tweede en derde elementen, 3 en 9.
Ze zijn in de juiste volgorde ten opzichte van elkaar.
Dat wil zeggen, 3 minder dan 9, zodat het algoritme niet verwisselen.
Vervolgens kijken we naar 9 en 6. Ze zijn niet in orde.
>> Dus, we moeten ze ruilen, want 9 is groter dan 6.
Tot slot kijken we naar de laatste twee gehele getallen, 9 en 5.
Ze zijn niet in orde, dus ze moeten worden verwisseld.
Na de eerste volledige passage door de lijst,
ziet het er zo uit: [2, 3, 6, 5, 9].
Niet slecht. Het is bijna gesorteerd.
Maar we moeten weer te lopen door de lijst om het te krijgen volledig gesorteerd.
Twee minder dan 3, zodat we niet ruilen.
>> Drie is minder dan 6, zodat we niet ruilen.
Zes groter is dan 5. We verwisseld.
Zes minder dan 9. We hebben geen ruilen.
Na de tweede passeren, ziet het er als volgt uit: [2, 3, 5, 6, 9]. Perfect.
Laten we nu eens schrijf het in pseudocode.
Kortom, voor elk element in de lijst, moeten we kijken
en het element direct aan de rechterkant.
Als ze in orde ten opzichte van elkaar - dat wil zeggen als het element aan de linkerkant
groter is dan de een aan de rechterkant - we moeten wisselen de twee elementen.
>> We doen dit voor elk element van de lijst, en we hebben een doorgang door.
Nu hoeven we alleen maar de pass-through vaak genoeg doen om de lijst te garanderen
volledig, goed gesorteerd.
Maar hoe vaak moeten we nog door de lijst door te geven aan
garanderen dat we klaar zijn?
Nou, de worst-case scenario is als we een volledig backwards lijst.
Dan neemt een aantal sluizen gelijk aan het aantal
elementen n-1.
Als dit niet intuïtief zin, denken aan een eenvoudig geval - de lijst [2, 1].
>> Dit gaat een pass-through te nemen om volledig te kunnen sorteren.
[3, 2, 1] - In het slechtste geval is dat met 3 elementen achteren gesorteerd,
het gaat om 2 iteraties te nemen om te sorteren.
Na een iteratie is [2, 1, 3].
De tweede levert de gesorteerde array [1, 2, 3].
Dus je weet dat je nooit meer hoeft te gaan door middel van de array, in het algemeen,
dan n-1 keer, waarbij n het aantal elementen in de array.
Het heet Bubble Sort omdat de grootste elementen hebben de neiging om 'bubble-up'
aan de rechterkant vrij snel.
In feite is dit algoritme interessant gedrag.
>> Na m iteraties door de hele array,
de rechter m elementen zijn gegarandeerd
worden gesorteerd op hun juiste plaats.
Als je dit wilt zien voor jezelf,
we kunnen proberen een volledig achterwaarts lijst [9, 6, 5, 3, 2].
Na een doorgang door de hele lijst,
[Geluid van schrijven]
[6, 9, 5, 3, 2] [6, 5, 9, 3, 2] [6, 5, 3, 9, 2] [6, 5, 3, 2, 9]
de meest rechtse element 9 is op de juiste plaats.
Na de tweede pass-through, zal de 6 hebben 'borrelde-up' aan de
seconden meest rechtse plaats.
De twee elementen rechts - 6 en 9 - worden in de juiste plaatsen
na de eerste twee sluizen.
>> Dus, hoe kunnen we dit gebruiken om het algoritme te optimaliseren?
Nou, na een iteratie door de array
we eigenlijk niet nodig om de meest rechtse element controleren
omdat we weten dat het gesorteerd.
Na twee iteraties, weten we zeker de meest rechtse twee elementen op hun plaats zitten.
Dus in het algemeen na k iteraties door de volledige array,
het controleren van de laatste k elementen is overbodig omdat we weten
ze in de juiste locatie reeds.
>> Dus als je het sorteren van een array van n elementen,
de eerste iteratie - u zult moeten alle elementen sorteren - de eerste n-0.
Op de tweede iteratie, zul je moeten kijken naar alle elementen, maar de laatste -
de eerste n-1.
Een andere optimalisatie zou kunnen zijn om te controleren of de lijst is al gesorteerd
na elke iteratie.
Als het al gesorteerd, hebben we geen behoefte aan een meer iteraties te maken
door de lijst.
Hoe kunnen we dit doen?
Nou, als we geen swaps te maken op een doorwerking van de lijst,
het is duidelijk dat de lijst al was gesorteerd, omdat we niet ruilen niets.
Dus we zeker niet nog een keer te sorteren.
>> Misschien kunt u initialiseren een vlag variabele genaamd 'niet gesorteerd' te
Valse en verander het naar waar als je moet alle elementen op ruilen
een iteratie door de array.
Of een andere soortgelijke, maak een teller om te tellen hoeveel swaps u
op een bepaalde iteratie.
Aan het einde van een iteratie, als je niet ruilen voor een van de elementen,
je weet de lijst is al gesorteerd en je bent klaar.
Bubble Sort, net als andere sortering algoritmen, kan
getweaked om te werken voor alle elementen die een bestelling methode.
>> Dat wil zeggen, gegeven twee elementen heb je een manier om te zeggen als de eerste
groter dan, gelijk aan of kleiner dan de tweede.
Bijvoorbeeld, kon u sorteren letters van het alfabet door te zeggen
dat a <b, b <c, etc.
Of je zou kunnen sorteren dagen van de week, waar zondag is minder dan maandag
die kleiner is dan dinsdag.
>> Bubble Sort is geenszins een zeer efficiënt of snel sorteren algoritme.
Het worst-case runtime is Big O van n ²
want je moet n iteraties te maken door middel van een lijst
controleren van alle n elementen elk pass-through, nxn = n ².
Deze looptijd betekent dat als het aantal elementen dat je stijgt het sorteren,
de looptijd neemt kwadratisch.
>> Maar als efficiëntie is niet een grote zorg van uw programma
of als je alleen het sorteren van een klein aantal elementen,
je zou kunnen vinden Bubble Sort nuttig omdat
het is een van de eenvoudigste sorteren algoritmen te begrijpen
en coderen.
Het is ook een geweldige manier om ervaring op te doen met het vertalen van een theoretische
algoritme in feitelijk functioneren code.
Nou, dat is Bubble Sort voor jou. Bedankt voor het kijken.
CS50.TV