Sorteer een array is het proces waarbij alle elementen in een bepaalde volgorde worden verdeeld. Heel vaak is dit nuttig. Uw inbox geeft bijvoorbeeld e-mails weer op basis van het tijdstip waarop ze zijn ontvangen; nieuwe e-mails worden als relevanter beschouwd dan de e-mails die u een half uur, een uur, twee of een dag geleden heeft ontvangen; Wanneer u naar uw contactenlijst gaat, staan ​​de namen meestal in alfabetische volgorde, omdat u dan gemakkelijker iets kunt vinden. In al deze gevallen moet de gegevens worden gesorteerd voordat deze daadwerkelijk worden uitgevoerd.

Hoe werkt sorteren?

Het sorteren van gegevens kan het zoeken binnen een array efficiënter maken, niet alleen voor mensen, maar ook voor computers. Neem bijvoorbeeld een geval waarin we moeten uitzoeken of een bepaalde naam voorkomt in een lijst met namen. Om dit te weten te komen, moeten we elk element van de array vergelijken met onze waarde. Het doorzoeken van een array met veel elementen kan te inefficiënt (duur) zijn.

Laten we echter aannemen dat onze reeks namen alfabetisch is gesorteerd. Dan begint onze zoektocht met de eerste letter van onze waarde en eindigt met de volgende letter in het alfabet. Als we in dit geval bij deze letter zijn aangekomen en de naam niet hebben gevonden, weten we zeker dat deze niet in de rest van de array staat, omdat we onze brief al in alfabetische volgorde hebben doorgegeven!

Het is geen geheim dat er betere algoritmen zijn voor het zoeken in gesorteerde arrays. Met behulp van een eenvoudig algoritme kunnen we zoeken naar een specifiek element in een gesorteerde array met 1.000.000 elementen met behulp van slechts 20 vergelijkingen! Het nadeel is natuurlijk dat het sorteren van een array met zo'n groot aantal elementen relatief duur is, en dat dit zeker niet wordt gedaan omwille van een enkele zoekopdracht.

In sommige gevallen maakt het sorteren van een array het zoeken overbodig. We zijn bijvoorbeeld op zoek naar de beste score van een leerling op een toets. Als de array niet is gesorteerd, moeten we elk element van de array doorzoeken om de hoogste score te vinden. Als de array is gesorteerd, staat de hoogste score op de eerste of op de laatste positie (afhankelijk van hoe de array is gesorteerd: oplopend of aflopend), dus we hoeven helemaal niet te zoeken!

Sorteren gebeurt doorgaans door paren array-elementen herhaaldelijk te vergelijken en de waarden te vervangen als ze aan bepaalde criteria voldoen. De volgorde waarin deze elementen worden vergeleken, hangt af van welk sorteeralgoritme wordt gebruikt. De criteria bestaan ​​uit hoe de array wordt gesorteerd (bijvoorbeeld oplopende of aflopende volgorde).

Om twee elementen te verwisselen kunnen we de functie gebruiken std::wissel() uit de C++-standaardbibliotheek, die is gedefinieerd in het algoritme. In C++11 is std::swap() verplaatst naar het headerbestand van het hulpprogramma:

#erbij betrekken #erbij betrekken int main() ( int a = 3; int b = 5; std::cout<< "Before swap: a = " << a << ", b = " << b << "\n"; std::swap(a, b); // меняем местами значения переменных a и b std::cout << "After swap: a = " << a << ", b = " << b << "\n"; }

#erbij betrekken #erbij betrekken // voor std::swap. Gebruik in C++11 header int hoofd() int a = 3; int b = 5; std::uit<< "Before swap: a = " << a << ", b = " << b << "\n" ; std::wissel(a, b); // verwissel de waarden van variabelen a en b std::uit<< "After swap: a = " << a << ", b = " << b << "\n" ;

Het resultaat van het uitvoeren van het bovenstaande programma:

Vóór de ruil: a = 3, b = 5
Na ruil: a = 5, b = 3

Na het uitvoeren van de vervangingsbewerking worden de waarden van de variabelen a en b verwisseld.

Arrays sorteren met behulp van de selectiemethode

Er zijn veel manieren om arrays te sorteren. Array-sortering op selectie is misschien het gemakkelijkst te begrijpen, maar ook een van de langzaamste.

Voor een array sorteren door van het kleinste naar het grootste element te selecteren de volgende stappen worden uitgevoerd:

Beginnend met het element op index 0, zoeken we naar de kleinste waarde in de array.

De gevonden waarde wordt verwisseld met het nulelement.

We herhalen stap nr. 1 en nr. 2 voor de volgende index in de array.

Met andere woorden: we zoeken naar het kleinste element in de array en verplaatsen dit naar de eerste plaats. Vervolgens zoeken we naar het op een na kleinste element en verplaatsen dit naar de tweede plaats na het eerste kleinste element. Dit proces gaat door totdat de array geen ongesorteerde elementen meer heeft.

Hier is een voorbeeld van hoe dit algoritme werkt in een array met 5 elementen:

{ 30, 50, 20, 10, 40 }

Eerst zoeken we naar het kleinste element, beginnend bij index 0:

{ 30, 50, 20, 10 , 40 }

Vervolgens verwisselen we het kleinste element met het element op index 0:

{ 10 , 50, 20, 30 , 40 }

