Wat is een sorteeralgoritme?

sorteeralgoritmen zijn een reeks instructies die een array of lijst als invoer nemen en de items in een bepaalde volgorde rangschikken.

waarom sorteeralgoritmen belangrijk zijn

omdat Sorteren vaak de complexiteit van een probleem kan verminderen, is het een belangrijk algoritme in de informatica. Deze algoritmen hebben directe toepassingen in het zoeken van algoritmen, database algoritmen, verdeel en heers methoden, data structuur algoritmen, en nog veel meer.,

Trade-Offs van algoritmen

bij het gebruik van verschillende algoritmen moeten enkele vragen worden gesteld. Hoe groot wordt de collectie gesorteerd? Hoeveel geheugen is beschikbaar om te gebruiken? Moet de collectie groeien?

de antwoorden op deze vragen kunnen bepalen welk algoritme het beste zal werken voor de situatie. Sommige algoritmen zoals merge sort kunnen veel ruimte nodig hebben om uit te voeren, terwijl insertion sort niet altijd de snelste is, maar het vereist niet veel middelen om uit te voeren.,

u moet bepalen wat de vereisten van het systeem zijn en zijn beperkingen voordat u beslist welk algoritme u wilt gebruiken.

enkele veel voorkomende sorteeralgoritmen

enkele van de meest voorkomende sorteeralgoritmen zijn:

  • selectie Sorteer
  • Bubble Sorteer
  • invoegen Sorteer
  • snel Sorteren
  • Heap Sorteer
  • tellen Sorteer
  • Radix Sorteer
  • Bucket Sorteer

maar voordat we in elk van deze, Laten we leren een beetje meer over wat maakt classificeert een sorteeralgoritme.,

classificatie van een sorteeralgoritme

sorteeralgoritmen kunnen worden gecategoriseerd op basis van de volgende parameters:

  1. gebaseerd op het aantal Swaps of inversie dit is het aantal keren dat de algoritme swaps elementen de invoer Sorteren. Selection Sort vereist het minimumaantal swaps.
  2. gebaseerd op het aantal vergelijkingen is dit het aantal keren dat het algoritme elementen vergelijkt om de invoer te sorteren., Met behulp van Big – O-notatie vereisen de bovenstaande voorbeelden van sorteeralgoritmen ten minste O(nlogn) vergelijkingen in het beste geval en O(n^2) vergelijkingen in het slechtste geval voor de meeste outputs.
  3. gebaseerd op recursie of Non-recursie sommige sorteeralgoritmen, zoals Quick Sort , gebruiken recursieve technieken om de invoer te sorteren. Andere sorteeralgoritmen , zoals Selection Sort of Insertion Sort, gebruiken niet-recursieve technieken., Tot slot maken sommige sorteeralgoritmen , zoals Merge Sort, gebruik van zowel recursieve als niet-recursieve technieken om de invoer te sorteren.
  4. gebaseerd op Stabiliteitssorteeralgoritmen wordt gezegd dat stable zijn als het algoritme de relatieve volgorde van elementen met gelijke sleutels behoudt. Met andere woorden, twee gelijkwaardige elementen blijven in dezelfde volgorde in de gesorteerde output als ze waren in de input.,
  5. Insertion sort , Merge Sort , and Bubble Sort are stable
  6. Heap Sort and Quick Sort are not stable
  7. Based on Extra Space Requirement Sorting algorithms are said to be in place if they require a constant O(1) extra space for sorting.,
  8. Insertion sort en Quick-sort zijn in place Sorteer als we de elementen over de pivot verplaatsen en geen aparte array gebruiken, wat niet het geval is in merge Sorteer waarbij de grootte van de invoer vooraf moet worden toegewezen om de uitvoer tijdens de Sorteer op te slaan.
  9. Merge Sort is een voorbeeld van out place Sorteer omdat het extra geheugenruimte nodig heeft voor zijn operaties.,

Best mogelijke tijdscomplexiteit voor elke vergelijking gebaseerde sortering

elk vergelijking gebaseerd sorteeralgoritme moet ten minste nLog2n vergelijkingen maken om de input array te sorteren, en Heapsort en merge sort zijn asymptotisch optimale vergelijkingssoorten. Dit kan gemakkelijk worden bewezen door een beslissingsboomdiagram te tekenen.

Bucket Sort

Bucket Sort is een vergelijkingssorteeralgoritme dat op elementen werkt door ze in verschillende emmers te verdelen en deze emmers vervolgens afzonderlijk te sorteren., Elke emmer wordt afzonderlijk gesorteerd met behulp van een apart sorteeralgoritme of door het bucket sorteeralgoritme recursief toe te passen.

