[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