Nu het eerste element van de array is gesorteerd, negeren we het. We zoeken naar het op één na kleinste element, maar beginnend bij index 1:

{ 10 , 50, 20 , 30, 40 }

En verwissel het met het element op index 1:

{ 10 , 20 , 50 , 30, 40 }

Nu kunnen we de eerste twee elementen negeren. We zoeken naar het op één na kleinste element, beginnend bij index 2:

{ 10 , 20 , 50, 30 , 40 }

En verwissel het met het element op index 2:

{ 10 , 20 , 30 , 50 , 40 }

We zoeken naar het op één na kleinste element, beginnend bij index 3:

{ 10 , 20 , 30 , 50, 40 }

En verwissel het met het element op index 3:

{ 10 , 20 , 30 , 40 , 50 }

We zoeken naar het op één na kleinste element, beginnend bij index 4:

{ 10 , 20 , 30 , 40 , 50 }

En we ruilen het met het element op index 4 (er wordt zelfvervanging uitgevoerd, d.w.z. we doen niets):

{ 10 , 20 , 30 , 40 50 }

{ 10, 20, 30, 40, 50 }

Houd er rekening mee dat de laatste vergelijking altijd een enkele vergelijking zal zijn (d.w.z. een zelfvervanging), wat een onnodige bewerking is, zodat we het sorteren daadwerkelijk kunnen stoppen vóór het laatste element van de array.

Arrays sorteren met behulp van de selectiemethode in C++

Hier ziet u hoe dit algoritme wordt geïmplementeerd in C++:

#erbij betrekken #erbij betrekken // voor std::swap. Gebruik in C++11 header int main() ( const int lengte = 5; int array = ( 30, 50, 20, 10, 40 ); // Loop door elk element van de array // (behalve de laatste, deze zal al gesorteerd zijn op de De tijd dat we er zijn, laten we erheen gaan) for (int startIndex = 0; startIndex< length - 1; ++startIndex) { // В переменной smallestIndex хранится индекс наименьшего значения, которое мы нашли в этой итерации // Начинаем с того, что наименьший элемент в этой итерации - это первый элемент (индекс 0) int smallestIndex = startIndex; // Затем ищем элемент поменьше в остальной части массива for (int currentIndex = startIndex + 1; currentIndex < length; ++currentIndex) { // Если мы нашли элемент, который меньше нашего наименьшего элемента, if (array < array) // то запоминаем его smallestIndex = currentIndex; } // smallestIndex теперь наименьший элемент // Меняем местами наше начальное наименьшее число с тем, которое мы обнаружили std::swap(array, array); } // Теперь, когда весь массив отсортирован - выводим его на экран for (int index = 0; index < length; ++index) std::cout << array << " "; return 0; }

#erbij betrekken #erbij betrekken // voor std::swap. Gebruik in C++11 header int hoofd() const int lengte = 5; // Loop door elk element van de array // (behalve de laatste, deze zal al gesorteerd zijn tegen de tijd dat we er zijn) < length - 1 ; ++ startIndex ) // De kleinsteIndex-variabele slaat de index op van de kleinste waarde die we in deze iteratie hebben gevonden // Begin met het kleinste element in deze iteratie, zijnde het eerste element (index 0) int kleinsteIndex = startIndex ; // Zoek vervolgens naar een kleiner element in de rest van de array < length ; ++ currentIndex ) // Als we een element vinden dat kleiner is dan ons kleinste element, if (array [huidigeIndex]< array [ smallestIndex ] ) // onthoud het dan kleinsteIndex = huidigeIndex; // kleinsteIndex is nu het kleinste element // Verwissel ons aanvankelijke kleinste getal met het getal dat we hebben gevonden std::swap(array[startIndex], array[kleinsteIndex]); // Nu de hele array is gesorteerd, geeft u deze op het scherm weer voor (int index = 0; index< length ; ++ index ) std::uit<< array [ index ] << " " ; retour 0;

Het meest verwarrende deel van dit algoritme bevindt zich in een andere lus (een geneste lus genoemd). De buitenste lus (startIndex) doorloopt de elementen één voor één (één voor één). In elke iteratie van de buitenste lus wordt de binnenste lus (currentIndex) gebruikt om het kleinste element te vinden onder de elementen die in de array achterblijven (beginnend bij startIndex + 1). kleinsteIndex houdt de index bij van het kleinste element dat door de binnenste lus wordt gevonden. Vervolgens verandert kleinsteIndex de waarde van startIndex . Ten slotte passeert de buitenste lus (startIndex) dit element en herhaalt het proces zich.

Aanwijzing: Als je problemen hebt met het begrijpen hoe het bovenstaande programma werkt, probeer het dan op een vel papier te schrijven. Schrijf de eerste (ongesorteerde) elementen van de array horizontaal op een lijn bovenaan het werkblad. Teken pijlen die aangeven welke elementen op dit moment startIndex , currentIndex en kleinsteIndex zijn. Loop handmatig door het programma en teken de pijlen opnieuw als de indices veranderen. Teken na elke iteratie van de buitenste lus een nieuwe lijn die de huidige status van de array aangeeft (de locatie van de elementen).

Het sorteren van tekst wordt uitgevoerd met hetzelfde algoritme. Wijzig gewoon het arraytype van -a in en initialiseer het met de juiste waarden.

std::sort()