Bucket Sort is vooral nuttig wanneer de invoer gelijkmatig over een bereik is verdeeld.

stel dat je het volgende probleem voor je hebt

Je hebt een grote array van drijvende komma gehele getallen gekregen die gelijkmatig tussen de onder-en bovengrens liggen. Deze array moet nu gesorteerd worden.

een eenvoudige manier om dit probleem op te lossen zou zijn om een ander sorteeralgoritme te gebruiken, zoals Merge sort, Heap Sort of Quick Sort., Deze algoritmen garanderen echter een best case time complexiteit van O (NlogN). Met behulp van bucket sort kan de bovenstaande taak echter in o(N)tijd worden voltooid.

laten we het eens nader bekijken.

bedenk dat u een array van lijsten moet maken, dat wil zeggen van emmers. Elementen moeten nu worden ingevoegd in deze emmers op basis van hun eigenschappen. Elk van deze emmers kan vervolgens individueel worden gesorteerd met behulp van Insertion Sort.,

Pseudo-Code voor Bucket Sort:

void bucketSort(float a,int n){ for(each floating integer 'x' in n) { insert x into bucket; } for(each bucket) { sort(bucket); }}

het tellen van de sortering

Het tellen van de sortering is een Sorteertechniek gebaseerd op sleutels tussen een specifiek bereik. Het werkt door het tellen van het aantal objecten met verschillende sleutelwaarden (soort hashing). Vervolgens wat rekenkunde doen om de positie van elk object in de Uitvoerreeks te berekenen.,

voorbeeld:

For simplicity, consider the data in the range 0 to 9. Input data: 1, 4, 1, 2, 7, 5, 2 1) Take a count array to store the count of each unique object. Index: 0 1 2 3 4 5 6 7 8 9 Count: 0 2 2 0 1 1 0 1 0 0 2) Modify the count array such that each element at each index stores the sum of previous counts. Index: 0 1 2 3 4 5 6 7 8 9 Count: 0 2 4 4 5 6 6 7 7 7The modified count array indicates the position of each object in the output sequence. 3) Output each object from the input sequence followed by decreasing its count by 1. Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2. Put data 1 at index 2 in output. Decrease count by 1 to place next data 1 at an index 1 smaller than this index. 

eigenschappen

implementatie in JavaScript

C++ implementatie

Swift implementatie

Invoegsortage

Invoegsortage is een eenvoudig sorteeralgoritme voor een klein aantal elementen.

voorbeeld:

bij invoegen vergelijkt u hetkey element met de vorige elementen. Als de vorige elementen groter zijn dan het key element, dan verplaats je het vorige element naar de volgende positie.

begin van index 1 tot de grootte van de invoer array.,fb52f3aa”>

Step 2 :

 key = 5 //2nd index 8 > 5 //move 8 to 2nd index and insert 5 to the 1st index. Result: 

Step 3 :

 key = 1 //3rd index 8 > 1 => 5 > 1 => 3 > 1 => Result: 

Step 4 :

 key = 4 //4th index 8 > 4 => 5 > 4 => 3 > 4 ≠> stop Result: 

Step 5 :

 key = 2 //5th index 8 > 2 => 5 > 2 => 4 > 2 => 3 > 2 => 1 > 2 ≠> stop Result: 

The algorithm shown below is a slightly optimized version to avoid swapping the key element in every iteration., Hier zal het key element worden verwisseld aan het einde van de iteratie (step).

 InsertionSort(arr) for j = 1 to arr.length key = arr i = j - 1 while i > 0 and arr > key arr = arr i = i - 1 arr = key

Hier is een gedetailleerde implementatie in JavaScript:

function insertion_sort(A) { var len = array_length(A); var i = 1; while (i < len) { var x = A; var j = i - 1; while (j >= 0 && A > x) { A = A; j = j - 1; } A = x; i = i + 1; }}

een snelle implementatie in Swift wordt hieronder getoond:

Het Java-voorbeeld wordt hieronder getoond:

en in c….

void insertionSort(int arr, int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr; j = i-1; while (j >= 0 && arr > key) { arr = arr; j = j-1; } arr = key; } } 

eigenschappen:

Heapsort

