Data sorteermethoden - presentatie. Sorteermethoden
Dit artikel bespreekt arrays sorteeralgoritmen. Om te beginnen worden geselecteerde algoritmen gepresenteerd met een korte beschrijving van hun werk, waarna het testen rechtstreeks wordt uitgevoerd, waarvan de resultaten in de tabel worden opgenomen en de eindconclusies worden gemaakt.
Het sorteren van algoritmen worden zeer veel gebruikt bij het programmeren, maar soms denken programmeurs niet eens over welk algoritme beter werkt dan alles (onder het concept van "best van alles" betekent een combinatie van snelheid en complexiteit van zowel schrijven als uitvoering).
In dit artikel zullen we proberen het uit te zoeken. Om de beste resultaten te garanderen, worden alle gepresenteerde algoritmen een geheel getal-reeks van 200 elementen sorteren. De computer waarop tests worden uitgevoerd, heeft de volgende kenmerken: AMD A6-3400M 4x1.4 GHz-processor, 8 GB RAM, Windows-besturingssysteem 10 X64 Build 10586.36.
Voor het onderzoek werden de volgende sorteeralgoritmen geselecteerd:
Selectie Sorteer (Sorteer op selectie) - De essentie van het algoritme ligt in de doorgang langs de array van het begin tot het einde in de zoektocht naar het minimumelement van de array en het verplaatsen naar het begin. De complexiteit van een dergelijk O (N2) -algoritme.
Bubble sorteren (sorteren op bubble) - Dit algoritme verandert in plaatsen twee aangrenzende elementen als het eerste element van de array groter is dan de tweede. Dit gebeurt totdat het algoritme alle niet-gesorteerde elementen op plaatsen uitwisselt. De complexiteit van dit sorteeralgoritme is O (N ^ 2).
Insertion Sorteer (sorteerinzetstukken) - Het algoritme sorteert een array omdat het door zijn elementen gaat. Element neemt elke iteratie en vergeleken met elk element in het reeds gesorteerde deel van de array, dus het vinden van "zijn plaats", waarna het element in zijn positie wordt ingebracht. Dit gebeurt totdat het algoritme door het massief passeert. Bij de uitgang krijgen we een gesorteerde array. De complexiteit van dit algoritme is gelijk aan O (N ^ 2).
Snelle sorteer (snelle sorteer) - De essentie van het algoritme is om de array te verdelen voor twee sub-array, de middelste lijn wordt beschouwd als een element dat zich in het midden van de array bevindt. In de loop van het werk van het algoritme zullen elementen minder dan het gemiddelde naar links en groot rechts worden verplaatst. Dezelfde actie zal recursief en met onder-array voorkomen, ze zullen worden onderverdeeld in twee onder-array totdat er iets te gescheiden is (één element zal blijven). Bij de uitgang krijgen we een gesorteerde array. De complexiteit van het algoritme is afhankelijk van de invoergegevens en is op zijn best gelijk aan O (N × 2LOG2N). In het ergste geval o (n ^ 2). Er is ook een gemiddelde waarde, dit o (n × log2n).
Kam sorteren (sorteerkam) - Het idee van het werk van het algoritme is uitermate vergelijkbaar met het sorteren van de uitwisseling, maar het belangrijkste verschil is dat niet twee aangrenzende elementen worden vergeleken, maar elementen op het interval, bijvoorbeeld in vijf elementen. Het geeft aan het ontdoen van kleine waarden aan het einde, wat bijdraagt \u200b\u200baan de versnelling van sortering in grote arrays. De eerste iteratie wordt uitgevoerd in een stap die wordt berekend door de formule (array-grootte) / (afname factor), waarbij de afnamefactor ongeveer 1.247330950103979 is, of afgerond tot 1,3. De tweede en daaropvolgende iteraties zullen plaatsvinden in een stap (huidige stap) / (reductiefactor) en zullen plaatsvinden totdat de stap gelijk is aan één. Bijna in ieder geval is de complexiteit van het algoritme gelijk aan O (N × Log2N).
Voor testen wordt het uitgevoerd op 5 lanceringen van elk algoritme en is de beste tijd geselecteerd. De beste tijd en het gebruikte geheugen worden vermeld in de tabel. Het testen van de sorteersnelheid van een array van 10, 50, 200 en 1000 elementen zal worden getest om te bepalen voor welke taken een specifiek algoritme is bedoeld.
Volledig ongezouten array:
Gedeeltelijk gesorteerde array (de helft van de elementen wordt besteld):
Resultaten verstrekt in diagrammen:
Als gevolg van het verkregen onderzoek en gegevens, om de ongezette array te sorteren, is de meest optimale van de gepresenteerde algoritmen voor het sorteren van de array snel sorteren. Ondanks de langere uitvoeringstijd verbruikt het algoritme minder geheugen, wat belangrijk kan zijn in grote projecten. Echter, dergelijke algoritmen als sorteren door de keuze, uitwisseling en inserts kunnen echter beter wetenschappelijke doeleinden benaderen, bijvoorbeeld bij het leren waar u geen enorme hoeveelheid gegevens hoeft aan te pakken. Met een gedeeltelijk gesorteerde array zijn de resultaten niet erg verschillend, alle sorteeralgoritmen tonen de tijd voor ongeveer 2-3 milliseconden minder. Bij het sorteren van een gedeeltelijk gesorteerde array werkt snel sortering veel sneller en verbruikt een kleinere hoeveelheid geheugen.
Het artikel bespreekt een van de meest populaire sorteeralgoritmen voor arrays die zowel praktisch als voor trainingsdoeleinden worden gebruikt. Meteen wil ik een reservering maken dat alle beschouwde algoritmen langzamer zijn dan de methode van klassieke sortering van de array door de lijst met waarden, maar toch de aandacht verdienen. Er zijn veel teksten, dus volgens elk algoritme beschrijf ik de meest elementaire.
1. Het algoritme "Sorteren op selectie".
Het is een van de eenvoudigste solide sorteeralgoritmen. De betekenis is om door de array te gaan en elke keer dat het is om te zoeken naar het minimumelement van de array, het uitwisselen van het met het initiële element van het ongezette deel van de array. In kleine arrays kan het nog efficiënter zijn dan meer complexe sorteeralgoritmen, maar verliest in elk geval op grote arrays. Het aantal uitwisselingen van elementen in vergelijking met de "bubble" -algoritme N / 2, waarbij n het aantal array-elementen is.
Algoritme:
1. Zoek het minimumelement in de array.
2. Wij veranderen het minimum- en eerste element op plaatsen.
3. Nogmaals, we zoeken het minimumelement in het ongezouten deel van de array
4. Wij veranderen het tweede element van de array en het gevonden minimum, omdat het eerste element van de array is gesorteerd.
5. We zijn op zoek naar minimale waarden en veranderen plaatst de elementen totdat de array tot het einde is gesorteerd.
// selecteren van de selectie (--- functie sorteren / zoomen (teken array) min \u003d 0; voor i \u003d 0 door array.vurrant () Cycle min \u003d i; voor j \u003d i + 1 door array () Cyclus // Wij zijn op zoek naar minimaal element in een array als een array [J]< Массив[Мин] Тогда Мин = j; КонецЕсли; КонецЦикла; Если Массив [Мин] = Массив [i] Тогда //Если мин. элемент массива = первому элементу неотс. части массива, то пропускаем. Продолжить; КонецЕсли; Смена = Массив[i]; //Производим замену элементов массива. Массив[i] = Массив[Мин]; Массив[Мин] = Смена; КонецЦикла; Возврат Массив; КонецФункции
2. Sorteer op bubble-algoritme.
Misschien is het beroemdste algoritme dat is toegepast voor academische doeleinden te traag voor de praktische toepassing. Het algoritme ligt ten grondslag aan meer complexe algoritmen: "Shaker sorteren", "Pyramidale sorteren", "Snelle sorteren". Het is opmerkelijk dat een van de snelste algoritmen "Snel algoritme" is ontwikkeld door een van de slechtste bubbel sorteeralgoritmen te upgraden. "Snel" en "Shaker" sorteren wordt verder overwogen. De betekenis van het algoritme is dat de meest "lichte" elementen van de array als het "pop-up" is, en de meest "zware" dun ". Vandaar de naam "Sorteren op bubble"
Algoritme:
1. Elk element van de array wordt vergeleken met de daaropvolgende en als het [I] -element\u003e -element wordt vervangen. Dus, de meest "lichte" elementen zijn "pop-up" - ga naar de bovenkant van de lijst, en de moeilijkste "drone" beweegt tot een einde.
2. We herhalen stap 1 N-1 keer, waarbij n een array is. Nieuwe nomecy ().
// Sorteren op een bubbel (--- functie met een soort verband (monsterarray) voor i \u003d 0 door array.vürnica () Cyclus voor j \u003d 0 door array.v.vurrant () - I - 1 cyclus als een array [j]\u003e array DAN vervanging \u003d een array [J]; array [J] \u003d array; array \u003d vervanging; beëindigd; Endackel; Sandflose; retour-array; Eindfunctie //--)
3. Garrier "Shaker Sorting" (sorteren op roeren, bidirectionele bubble sorteren).
Het algoritme is een van de versies van de vorige sortering - "Sorteren door Bubble". Het belangrijkste verschil is dat in de klassieke sortering de bubbel een unidirectionele beweging van elementen uit de onderkant optreedt, dan in de shaker-sortering, het neemt de bottom-up en vervolgens op top-down.
Het algoritme is hetzelfde als in bubble sorteren + de luscyclus van bovenaf is toegevoegd.
In het onderstaande voorbeeld is er een verbetering van de shaker-sortering. In tegenstelling tot klassiek, 2 keer minder gebruikt dan iteraties.
// Sorteren (Shaker-sorteren) (--- functie sorteren permeyssing (monster array) voor i \u003d 0 door array.Vurrant () / 2 Нитер \u003d 0; context \u003d array (); tot niter array [niter + 1] Vervanging \u003d array [niter]; array [niter] \u003d array [niter + 1]; array [niter + 1] \u003d vervanging; beëindigd; niter \u003d niter + 1; // bewegende de positie vooruit // passeren met einde Array [ConinterTee - 1]\u003e Een array [conintertee] dan vervangen \u003d array [conintertee - 1]; array [coniferous-1] \u003d array [conisator]; array [conisator] \u003d vervanging; beëindigd; context \u003d transporteur - 1; / / Verplaats de positie een stap achteruit; de endackel; retourarray; endfunctie // ---)
4. Algoritme "GNOME SORTING".
Het algoritme is zo vreemd genoemd dankzij de Nederlandse wetenschapper Dick Pear.
GNOME Gesorteerd is gebaseerd op de techniek die wordt gebruikt door de gebruikelijke Nederlandse Tuin GNOME (NETERL. TUINKABOUTER). Dit is een methode die de Garden Gnome de bloempotleiding sorteert. In wezen kijkt hij naar de volgende en vorige tuinpotten: als ze in de juiste volgorde zijn, loopt hij op één pot naar voren, anders verandert hij ze op plaatsen en loopt op één pot terug. Grensvoorwaarden: als er geen eerdere pot is, stopt hij naar voren; Als er geen volgende pot is, eindigde hij.
Dick arm.
Hier is de daadwerkelijke beschrijving van het algoritme "GNOME SORTING". Wat interessant is, bevat het algoritme geen geneste cycli en sorteert de hele array in één pas.
// gnome sorteren (--- de functie van de dwarfish (tekenarray) i \u003d 1; j \u003d 2; tot nu toe< Массив.Количество() Цикл // Сравнение < - Сортировка по возрастанию, > - Aflopend als een array i \u003d J; j \u003d j + 1; Anders is de vervanging \u003d array [i]; Array [i] \u003d array; Array \u003d vervanging; i \u003d I - 1; Als ik \u003d 0 dan I \u003d J; j \u003d j + 1; Eindigde; Eindigde; Endcycle; Een array retourneren; Endfunctie // ---)
5. Algoritme "Sorteren op inserts".
Het is een eenvoudig sorteeralgoritme. De betekenis is dat we bij elke stap een element nemen, we zijn op zoek naar een positie voor hem en inslaan op de juiste plaats.
Elementair voorbeeld: bij het spelen in een dwaas, trekt u de kaart uit het dek en steekt u deze in een geschikte plaats in een toename in uw beschikbare kaarten. Of
in de winkel heb je een levering van 550 roebel, één rekening van 500, nog eens 50. Ze kijken in de portemonnee, en er is een waardigheid van 10.100.1000. Je plaatst rekeningen
dosto Compound 50p. Tussen de rekeningen van waardigheid 10P en 100R, en de rekening van 500 roebel tussen rekeningen 100 roebel en 1000r. Het blijkt 10.50.100.500.1000 - hier ben jij
en het algoritme "sorteer inserts."
Met elke stap van het algoritme moet u de gegevens op de informatie sorteren en de waarde op de juiste plaats invoegen.
// Sorteer op inserts (--- functie sorteren. En vervanging< Массив Цикл Массив[j] = Массив; Замена = j - 1; Ключ = j - 1; j = j - 1; КонецЦикла; Массив[Ключ] = Замена; КонецЦикла; Возврат Массив; КонецФункции //---}
6. Algoritme "sorteren sorteren".
Interessant in termen van implementatie en ideeën-algoritme. De betekenis ervan om de array op de rebellen te doorbreken totdat de lengte van elke onderzeeër gelijk is aan 1. Dan beweren we dat een dergelijk subsysteem is gesorteerd. Dan voegen we de resulterende submassagels samen, tegelijkertijd de elementaire waarden van de onderzeeërs te vergelijken en te sorteren.
p / S kon geen tekening plaatsen met een meer visuele regeling, constant besmeurd. Maar het is duidelijk zichtbaar in het screenshots blokkeren hieronder. Je kunt zien hoe het algoritme werkt.
// samenvoegen sorteren (---
Sorteerfunctie (tekenarray) als een array. Racing () \u003d 1 retourneer de array; Eindigde; Punt) \u003d array. Naliteit () / 2; LJASIVE \u003d nieuwe array; PASSIVE \u003d nieuwe array; Voor SCH \u003d 0 door array.vurrant () Cycle IF SCH< ТочкаРазрыв Тогда лМассив.Добавить(Массив[Сч]); Иначе прМассив.Добавить(Массив[Сч]); КонецЕсли; КонецЦикла; Возврат Слияние(СортировкаСлиянием(лМассив),СортировкаСлиянием(прМассив)); КонецФункции Функция Слияние(массив1,массив2) a = 0; b = 0; слМассив = Новый Массив; Для Сч = 0 ПО (Массив1.Количество() + Массив2.Количество())-1 Цикл слМассив.Добавить(); КонецЦикла; Для i = 0 ПО (массив1.Количество() + массив2.Количество())-1 Цикл Если b < массив2.Количество() И a < массив1.Количество() Тогда Если (массив1[a] > array 2 [b]) en (b< массив2.Количество()) Тогда слМассив[i] = массив2[b]; b = b + 1; Иначе слМассив[i] = массив1[a]; a = a + 1; КонецЕсли; Иначе Если b < массив2.количество() Тогда слМассив[i] = массив2[b]; b = b + 1; Иначе слМассив[i] = массив1[a]; a = a + 1; КонецЕсли; КонецЕсли; КонецЦикла; Возврат слМассив; КонецФункции //---}
7. Allegortim "Sorteer Shell".
Het algoritme wordt zo genoemd ter ere van de Amerikaanse wetenschapper Donald Shell. In wezen is dit algoritme een verbeterde algoritme "sorteerinzetstukken". De betekenis van het algoritme is om niet alleen de elementen naast elkaar te vergelijken, maar op enige afstand. Aanvankelijk wordt een stap geselecteerd - een interval waardoor de elementen van de array worden vergeleken met elke iteratie. Het wordt meestal door dit bepaald:
Voor de eerste iteratie, stap \u003d inname (array. Nationaliteit () / 2), voor opeenvolgende stap \u003d 2 (stap / 2). Die. Geleidelijk wordt de stap verminderd en wanneer de stap gelijk is aan 1, zal de laatste vergelijking plaatsvinden en wordt de array gesorteerd.
Voorbeeld:
Een array wordt gegeven (10,5,31,14,27,12).
1. Stap \u003d 4.
We assorteren de eenvoudige inserts elke 4 groepen van 2 elementen (10.14) (5.2) (3.7) (1.12)
10 ,2 ,3 ,1,14 ,5 ,7 ,12
2. Stap \u003d 2
We assorteren de eenvoudige inserts elke 2 groepen van 4 elementen (10,3,114,7) (2,15,12)
3 ,1 ,7 ,2 ,10 ,5 ,14 ,12
3. Stap \u003d 1
We sorteren de eenvoudige inzetstukken elke 1 groep van 8 elementen.
1,2,3,5,7,10,12,14
// Sorteer Shell (--- Function Sortingchella (Sign Array) Stap \u003d Complex (array. Naliteit () / 2); terwijl stap\u003e 0 cyclus i \u003d 0; tot nu toe< (Массив.Количество() - Шаг) Цикл j = i; Пока j >\u003d 0 en array [j]\u003e array van de vervangende cyclus \u003d array [j]; Array [j] \u003d array; Array \u003d vervanging; j \u003d j - 1; Als de beeldvormingen vervolgens ingeschakeld worden weergegeven (array); Eindigde; Endcycle; i \u003d I + 1; Endcycle; Stap \u003d Inname (stap / 2); Verwerkingspreservatie (); Endcycle; Een array retourneren; Endfunctie // ---)
8. Algoritme "Snelle sorteren".
Het meest populaire en toegepaste algoritme in de praktijk. Het is een van de meest effectieve algoritmen voor gegevens sorteren.
De hele essentie van het algoritme komt naar beneden om de uitdagende taak uit te breken en ze afzonderlijk op te lossen. Een bepaald referentiepunt is geselecteerd en alle waarden die minder naar links zijn verplaatst, is de rest goed. Vervolgens, voor elk verkregen deel, het uitvoeren van hetzelfde, zolang de onderdelen niet worden verpletterd. Aan het einde krijgen we een aantal gesorteerde onderdelen die u gewoon in 1 geheel wilt lijmen.
// Algoritme "Snelle sorteren" (PROCEDURE B_SORTERY (ARRAY, NIZHNY PELO, UPPORE POIL) I \u003d NIZHNNYPHIPIELD; J \u003d upperfield; M \u003d array [2 ((i + j) / 2)]; terwijl de waarheid de cyclus is terwijl de array [i]< m Цикл i = i + 1; КонецЦикла; Пока Массив[j] > m cyclus j \u003d j - 1; Endcycle; Als I\u003e J dan onderbreekt; Eindigde; Endcycle; Als Nizhnyphield< j Тогда б_Сортировка(Массив,НижнийПредел,j); КонецЕсли; Если i < ВерхнийПредел Тогда б_Сортировка(Массив,i,ВерхнийПредел); КонецЕсли; КонецПроцедуры Функция БыстраяСортировка(Массив) НижняяГраница = 0; ВерхняяГраница = Массив.ВГраница(); б_Сортировка(Массив,НижняяГраница,ВерхняяГраница); Возврат Массив; КонецФункции //---}
9. Klassieke sorteren van een array in 1c.
We zenden een array naar de lijst met waarden. We assorteren de standaard "sorteer" -methode.
// Sorteren op de lijst met waarden (--- de functie van de sorteeracceptatie (tekenarray) van de MSiscznch \u003d Nieuwe lijst van benaderingen; Mspisokznch
Alle sorteren kan worden versneld door de code in cycli in 1 regel te plaatsen. Maar voor leesbaarheid, vertrokken dus.
Geplaatst door verwerking waarin alle bovengenoemde algoritmen worden geïmplementeerd, wordt ook de dynamische animatie van het sorteerproces ondersteund. (Behalve standaard sorteren 1c) .
- Startende verwerking automatisch, de reeks willekeurige nummers van 0 tot 100 dimensies van 100 elementen vormt automatisch.
- Voor het maken van een andere array moet u klikken op de knop "Creëren van HSH MAXIF", u kunt ook het vereiste bereik kiezen.
- Voor opname van dynamische animatie moet worden aangevinkt op "Display sorteren in de diagram". Ik adviseer u op ineffectieve algoritmen om een \u200b\u200bvinkje te installeren met de dimensie van de array tot 100 elementen, anders wacht u op het sorteren :)
Dynamische tekening van het sorteerproces vermindert de prestaties aanzienlijk, maar kan duidelijk zien hoe het algoritme werkt.
Invoering .
Ongeveer drie en een halve decennia zijn gepasseerd sinds de voetstukjes worden geïntroduceerd als een academische discipline-programmering voor computers. Met de enorme snelheid van veranderingen in het onderwerp, was altijd de snelheid van de snelheid van centrale uitgeversmechanismen, speciaal gericht op de pedavische programma's van de boeken niet vaker, dan een keer in een decennium - het is nauwelijks evenredig aan de snelheid van verandering van Generaties van computers. Tegenwoordig zijn de planken van boekwinkels barst van publicaties op de informatica. Echter, de leraar (en de meeste studenten) Speciale trainingsboeken, de inhoud en focus waarvan voldoen aan het opgegeven curriculum en het programma zijn nog steeds erg nodig. Nu worden, naast het programmeren, andere complexere speciale cursussen, op de kruising van toegepaste (discrete) wiskunde en informatica, geïntroduceerd in sommige specialiteiten in voetstukken.
In deze cursus kunt u kennismaken met arrays en leren over de eenvoudige en complexe methoden van hun sortering, evenals waarvan het meest effectief is en in welke gevallen.
1. Sorteer taken.
1.1. Gemeenschappelijke bepalingen.
De hoofdtaak is om verschillende sorteermethoden te demonstreren en het meest effectief van hen toe te wijzen. Sorteren is een vrij goed voorbeeld van een taak die kan worden opgelost met veel verschillende algoritmen. Elk van hen heeft zijn eigen voordelen en hun tekortkomingen en kies het algoritme, op basis van de specifieke instelling van het probleem.
In het algemeen moet het sorteren worden begrepen als het proces van hergroepering van een gegeven set objecten in een specifieke volgorde. Het doel van de soort is om de volgende zoektocht naar items in een dergelijke gesorteerde set te vergemakkelijken. Dit is bijna universele, fundamentele activiteiten. We ontmoeten gesorteerde objecten in telefoonboeken, in inkomstenbelastingen, in de tafels van boeken, in bibliotheken, in woordenboeken, in magazijnen - bijna overal, waar u moet zoeken naar opgeslagen objecten.
Het gesprek over het sorteren is dus behoorlijk passend en belangrijk, als het gaat om gegevensverwerking. De eerste interesse in sortering is gebaseerd op het feit dat bij het bouwen van algoritmen, we vele zeer fundamentele technieken hebben. Er zijn bijna geen methoden die niet moeten voldoen bij het bespreken van deze taak. Sorteren is in het bijzonder het perfecte voorwerp voor de demonstratie van een enorme verscheidenheid aan algoritmen, ze zijn allemaal uitgevonden voor dezelfde taak, veel in zekere zin zijn optimaal, de meerderheid hebben hun voordelen. Daarom is het ook een ideaal object dat de noodzaak om de prestaties van algoritmen te analyseren. Bovendien kan op voorbeelden van sorteren worden getoond, zoals door het algoritme te compliceren, hoewel er al voor de hand liggende methoden zijn, kunt u een aanzienlijke winst bereiken in efficiëntie.
De selectie van het algoritme is afhankelijk van de structuur van de verwerkte gegevens is bijna de wet, maar in het geval van een sorteren is een dergelijke afhankelijkheid zo diep dat de bijbehorende methoden in twee klassen - sorteerarrays en sorteerbestanden (sequenties) braken. Soms worden ze interne en externe sortering genoemd, omdat arrays worden opgeslagen in snel, operationeel, intern geheugen van de machine met willekeurige toegang, en de bestanden worden meestal in een langzamer geplaatst, maar ook meer externe geheugencapacles op apparaten op basis van mechanische verplaatsingen ( schijven of tapes).
, een, ......, en vervolgens sorteren is de permutatie van deze elementen in een AK-array, AK, ..., Akfe AK<= ak <= ….. <= ak.Wij zijn van mening dat het type item wordt gedefinieerd als een geheel getal.
Constn \u003d ???; // Hier specificeert de gewenste lengte van de array
Var A: array of integer;
De keuze van integer tot op zekere hoogte willekeurig. Het was mogelijk om te nemen en
een ander type waarop de gemeenschappelijke relatie wordt bepaald.
De sorteermethode wordt stabiel genoemd als tijdens het sorteerproces de relatieve locatie van elementen met gelijke sleutels niet verandert. Sorteerstabiliteit is vaak wenselijk als het gaat om elementen die reeds bestelde (gesorteerd) in sommige secundaire sleutels (d.w.z. eigenschappen) die geen invloed hebben op de hoofdsleutel.
1.2. Het instellen van de taak van sorteren van arrays.
Basisvoorwaarde: de geselecteerde methode van sorteerarrays moet economisch het beschikbare geheugen gebruiken. Dit suggereert dat de permutaties die de elementen in orde moeten worden uitgevoerd op dezelfde plaats die wil zeggen, de methoden waarin elementen uit array A worden verzonden naar de resulterende array B aanzienlijk minder belang zijn. We zullen eerst de methoden voor hun economie, d.w.z. classificeren, tegen de tijd van hun werk. Een goede effectiviteit kan C zijn - het aantal sleutelvergelijkingen en M is het aantal doorstuurde (permutaties) van elementen. Deze cijfers zijn de essentie van de functie van N - het aantal gesorteerde elementen. Hoewel goede sorteeralgoritmen de volgorde van n * logn-vergelijkingen vereisen, onderzoeken we eerst verschillende eenvoudige en voor de hand liggende methoden, ze worden direct genoemd, waar N2-toetsenvergelijkingen vereist zijn. Begin analyse van directe methoden, niet de aanraking van snelle algoritmen, we veroorzaken dergelijke redenen:
1. Directe methoden zijn bijzonder handig om de kenmerkende kenmerken van de basisprincipes van de meeste sortering uit te leggen.
2. Programma's van deze methoden zijn gemakkelijk te begrijpen, en ze zijn kort.
3. Volledige methoden vereisen een groot aantal operaties, en daarom zijn voor voldoende kleine N-directe methoden sneller, hoewel het niet mag worden gebruikt om ze te gebruiken.
De methoden voor het sorteren "op dezelfde plaats" kunnen worden verdeeld in overeenstemming met de definiërende principes voor drie hoofdcategorieën:
· Sorteren op inclusie (Byinsertion).
· Sorteren op selectie.
· Sorteren op beurzen (doorhexchange).
Nu verkennen we deze principes en vergelijken we ze. Alle programma's worden bediend door een array a.
Constn \u003d.<длина массива>
a: array ofIteger;
2. Methoden voor het sorteren van arrays.
2.1. Eenvoudige methoden voor het sorteren van arrays.
2.1.1. Sorteer op directe opname.
Deze methode wordt veel gebruikt bij het speelkaarten. Elementen zijn mentaal verdeeld in reeds "ready" -sequentie
, ... en de originele volgorde. Met elke stap, beginnend met I \u003d 2 en toenemende I Elke keer per eenheid, van de initiële sequentie, worden de i- de elementen opgehaald en verschoven in de afgewerkte volgorde, terwijl deze op de gewenste locatie wordt geplaatst.Programma 2.1. Ondersteuning met behulp van directe opname.
I, J, N, X: Integer;
A: array of integer;
Writeln ('voer de lengte van de array' in ');
Writeln ('ingebouwde');
Voor I: \u003d 1 tot n Lees (A [I]);
Voor i: \u003d 2 to n do