Omdat de werking van sorteerarrays heel gebruikelijk is, biedt de standaardbibliotheek van C++ een ingebouwde sorteerfunctie − std::sort(). Het bevindt zich in het headerbestand van het algoritme en wordt als volgt aangeroepen:

#erbij betrekken #erbij betrekken // for std::sort int main() ( const int lengte = 5; int array = ( 30, 50, 20, 10, 40); std::sort(array, array+lengte); for (int i= 0;< length; ++i) std::cout << array[i] << " "; return 0; }

#erbij betrekken #erbij betrekken // voor std::sort int hoofd() const int lengte = 5; int array [lengte] = (30, 50, 20, 10, 40); std::sort(array, array + lengte) ; voor (int ik = 0; ik< length ; ++ i ) std::uit<< array [ i ] << " " ; retour 0;

Test

Taak nr. 1

Schrijf op een vel papier hoe je de volgende array kunt sorteren met behulp van de selectiemethode (zoals we hierboven hebben gedaan):

{30, 60, 20, 50, 40, 10}

Antwoord #1

30 60 20 50 40 10
10 60 20 50 40 30
10 20 60 50 40 30
10 20 30 50 40 60
10 20 30 40 50 60
10 20 30 40 50 60 (zelfvervanging)
10 20 30 40 50 60 (zelfvervanging)

Taak nr. 2

Herschrijf de programmacode vanaf de ondertitel “Arrays sorteren op selectie in C++” zodat het sorteren in aflopende volgorde gebeurt (van het grootste naar het kleinste getal). Hoewel dit op het eerste gezicht misschien ingewikkeld lijkt, is het eigenlijk heel eenvoudig.

Antwoord #2

Verander gewoon:

Als (matrix< array)

if (array [huidigeIndex]< array [ smallestIndex ] )

Als (matrix > matrix)

if (array [huidigeIndex] > array [kleinsteIndex] )

Ook kleinsteIndex moet worden hernoemd naar grootsteIndex:

#erbij betrekken #erbij betrekken // voor std::swap. Gebruik in C++11 header int main() ( const int lengte= 5; int array = ( 30, 50, 20, 10, 40 ); // Loop door elk array-element behalve het laatste voor (int startIndex = 0; startIndex< length - 1; ++startIndex) { // largestIndex - это индекс наибольшего элемента, который мы обнаружили до сих пор int largestIndex = startIndex; // Перебираем каждый элемент массива начиная со startIndex + 1 for (int currentIndex = startIndex + 1; currentIndex < length; ++currentIndex) { // Если текущий элемент больше нашего наибольшего элемента, if (array >array) // dan is dit het nieuwe grootste element in deze iteratie grootsteIndex = currentIndex;< length; ++index) std::cout << array << " "; return 0; }

#erbij betrekken #erbij betrekken // voor std::swap. Gebruik in C++11 header int hoofd() const int lengte = 5; int array [lengte] = (30, 50, 20, 10, 40); ) // Verwissel ons startnummer met het grootste gevonden element std::swap(array, array); ) voor (int index = 0; index< length - 1 ; ++ startIndex ) // Loop door elk element van de array behalve het laatste for (int startIndex = 0; startIndex // grootsteIndex is de index van het grootste element dat we tot nu toe hebben gevonden for (int currentIndex = startIndex + 1; currentIndex< length ; ++ currentIndex ) // Als het huidige element groter is dan ons grootste element, if (array [huidigeIndex] > array [grootsteIndex] ) // dan is dit het nieuwe grootste element in deze iteratie grootsteIndex = huidigeIndex; // Verwissel ons startnummer met het grootste gevonden element std::swap (array [startIndex], array [grootsteIndex]); // Geef de gesorteerde array op het scherm weer voor (int index = 0; index< length ; ++ index ) std::uit<< array [ index ] << " " ; retour 0;

Taak nr. 3

Deze taak is iets moeilijker.

Een andere eenvoudige methode voor het sorteren van elementen is "bellen sorteren"(of anders "bellen sorteren"). Het idee is om een ​​paar waarden in de buurt te vergelijken, en als aan de opgegeven criteria wordt voldaan, worden de waarden van dit paar verwisseld. En zo ‘borrelen’ de elementen naar het einde van de array. Hoewel er verschillende manieren zijn om het sorteren van bellen te optimaliseren, blijven we voor deze opdracht bij de niet-geoptimaliseerde versie, omdat deze eenvoudiger is.

Voor een niet-geoptimaliseerde versie van bellensortering worden de volgende stappen uitgevoerd: sorteer een array van de kleinste naar de grootste waarde:

Het array-element op index 0 wordt vergeleken met het array-element op index 1. Als het element op index 0 groter is dan het element op index 1, dan worden de waarden verwisseld.

We gaan dan naar het volgende paar waarden: het element op index 1 en het element op index 2, enzovoort totdat we het einde van de array bereiken.

We herhalen stap nr. 1 en stap nr. 2 totdat de hele array is gesorteerd.

Schrijf een programma dat de volgende array sorteert met behulp van bellensortering volgens de bovenstaande regels:

const int lengte(9); int array = ( 7, 5, 6, 4, 9, 8, 2, 1, 3 );

const int lengte(9);

Aan het einde van het programma drukt u de gesorteerde elementen van de array af.

Aanwijzing: Als we slechts één element in één iteratie kunnen sorteren, betekent dit dat we de lus net zo vaak moeten herhalen als er getallen in onze array staan ​​(de lengte ervan) om ervoor te zorgen dat de hele array wordt gesorteerd.