Heapsort is een efficiënt sorteeralgoritme gebaseerd op het gebruik van MAX / min heaps., Een heap is een boom-gebaseerde datastructuur die voldoet aan de heap eigenschap – dat is voor een max heap, de sleutel van een knooppunt is kleiner dan of gelijk aan de sleutel van zijn ouder (als het een ouder heeft).

Deze eigenschap kan worden gebruikt om toegang te krijgen tot het maximum element in de heap in o(logn) tijd met behulp van de methode maxHeapify. We voeren deze bewerking n keer, elke keer verplaatsen van het maximale element in de heap naar de top van de heap en extraheren het uit de heap en in een gesorteerde array. Dus, na n iteraties zullen we een gesorteerde versie van de input array hebben.,

het algoritme is geen in-place algoritme en vereist dat eerst een heap – gegevensstructuur wordt geconstrueerd. Het algoritme is ook onstabiel, wat betekent dat bij het vergelijken van objecten met dezelfde sleutel, de oorspronkelijke volgorde niet zou worden bewaard.

dit algoritme draait in o(nlogn) tijd en O (1) extra ruimte omdat alle bewerkingen volledig op hun plaats worden uitgevoerd.

de beste, slechtste en gemiddelde casus tijd complexiteit van Heapsort is O (nlogn). Hoewel heapsort een betere slechter geval complexiteit dan quicksort heeft, een goed geà mplementeerde quicksort loopt sneller in de praktijk., Dit is een vergelijkingsgebaseerd algoritme, zodat het kan worden gebruikt voor niet-numerieke datasets voor zover een relatie (heap-eigenschap) kan worden gedefinieerd over de elementen.

een implementatie in Java is zoals hieronder getoond:

implementatie in C++

Radix Sorteer

vereisten: Het tellen van Sorteer

QuickSort, MergeSort en HeapSort zijn op vergelijking gebaseerde sorteeralgoritmen. Graafsort niet. Het heeft de complexiteit van O(n+k), waarbij k het maximale element van de input array is., Dus, als k O(n) is, wordt CountSort lineair Sorteren, wat beter is dan vergelijking gebaseerde sorteeralgoritmen die o(nlogn) tijdcomplexiteit hebben.

het idee is om het CountSort-algoritme uit te breiden om een betere tijdcomplexiteit te krijgen wanneer k gaat O(n2). Hier komt het idee van Radix soort.

het algoritme:

voor elk cijfer i waarbij i varieert van het minst significante cijfer tot het meest significante cijfer van een getal, Sorteer input array met behulp van countsort algoritme volgens het IDE cijfer. We gebruikten count sort omdat het een stabiele soort is.,

voorbeeld: Stel dat de invoer array is:

10, 21, 17, 34, 44, 11, 654, 123

Op basis van het algoritme Sorteren we de invoer array op basis van het cijfer van de ene (minst significante cijfer).

0: 10
1: 21 11
2:
3: 123
4: 34 44 654
5:
6:
7: 17
8:
9:

10, 21, 11, 123, 24, 44, 654, 17.

nu sorteren we volgens het getal van de ten:

0:
1: 10 11 17
2: 21 123
3: 34
4: 44
5: 654
6:
7:
8:
9:

nu wordt de array: 10, 11, 17, 21, 123, 34, 44, 654.,

tenslotte Sorteren we op het cijfer van de honderd (meest significante cijfer):

0: 010 011 017 021 034 044
1: 123
2:
3:
4:
5:
6: 654
7:
8:
9:

De array wordt : 10, 11, 17, 21, 34, 44, 123, 654 dat is geregeld. Zo werkt ons algoritme.

een implementatie in C:

selectie Sorteren

selectie sorteren is een van de eenvoudigste sorteeralgoritmen. Dit algoritme ontleent zijn naam aan de manier waarop het itereert door de array: het selecteert het huidige kleinste element, en wisselt het op zijn plaats.,

zo werkt het:

  1. zoek het kleinste element in de array en ruil het met het eerste element.
  2. zoek het tweede kleinste element en wissel met het tweede element in de array.
  3. zoek het derde kleinste element en ruil wit met het derde element in de array.
  4. herhaal het proces van het vinden van het volgende kleinste element en wissel het in de juiste positie totdat de gehele array gesorteerd is.

maar hoe zou u de code schrijven voor het vinden van de index van de op een na kleinste waarde in een array?,

een eenvoudige manier is om op te merken dat de kleinste waarde al is omgewisseld in index 0, dus het probleem vermindert tot het vinden van het kleinste element in de array beginnend bij index 1.

selectie sorteert altijd hetzelfde aantal sleutelvergelijkingen-N (N-1) / 2.

implementatie in C/C++

het volgende C++ programma bevat zowel een iteratieve als een recursieve implementatie van het selectie-sorteeralgoritme. Beide implementaties worden aangeroepen in de main() functie.,

Implementatie in JavaScript

Implementatie in Python

Implementatie in Java

Implementatie in MATLAB

Eigenschappen

  • Ruimte Complexiteit: O(n)
  • Tijd Complexiteit: O(n2)
  • Sorteren op Plaats: Ja
  • Stabiel: Geen

Bubble Sort

Net als de manier waarop gasbellen van de bodem van een glas, bubble sort is een eenvoudig algoritme dat sorteert een lijst, zodat ofwel een lagere of hogere waarden te drijven naar de top., Het algoritme doorkruist een lijst en vergelijkt aangrenzende waarden, door ze te ruilen als ze niet in de juiste volgorde staan.

met een worst-case complexiteit van O(n^2), is het sorteren van bubbels erg traag in vergelijking met andere sorteeralgoritmen zoals quicksort. Het voordeel is dat het een van de makkelijkste sorteeralgoritmen is om vanaf nul te begrijpen en te coderen.

vanuit technisch perspectief is bubble Sorteren redelijk voor het sorteren van kleine arrays of speciaal bij het uitvoeren van sorteeralgoritmen op computers met Opmerkelijk beperkte geheugenbronnen.,

eerste doorloop door de lijst:

tweede doorloop door de lijst:

de lijst is al gesorteerd, maar het bubble sorteeralgoritme realiseert dit niet. In plaats daarvan moet het een hele pas door de lijst voltooien zonder waarden te wisselen om te weten dat de lijst gesorteerd is.,

Third pass through the list:

  • =>
  • =>
  • =>
  • =>

Clearly bubble sort is far from the most efficient sorting algorithm. Still, it’s simple to wrap your head around and implement yourself.,

Properties

  • Space complexity: O(1)
  • Best case performance: O(n)
  • Average case performance: O(n*n)
  • Worst case performance: O(n*n)
  • Stable: Yes

Video Explanation

Bubble sort algorithm

Example in JavaScript

Example in Java.

Example in C++

Example in Swift

Example in Python

def bubbleSort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr > arr : arr, arr = arr, arr print(arr)

Example in PHP

Example in C

Quick Sort

Quick sort is an efficient divide and conquer sorting algorithm., Gemiddelde casus tijd complexiteit van snelle sortering is O(nlog(n)) met worst case tijd complexiteit is O (n^2) afhankelijk van de selectie van het pivot element, dat de huidige array verdeelt in twee sub arrays.

bijvoorbeeld, de tijdscomplexiteit van Quick Sort is ongeveer O(nlog(n)) wanneer de selectie van pivot de originele array verdeelt in twee subarrays van bijna gelijke grootte.,

aan de andere kant, als het algoritme, dat een pivot-element van de invoerarrays selecteert, consequent 2 subarrays uitvoert met een groot verschil in termen van arraysgroottes, kan het snelsorteeralgoritme de ongunstigste tijdscomplexiteit van O(n^2) bereiken.

de stappen die betrokken zijn bij snelle sortering zijn:

  • Kies een element dat als draaipunt dient, in dit geval is het laatste element van de array het draaipunt.
  • partitionering: Sorteer de array op zo ‘ n manier dat alle elementen minder dan de pivot naar links zijn, en alle elementen groter dan de pivot naar rechts.,
  • aanroep Quicksort recursief, rekening houdend met de vorige pivot om de linker en rechter arrays correct te verdelen.

voorbeeld implementaties in verschillende talen

implementatie in JavaScript:

implementatie in C

implementatie in Python3

implementatie in MATLAB

de complexiteit van snelle sortering is O(n) . Dit is een verbetering ten opzichte van andere verdeel en heers sorteeralgoritmen, die O(nlong(n)) ruimte nemen.,

snelle sortering bereikt dit door de volgorde van elementen binnen de gegeven array te veranderen. Vergelijk dit met het samenvoeg sorteeralgoritme dat 2 arrays maakt, elke lengte n/2, in elke functie aanroep.

Er bestaat echter wel het probleem dat dit sorteeralgoritme van tijd O(n*n) is als het draaipunt altijd in het midden wordt gehouden. Dit kan worden overcomed door gebruik te maken van een willekeurig pivot

complexiteit

de complexiteit van de ruimte bij snelle sortering is O(n)., Dit is een verbetering ten opzichte van andere verdeel en heers sorteeralgoritmen, die o(n log(n)) ruimte nemen.