Antwoord #3

#erbij betrekken #erbij betrekken // voor std::swap. Gebruik in C++11 header int main() ( const int lengte(9); int array = ( 7, 5, 6, 4, 9, 8, 2, 1, 3 ); for (int iteratie = 0; iteratie< length-1; ++iteration) { // Перебираем каждый элемент массива до последнего элемента (не включительно) // Последний элемент не имеет пары для сравнения for (int currentIndex = 0; currentIndex < length - 1; ++currentIndex) { // Если текущий элемент больше элемента после него, то меняем их местами if (array >array) std::swap(array, array);< length; ++index) std::cout << array << " "; return 0; }

#erbij betrekken #erbij betrekken // voor std::swap. Gebruik in C++11 header int hoofd() const int lengte(9); ) ) // Geef de gesorteerde array op het scherm weer voor (int index = 0; index int array [lengte] = (7, 5, 6, 4, 9, 8, 2, 1, 3);< length - 1 ; ++ iteration ) voor (int iteratie = 0; iteratie // Loop door elk array-element tot aan het laatste element (niet inclusief) // Laatste element heeft geen paar om te vergelijken< length - 1 ; ++ huidigeIndex) { // Als het huidige element groter is dan het element erna, verwissel ze dan als(reeks[ huidigeIndex] > reeks[ huidigeIndex+ 1 ] ) standaard:: ruil(reeks[ huidigeIndex] , reeks[ huidigeIndex+ 1 ] ) ; } } // Geef de gesorteerde array op het scherm weer voor(intindex= 0 ; index< lengte; ++ index) standaard:: uit<< reeks[ index] << " " ; opbrengst0 ; }

Taak nr. 4

Implementeer de volgende twee optimalisatieoplossingen voor het bellensorteeralgoritme dat je in de vorige opdracht hebt geschreven:

Merk op dat elke keer dat het sorteren van bellen wordt uitgevoerd, de grootste waarde in de array naar het einde “bubbelt”. Na de eerste iteratie is het laatste element van de array al gesorteerd. Na de tweede iteratie wordt het voorlaatste element van de array gesorteerd, enzovoort. Bij elke nieuwe iteratie hoeven we elementen die al zijn gesorteerd niet opnieuw te controleren. Pas uw lus aan zodat u elementen die al zijn gesorteerd niet opnieuw controleert.

Er wordt geschat dat tot een kwart van de tijd van gecentraliseerde computers wordt besteed aan het sorteren van gegevens. Dit komt omdat het veel gemakkelijker is om een ​​waarde te vinden in een array die vooraf is gesorteerd. Anders lijkt het zoeken een beetje op het zoeken naar een speld in een hooiberg.

Er zijn programmeurs die al hun werktijd besteden aan het bestuderen en implementeren van sorteeralgoritmen. Dit komt omdat de overgrote meerderheid van bedrijfssoftware databasebeheer omvat. Mensen zoeken voortdurend naar informatie in databases. Dit betekent dat er veel vraag is naar zoekalgoritmen.

Maar er is één ‘maar’. Zoekalgoritmen werken veel sneller met databases die al gesorteerd zijn. In dit geval is alleen lineair zoeken vereist.

Hoewel de computers op sommige momenten geen gebruikers hebben, blijven de sorteeralgoritmen op de databases werken. Er komen weer zoekers en de database is al gesorteerd op basis van een of ander zoekdoel.

Dit artikel geeft voorbeelden van implementaties van standaard sorteeralgoritmen.

Selectie sorteren

Om een ​​array in oplopende volgorde te sorteren, moet je bij elke iteratie het element met de grootste waarde vinden. Hiermee moet je het laatste element verwisselen. Het volgende element met de hoogste waarde wordt op de voorlaatste plaats geplaatst. Dit zou moeten gebeuren totdat de elementen op de eerste plaatsen in de array in de juiste volgorde staan.

C++-code

void SortAlgo::selectionSort(int data, int lenD) ( int j = 0; int tmp = 0; for (int i=0; i gegevens[k])( j = k; ) ) tmp = gegevens[i];

gegevens[i] = gegevens[j];

Bij het sorteren van bellen worden aangrenzende elementen vergeleken en van plaats gewisseld als het volgende element kleiner is dan het vorige. Er zijn meerdere passages door de gegevens vereist. Tijdens de eerste doorgang worden de eerste twee elementen in de array vergeleken. Als ze niet in orde zijn, worden ze verwisseld en worden de elementen in het volgende paar vergeleken. Onder dezelfde voorwaarde wisselen ze ook van plaats. Het sorteren vindt dus in elke cyclus plaats totdat het einde van de array is bereikt.

C++-code