Timsort

Timsort is een snel sorteeralgoritme dat werkt met een stabiele o(n log (N)) complexiteit.

Timsort is een mix van Invoegsort en Mergesort. Dit algoritme wordt geà mplementeerd in Java ‘ s Arrays.sort () evenals Python ‘ s sorted () en sort (). De kleinere delen worden gesorteerd met behulp van Insertion Sort en worden later samengevoegd met behulp van Mergesort.,

een snelle implementatie in Python:

complexiteit:

Tim sort heeft een stabiele complexiteit van o(n log(N)) en vergelijkt heel goed met Quicksort. Een vergelijking van complexiteit is te vinden op deze grafiek.

Merge Sort

Merge Sort is een verdeel en heers algoritme. Het verdeelt input array in twee helften, roept zichzelf op voor de twee helften en voegt dan de twee gesorteerde helften samen. Het belangrijkste deel van het algoritme krijgt twee gesorteerde arrays, en we moeten ze samenvoegen tot een enkele gesorteerde array., Het hele proces van het sorteren van een array van n gehele getallen kan worden samengevat in drie stappen-

  • verdeel de array in twee helften.
  • Sorteer de linkerhelft en de rechterhelft met hetzelfde terugkerende algoritme.
  • voeg de gesorteerde helften samen.

er is iets bekend als het Two Finger algoritme dat ons helpt twee gesorteerde arrays samen te voegen. Het gebruik van deze subroutine en het recursief aanroepen van de merge sort functie op de array helften geeft ons de uiteindelijke gesorteerde array waar we naar op zoek zijn.,

omdat dit een recursiegebaseerd algoritme is, hebben we er een herhalingsrelatie voor. Een herhalingsrelatie is gewoon een manier om een probleem in termen van zijn subproblemen weer te geven.

T(n) = 2 * T(n / 2) + O(n)

door het in gewoon Engels op te splitsen, splitsen we het subprobleem in twee delen bij elke stap en we hebben een lineaire hoeveelheid werk die we moeten doen voor het samenvoegen van de twee gesorteerde helften bij elke stap.

complexiteit

Het grootste voordeel van het gebruik van Merge sort is dat de tijdscomplexiteit alleen n*log(n) is om een hele Array te sorteren., Het is een stuk beter dan n^2 looptijd van bubble sort of insertion sort.

voordat we code schrijven, laten we begrijpen hoe merge sort werkt met behulp van een diagram.

eigenschappen:

  • complexiteit van de ruimte: O(n)
  • complexiteit van de tijd: o(n*log(n)). De tijdscomplexiteit voor het samenvoegen is misschien niet meteen duidelijk. De log (n) factor die binnenkomt is vanwege de recidief relatie die we eerder hebben genoemd.,
  • Sorteren op zijn plaats: Nee in een typische implementatie
  • stabiel: ja
  • Parallellizable: Ja (verschillende parallelle varianten worden besproken in de derde editie van Cormen, Leiserson, Rivest en Stein ‘ s Introduction to Algorithms.)

C++ implementatie

JavaScript implementatie

eerst controleren we de lengte van de array. Als het 1 is dan geven we gewoon de array terug. Dit zou onze basiszaak zijn. Anders zullen we de middelste waarde vinden en de array in twee helften verdelen. We zullen nu beide helften Sorteren met recursieve aanroepen naar MergeSort-functie.,

function merge (a,b) { var result = ; while (a.length >0 && b.length >0) result.push(a < b? a.shift() : b.shift()); return result.concat(a.length? a : b);}

wanneer we de twee helften samenvoegen, slaan we het resultaat op in een auxilliaire array. We zullen het startelement van de linker array vergelijken met het startelement van de rechter array. Welke minder is zal worden geduwd in de resultaten array en we zullen het verwijderen van daar respectievelijke arrays met behulp van; console.log (mergeSort (test));>>

een samenvoegen Sorteer YouTube-Tutorial

Hier is een goede YouTube-video die in detail door het onderwerp loopt.,

Implementaion in JS

implementatie in C

implementatie in C++

laten we array a = {2,5,7,8,9,12,13} en array B = {3,5,6,9,15} beschouwen en we willen array C ook in oplopende volgorde.

implementatie in Python

implementatie in Java

voorbeeld in Java

Written by 

Geef een reactie

Het e-mailadres wordt niet gepubliceerd. Vereiste velden zijn gemarkeerd met *