void SortAlgo::bubbleSort(int data, int lenD) ( int tmp = 0; for (int i = 0;i =(i+1);j--)( als (gegevens[j]

Invoegsoort

Bij invoegsortering wordt de array in twee gebieden gesplitst: geordend en ongeordend. Aanvankelijk is de gehele array een ongeordend gebied. Bij de eerste doorgang wordt het eerste element uit het ongeordende gebied verwijderd en op de juiste positie in het geordende gebied geplaatst.

Bij elke doorgang neemt de grootte van het geordende gebied met 1 toe en neemt de grootte van het ongeordende gebied met 1 af.

De hoofdlus loopt van 1 tot N-1. Bij de jde iteratie wordt element [i] op de juiste positie in het geordende gebied ingevoegd. Dit wordt gedaan door alle elementen van het geordende gebied die groter zijn dan [i] één positie naar rechts te verschuiven. [i] wordt ingevoegd in de ruimte tussen de elementen die kleiner zijn dan [i] en de elementen die groter zijn dan [i].

C++-code

void SortAlgo::insertionSort(int data, int lenD) ( int sleutel = 0; int i = 0; for (int j = 1;j =0 && data[i]>sleutel)( data = data[i]; i = i-1; data=sleutel; ) ) )

Sorteer samen

C++-code

void SortAlgo::mergeSort(int data, int lenD) ( if (lenD>1)( int middle = lenD/2; int rem = lenD-middle; int * L = new int; int * R = new int; for ( int i=0;i

Snel sorteren

Quicksort maakt gebruik van een verdeel en heers-algoritme. Het begint met het splitsen van de oorspronkelijke array in twee regio's. Deze onderdelen bevinden zich links en rechts van het gemarkeerde element, de zogenaamde steun. Aan het einde van het proces zal het ene deel elementen bevatten die kleiner zijn dan de referentie, en het andere deel zal elementen bevatten die groter zijn dan de referentie.

C++-code

void SortAlgo::quickSort(int * data, int const len) ( int const lenD = len; int pivot = 0; int ind = lenD/2; int i,j = 0,k = 0; if (lenD>1) ( int * L = nieuwe int ; int * R = nieuwe int ; pivot = data; for (i=0;i

Er zijn veel methoden ontwikkeld voor het in oplopende of aflopende volgorde sorteren (ordenen) van waarden in een array [Wirth, Knuth. t 3]. Laten we er drie bekijken, waarbij we voor de zekerheid aannemen dat de eerste n, n=6, elementen van de array X.

Bij elke volgende i-de stap, i=2, 3,…,n-1, wordt de waarde van de (i+1)e cel van de array verplaatst naar een verlaging van de celindex door de positie uit te wisselen met het getal van de vorige cel totdat Het zal niet blijken dat de vorige cel een kleiner getal bevat.

Uit het bovenstaande volgt dat bij het implementeren van de directe opnamemethode de buitenste lus n-1 keer moet worden uitgevoerd, en het maximaal mogelijke aantal uitvoeringen van de binnenste lus, in de hoofdtekst waarvan vergelijkingen en herschikkingen van getallen moeten worden uitgevoerd, zal toenemen van 1 naar n-1. De binnenste lus moet echter zo worden georganiseerd dat deze eindigt of helemaal niet wordt uitgevoerd wanneer de voorwaarde zich voordoet: de waarde in de vorige arraycel is kleiner dan in de huidige.

In ons voorbeeld:

Wanneer i=2, wisselt het getal 15 uit cel X 3 achtereenvolgens van plaats met het getal 34 uit cel X 2, en vervolgens met het getal 21 uit cel X 1,

Wanneer i=4, wisselt het getal 25 uit cel X 5 van plaats met het getal 34 uit cel X 3,

Hieronder staat een fragment van een programma voor het in oplopende volgorde ordenen van de eerste n elementen van de array X met behulp van de directe inclusiemethode (inclusie met behoud van de volgorde).

voor i:=1 tot n-1 wel

2. terwijl (X 0) doen

3. R:=X[j];

   X[j]:=X;

   X:=R;

Om de getallen in een array in aflopende volgorde te ordenen, volstaat het om bij elke stap de voorwaarde voor het permuteren van getallen in aangrenzende cellen van de array in het tegenovergestelde te veranderen, namelijk dat de uitwisseling van waarden van aangrenzende cellen zal worden uitgevoerd in de wanneer de vorige kleiner is dan de huidige.

Directe uitwisselingsmethode (bubbelmethode).

Deze methode is, net als de vorige, gebaseerd op de uitwisseling van waarden van aangrenzende cellen van de array, maar vanaf de allereerste stap in de sequentiële analyse, bij het verplaatsen van het ene uiteinde van de array naar het andere, worden alle paren van aangrenzende cellen van de array zijn hierbij betrokken.

Bij de eerste stap worden achtereenvolgens voor j = n, n-1, ..., 2 de waarden van aangrenzende cellen van de array vergeleken, en als de voorwaarde X j<Х j-1 выполняется их перестановка, в результате чего наименьшее число оказывается в ячейке Х 1 .

In ons voorbeeld zullen de gegevens in de array na het voltooien van de eerste stap als volgt worden gelokaliseerd:

Bij elke volgende stap zal het aantal gecontroleerde celparen met 1 afnemen. Over het algemeen wordt bij elke stap i, i=1, 2, 3, ..., n-1 het proces uitgevoerd voor j vanaf n tot i+1, in het bijzonder voor i= n-1 – slechts één keer voor de n-de en (n-1)-de cellen.

Uit het bovenstaande volgt dat bij het implementeren van de directe uitwisselingsmethode de buitenste lus n-1 keer moet worden uitgevoerd, en dat het aantal uitvoeringen van de binnenste lus, in de hoofdtekst waarvan vergelijkingen en herschikkingen van getallen moeten worden uitgevoerd, zal afnemen. van n-1 naar 1.

De oorsprong van de term ‘bubbelmethode’ wordt als volgt uitgelegd: als je je de verticale opstelling van arraycellen voorstelt met een toenemende index van boven naar beneden, dan zal het kleinste aantal van de beschouwde cellen naar boven stijgen als een bel in water.

In ons voorbeeld

Wanneer i=3 zullen permutaties leiden tot de volgende toestand van de array

Bij het gebruik van de bellenmethode maakt het niet uit of de analyse van getallenparen in de array naar stijgende of dalende indices evolueert, en het type ordening (oplopend of aflopend) wordt alleen bepaald door de voorwaarde van permutatie van getallen (de kleinere moet zich achter de grotere bevinden of omgekeerd).

Gemodificeerde directe uitwisselingsmethode (gemodificeerde bubbelmethode).

Zoals uit het bovenstaande numerieke voorbeeld blijkt, bleek de array na de vierde stap geordend te zijn, dat wil zeggen dat het mogelijk is om de buitenste lus niet n-1 keer uit te voeren, maar minder, wanneer bekend wordt dat de array al besteld. Deze controle is gebaseerd op het volgende: als er geen permutaties hebben plaatsgevonden tijdens de uitvoering van de binnenste lus, dan is de array al geordend en kunt u de buitenste lus verlaten. Een variabele van het Booleaanse type wordt gebruikt als teken of er een permutatie is uitgevoerd: voordat deze de binnenste lus binnengaat, krijgt deze een waarde, bijvoorbeeld False, en wanneer de permutatie wordt uitgevoerd, krijgt deze een andere waarde, bijvoorbeeld WAAR.

Het is duidelijk dat het effect van het gebruik van de gewijzigde bellenmethode in vergelijking met de ongewijzigde methode bij het versnellen van het sorteerproces zal worden waargenomen als de oorspronkelijke reeks getallen bijna in de gewenste richting is geordend. In het extreme geval, wanneer de array al op de gewenste manier is geordend, wordt de body van de buitenste lus slechts één keer uitgevoerd.

Wat is het idee achter selectiesoorten?

1. In een ongesorteerde subarray wordt gezocht naar een lokaal maximum (minimum).
2. Het gevonden maximum (minimum) wisselt van plaats met het laatste (eerste) element in de subarray.
3. Als er nog ongesorteerde subarrays in de array aanwezig zijn, zie punt 1.

Een kleine lyrische uitweiding. Aanvankelijk was ik van plan om in mijn serie artikelen materiaal over het sorteren van klassen opeenvolgend in strikte volgorde te presenteren. Daarna werden artikelen gepland over andere invoegalgoritmen: solitaire sort, Young table sort, eversion sort, enz.

Nu echter niet-lineariteit de trend is, zal ik vandaag, zonder alle publicaties over invoegsoorten te hebben geschreven, een parallelle draad over selectiesoorten starten. Daarna zal ik hetzelfde doen voor andere algoritmische klassen: samenvoegsoorten, distributiesoorten, enz. Over het algemeen kunt u hiermee publicaties over het ene of het andere onderwerp schrijven. Met zo'n thematische afwisseling wordt het leuker.

Selectie sorteren:: Selectie sorteren

Eenvoudig en pretentieloos - we doorlopen de array op zoek naar het maximale element. Het gevonden maximum wordt verwisseld met het laatste element. Het ongesorteerde deel van de array is met één element afgenomen (exclusief het laatste element waar we het gevonden maximum hebben verplaatst). We passen dezelfde acties toe op dit ongesorteerde deel: we vinden het maximum en plaatsen het op de laatste plaats in het ongesorteerde deel van de array. En we gaan zo door totdat het ongesorteerde deel van de array is teruggebracht tot één element.

Def selectie(data): voor i, e in enumerate(data): mn = min(range(i, len(data)), key=data.__getitem__) data[i], data = data, e return data

Eenvoudige selectiesortering is een dubbele zoekopdracht met brute kracht. Kan het verbeterd worden? Laten we een paar wijzigingen bekijken.

Dubbele selectie sorteren: Dubbele selectie sorteren

Een soortgelijk idee wordt gebruikt in , een variant van bubble sort. Als we door het ongesorteerde deel van de array lopen, vinden we onderweg naast het maximum ook het minimum. We zetten het minimum op de eerste plaats, het maximum op de laatste plaats. Het ongesorteerde deel wordt dus bij elke iteratie met twee elementen verkleind.

Op het eerste gezicht lijkt het erop dat dit het algoritme twee keer versnelt: na elke doorgang wordt de ongesorteerde subarray niet aan één kant verkleind, maar aan beide kanten tegelijk. Maar tegelijkertijd verdubbelde het aantal vergelijkingen, terwijl het aantal swaps onveranderd bleef. Dubbele selectie verhoogt de snelheid van het algoritme slechts lichtjes, en in sommige talen werkt het om de een of andere reden zelfs langzamer.

Het verschil tussen selectiesortering en invoegsortering

Het lijkt misschien dat selectie, sortering en sortering in wezen hetzelfde zijn: een algemene klasse van algoritmen. Nou ja, of invoegsortering - een soort selectiesortering. Of selectiesortering - een speciaal geval van invoegsortering. In beide gevallen halen we om beurten elementen uit het ongesorteerde deel van de array en sturen ze om naar het gesorteerde gebied.

Het belangrijkste verschil: bij invoegsortering extraheren we uit het ongesorteerde deel van de array elk element en plaats het op zijn plaats in het gesorteerde onderdeel. In selectiesoort zoeken we doelbewust maximaal element (of minimaal) waarmee we het gesorteerde deel van de array aanvullen. Bij invoegingen zoeken we waar we het volgende element moeten invoegen, en bij selectie weten we van tevoren al op welke plaats we het zullen plaatsen, maar tegelijkertijd moeten we een element vinden dat met deze plaats overeenkomt.

Dit maakt beide klassen algoritmen volledig verschillend van elkaar in hun essentie en de gebruikte methoden.

Bingo sorteren:: Bingo sorteren

Een interessant kenmerk van selectiesortering is dat de snelheid niet afhankelijk is van de aard van de gegevens die worden gesorteerd.

Als de array bijvoorbeeld bijna is gesorteerd, zal invoegsortering deze, zoals bekend, veel sneller verwerken (zelfs sneller dan snel sorteren). En een array met omgekeerde volgorde voor invoegsortering is een gedegenereerd geval; deze zal deze zo lang mogelijk sorteren.

En voor het sorteren van selecties maakt het gedeeltelijk of in omgekeerde volgorde van de array niet uit; deze wordt met ongeveer dezelfde snelheid verwerkt als normaal willekeurig. Bovendien maakt het bij klassieke selectiesortering niet uit of de array uit unieke of herhalende elementen bestaat; dit heeft vrijwel geen effect op de snelheid.

Maar in principe kun je slim worden en het algoritme aanpassen, zodat het voor sommige datasets sneller werkt. Bij bingosortering wordt er bijvoorbeeld rekening mee gehouden of de array uit dubbele elementen bestaat.

De truc hier is dat in het ongeordende deel niet alleen het maximale element wordt onthouden, maar ook het maximum voor de volgende iteratie wordt bepaald. Hierdoor kun je bij herhaalde maxima niet elke keer opnieuw zoeken, maar ze meteen op hun plaats zetten zodra dit maximum opnieuw in de array wordt aangetroffen.

De algoritmische complexiteit blijft hetzelfde. Maar als de reeks uit herhalende getallen bestaat, zal het sorteren van bingo tientallen keren sneller zijn dan het sorteren van gewone selecties.

# Bingo sorteer def bingo(data): # Eerste doorgang.

max = len(data) - 1 nextValue = data voor i binnen bereik(max - 1, -1, -1): als data[i] > nextValue: nextValue = data[i] while max en data == nextValue: max -= 1 # Volgende passen.

Cyclisch sorteren is interessant (en waardevol vanuit praktisch oogpunt) omdat veranderingen tussen de elementen van een array plaatsvinden als en alleen als het element op zijn definitieve plaats wordt geplaatst. Dit kan handig zijn als het herschrijven van een array te duur is en als u voorzichtig moet zijn met fysiek geheugen, moet u het aantal wijzigingen aan array-elementen minimaliseren.

Het werkt zo. Laten we de array doornemen en X de volgende cel in deze buitenste lus noemen. En we kijken naar welke plaats in de array we het volgende element uit deze cel moeten invoegen. Op de plaats waar je moet plakken staat een ander element, we sturen het naar het klembord. Voor dit element in de buffer zoeken we ook zijn plaats in de array (en plaatsen het op deze plek, en sturen het element dat op deze plek terechtkomt naar de buffer). En voor het nieuwe nummer in de buffer voeren we dezelfde acties uit. Hoe lang moet dit proces doorgaan? Totdat het volgende element op het klembord het element blijkt te zijn dat in cel X moet worden ingevoegd (de huidige locatie in de array in de hoofdlus van het algoritme). Vroeg of laat zal dit moment plaatsvinden en dan kun je in de buitenste lus naar de volgende cel gaan en daarvoor dezelfde procedure herhalen.

Bij andere selectiesoorten zoeken we naar het maximum/minimum om ze op de laatste/eerste plaats te plaatsen. Bij cyclussortering blijkt dat het minimum in de eerste plaats in de subarray zelf als het ware zelf is, terwijl verschillende andere elementen ergens in het midden van de array op hun rechtmatige plaats worden geplaatst.

En ook hier blijft de algoritmische complexiteit binnen O( n 2). In de praktijk is cyclisch sorteren zelfs meerdere keren langzamer dan regulier selectiesorteren, omdat je vaker door de array moet lopen en vaker moet vergelijken. Dit is de prijs voor het minimaal mogelijke aantal herschrijvingen.

# Cyclisch sorteren def cycle(data): # We doorzoeken de array op zoek naar cyclische cycli voor cycleStart in range(0, len(data) - 1): waarde = data # We zoeken waar we het element pos = cycleStart moeten invoegen voor i binnen bereik(cycleStart + 1, len(data)): als data[i]< value: pos += 1 # Если элемент уже стоит на месте, то сразу # переходим к следующей итерации цикла if pos == cycleStart: continue # В противном случае, помещаем элемент на своё # место или сразу после всех его дубликатов while value == data: pos += 1 data, value = value, data # Циклический круговорот продолжается до тех пор, # пока на текущей позиции не окажется её элемент while pos != cycleStart: # Ищем, куда переместить элемент pos = cycleStart for i in range(cycleStart + 1, len(data)): if data[i] < value: pos += 1 # Помещаем элемент на своё место # или сразу после его дубликатов while value == data: pos += 1 data, value = value, data return data

Pannenkoeken sorteren

Een algoritme dat door alle levensniveaus wordt beheerst - van tot.

In de eenvoudigste versie zoeken we naar het maximale element in het ongesorteerde deel van de array. Als het maximum is gevonden, maken we twee scherpe bochten. Eerst draaien we de keten van elementen om, zodat het maximum zich aan de andere kant bevindt. Vervolgens draaien we de hele ongesorteerde subarray om, waardoor het maximum op zijn plaats valt.

Dergelijke koorballets leiden over het algemeen tot een algoritmische complexiteit van O( n 3). Dit zijn getrainde ciliaten die in één klap tuimelen (daarom hebben hun prestaties een complexiteit van O( n 2)), en bij het programmeren is het omkeren van een deel van een array een extra lus.

Het sorteren van pannenkoeken is vanuit wiskundig oogpunt erg interessant (de knapste koppen hebben nagedacht over het schatten van het minimale aantal beurten dat voldoende is voor het sorteren); er zijn complexere formuleringen van het probleem (met de zogenaamde verbrande kant). Het onderwerp pannenkoeken is buitengewoon interessant, misschien zal ik een meer gedetailleerde monografie over deze kwesties schrijven.

# Pancake sort def pancake(data): if len(data) > 1: for size in range(len(data), 1, -1): # Positie van het maximum in het ongesorteerde deel maxindex = max(range(size) , key = data.__getitem__) if maxindex + 1 != size: # Als het maximum geen woorden is, dan moet je het omkeren als maxindex != 0: # Draai het zo # dat het maximum op de linkerdata staat[: maxindex+1] = reversed(data[:maxindex +1]) # Keer het ongesorteerde deel van de array om, # het maximum valt op zijn plaats data[:size] = reversed(data[:size]) retourneer gegevens

Selectie sorteren is slechts zo effectief als het zoeken naar het minimum/maximum element in het ongesorteerde deel van de array. In alle algoritmen die vandaag de dag worden geanalyseerd, wordt de zoekopdracht uitgevoerd in de vorm van dubbel zoeken. En dubbel zoeken, hoe je het ook bekijkt, zal altijd een algoritmische complexiteit hebben die niet beter is dan O( n 2). Betekent dit dat alle selectiesoorten gedoemd zijn tot vierkante complexiteit? Helemaal niet, als het zoekproces fundamenteel anders is ingericht. Beschouw een dataset bijvoorbeeld als een hoop en zoek binnen de hoop. Het onderwerp hopen is echter niet eens een artikel, maar een hele saga; we zullen het zeker over hopen hebben, maar een andere keer.

Alle hieronder beschreven methoden moeten worden beschouwd als speciale varianten van de zogenaamde methode directe selectiemethode of sorteer op selectie. Wat deze methoden gemeen hebben is het vinden (selecteren) van de maximale of minimale elementen van een array en deze in opeenvolgende cellen van de array plaatsen.

Methode voor het vinden van het minimumelement

De essentie van deze methode (rekening houdend met de geselecteerde beperkingen voor het numerieke voorbeeld dat we overwegen) is als volgt.

Bij de eerste stap wordt het minimumaantal van alle getallen in de array en de bijbehorende index gevonden en opgeslagen in een variabele, bijvoorbeeld Xmin, en wordt de index ervan opgeslagen in een andere variabele, bijvoorbeeld Imin, en vervolgens worden de posities in de array opgeslagen. array van het gevonden minimumaantal worden uitgewisseld met het eerste element van de array: X:=X ; X:=Xmin;.

In ons voorbeeld staat het minimumgetal Xmin=15 in cel Imin=3, en het herschikken van het eerste en minimumgetal zal tot het volgende resultaat leiden

Voor i=3 krijgen we Xmin=21 en Imin=4, en na herschikking

Voor i=5 krijgen we Xmin=34 en Imin=5, en na herschikking

De buitenste lus moet dus n-1 keer worden uitgevoerd, en het aantal uitvoeringen van de binnenste lus zal afnemen van n-1 naar 1. Om de array in aflopende volgorde te sorteren, moet het eerste gevonden minimumaantal worden verwisseld met het laatste. één, de tweede met de voorlaatste, enzovoort.

Maximale zoekmethode voor elementen

Deze methode verschilt alleen van de vorige doordat het maximale aantal elementen wordt gevonden. Met dezelfde organisatie van lussen bij het implementeren van deze methoden zullen ze precies tegenovergestelde resultaten opleveren: als de ene leidt tot een toename van de getallen in de array, leidt de andere tot een afname, en omgekeerd.

Indexzoekmethode minimaal element

Deze methode verschilt van de methode voor het zoeken naar het minimumelement en de index ervan doordat de binnenste lus wordt gebruikt om alleen naar de index van het minimumelement te zoeken, dus permutaties van getallen in de array bij elke stap i, i=1, 2 , ...,n-1 zal moeten worden uitgevoerd met behulp van een extra variabele, bijvoorbeeld R: R:=X[i]; X[i]:=X; X:=R;.

Maximale zoekmethode voor elementindex

Deze methode verschilt alleen van de vorige doordat de index van het maximale element wordt gevonden. Met dezelfde organisatie van lussen bij het implementeren van deze methoden zullen ze precies tegenovergestelde resultaten opleveren: als de ene leidt tot een toename van de getallen in de array, leidt de andere tot een afname, en omgekeerd.