Hva er en Sortering Algoritme?

Sorterings-algoritmer er et sett av instruksjoner som tar en matrise eller en liste som en inngang til og organiserer elementene i en bestemt rekkefølge.

Hvorfor Sorterings-Algoritmer er Viktig

Siden sortering kan ofte redusere kompleksiteten av et problem, det er en viktig algoritme i informatikk. Disse algoritmene har direkte programmer i å søke algoritmer, database algoritmer, splitt og hersk-metoder, data struktur algoritmer, og mange flere.,

Trade-Offs av Algoritmer

Når du bruker ulike algoritmer noen spørsmål stilles. Hvor stor er den i samlingen er sortert? Hvor mye minne som er til disposisjon for å bli brukt? Gjør samlingen trenger for å vokse?

svarene På disse spørsmålene kan bestemme hva algoritme kommer til å fungere best for situasjonen. Noen algoritmer som fusjonere kan sortere trenger mye plass til å kjøre, mens innsetting sorter er ikke alltid den raskeste, men det krever ikke mange ressurser til å kjøre.,

Du bør finne ut hva som trengs av systemet og dets begrensninger før du bestemmer deg for hva algoritmen for å bruke.

Noen Vanlige Sorterings-Algoritmer

Noen av de vanligste sorterings-algoritmer er:

  • Sorter Utvalget
  • Boble Sortere
  • Innsetting Sortere
  • slå sammen Sortere
  • Rask Sortere
  • Heap Sortere
  • Telle Sortere
  • Radix Sortere
  • Bøtte Sortere

Men før vi kommer inn på hver av disse, la oss lære litt mer om hva som gjør klassifiserer en sortering algoritme.,

Klassifisering av en Sortering Algoritme

Sorterings-algoritmer kan kategoriseres basert på følgende parametre:

  1. Basert på Antall Bytteavtaler eller Vending Dette er antall ganger algoritmen bytteavtaler elementer for å sortere inngang. Selection Sort krever minimum antall bytteavtaler.
  2. Basert på Antall Sammenligninger Dette er antall ganger algoritmen sammenligner elementer for å sortere inngang., Ved hjelp av Big-O notasjon, sortering algoritme eksempler er nevnt ovenfor, krever minst O(nlogn) sammenligninger i beste fall og O(n^2) sammenligninger i verste fall for de fleste av utgangene.
  3. Basert på Recursion eller Ikke-Recursion Noen sorterings-algoritmer, slik som Quick Sort bruk rekursiv teknikker for å sortere inngang. Andre sorterings-algoritmer, slik som Selection Sort eller Insertion Sort , bruke ikke-rekursive teknikker., Til slutt, noen sortering algoritme, som for eksempel Merge Sort , gjøre bruk av både rekursiv så vel som ikke-rekursive teknikker for å sortere inngang.
  4. Basert på Stabilitet Sorterings-algoritmer er sagt å være stable hvis algoritmen opprettholder den relative rekkefølge av elementer med lik tastene. Med andre ord, to tilsvarende elementer forblir i samme rekkefølge sortert ut som de var i 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 og Quick-sort er in place sorter som vi flytte elementer rundt pivot og ikke faktisk bruk et eget utvalg som IKKE er tilfelle i fusjonere sorter der størrelsen på input må være tildelt på forhånd for å lagre utdataene under sorteringen.
  9. Merge Sort er et eksempel på out place sorter som det krever ekstra plass i minnet for sin virksomhet.,

Best mulig tid kompleksitet for enhver sammenlikning basert sortering

Enhver sammenlikning basert sortering algoritmen må gjøre minst nLog2n sammenligninger for å sortere inngang utvalg, og Heapsort og flette sorter er asymptotically optimal sammenligningen slag. Dette kan være lett vist seg ved å tegne en beslutning treet diagrammet.

Bøtte Sortere

Bøtte Sorter er en sammenligning sortere algoritme som opererer på elementer ved å dele dem inn i ulike bøtter og deretter sortere disse bøtter individuelt., Hver bøtte er sortert individuelt ved hjelp av en separat sortering algoritme eller ved å bruke bøtte sortere algoritme med undermapper.

Bøtte Sorter er hovedsakelig nyttig når input er jevnt fordelt over et område.

Anta at du har følgende problem i front av deg

Du har fått et stort utvalg av floating point heltall lå jevnt mellom nedre og øvre grense. Denne tabellen må nå være sortert.

En enkel måte å løse dette problemet ville være å bruke en annen sortering algoritme for eksempel slå sammen sortere, Haugen Sortere eller Hurtig på Sorter., Imidlertid, disse algoritmene garantere en beste fall tid kompleksitet O(NlogN). Imidlertid, ved hjelp av bøtte sortere, ovenfor oppgaven kan være ferdig i O(N)tid.

La oss ta en nærmere titt på det.

Tenk på at du må opprette en rekke lister, som er av bøtter. Elementer trenger nå å bli satt inn i disse kategoriene, på grunnlag av deres egenskaper. Hver av disse kategoriene, kan så sorteres hver for seg ved bruk Innsetting Sorter.,

Pseudo-Kode for Spann Form:

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

Telle Sortere

Telle sortering sortering er en teknikk basert på tastene mellom et bestemt område. Det fungerer ved å telle antall objekter å ha forskjellige viktige verdier (type nummerering). Deretter gjøre noen aritmetiske til å beregne posisjonen for hvert objekt i output-sekvens.,

Eksempel:

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. 

Egenskaper

Implementering i JavaScript

C++ – Implementering

Rask Implementering

Innsetting Sortere

Innsetting sorter er en enkel sortering algoritme for et lite antall elementer.

Eksempel:

I Innsetting sortere, sammenligne key – element med den forrige elementer. Hvis den forrige elementer er større enn key – element, så kan du flytte den forrige element til neste posisjon.

Start fra indeks 1 til størrelsen på input-tabellen.,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., Her key – element vil bli byttet på slutten av iterasjonen (trinn).

 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

Her er en detaljert gjennomføring i 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; }}

En rask implementering i Swift er vist nedenfor:

Java eksempel er vist nedenfor:

i 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; } } 

Egenskaper:

Heapsort

Heapsort er en effektiv sortering algoritme basert på bruk av maks/min hauger., En heap er et tre-baserte data-struktur som tilfredsstiller haugen eiendom – som er for en maks haugen, nøkkelen til enhver node er mindre enn eller lik nøkkelen til sine foreldre (hvis den har en forelder).

Denne egenskapen kan utnyttes til å få tilgang til det maksimale elementet i haugen i O(logn) tid ved hjelp av maxHeapify metode. Vi utfører denne operasjonen n ganger, og hver gang du flytter den maksimale elementet i haugen til toppen av haugen og trekke det fra haugen og inn i et sortert array. Dermed, etter n iterasjoner vi vil ha en sortert versjon av input-tabellen.,

algoritmen er ikke en algoritme, og ville kreve en haug data struktur skal bygges først. Algoritmen er også ustabilt, noe som betyr at når man sammenligner objekter med samme tast, vil den opprinnelige bestilling vil ikke bli bevart.

Denne algoritmen kjører i O(nlogn) tid og O(1) ekstra plass siden alle operasjoner er utført helt på plass.

Den beste, største og gjennomsnittlige tilfelle tid kompleksiteten av Heapsort er O(nlogn). Selv om heapsort har en bedre verre-sak kompleksitet enn quicksort, en godt gjennomført quicksort går raskere i praksis., Dette er en sammenligning-basert algoritme, slik at den kan brukes til ikke-numeriske data sett i den grad noen relasjon (heap eiendom), kan være definert over elementene.

En implementering i Java er som vist nedenfor :

implementert i C++

Radix Sortere

Forutsetning: Telling Sortere

QuickSort, MergeSort, og HeapSort er sammenligningen-basert sorterings-algoritmer. CountSort er det ikke. Det har kompleksitet O(n+k), der k er den maksimale elementet av input-tabellen., Så, hvis k er O(n), CountSort blir lineær sortering, som er bedre enn sammenligningen basert sorterings-algoritmer som har O(nlogn) tid kompleksitet.

ideen er å utvide CountSort algoritmen for å få en bedre tid kompleksitet når k går O(n2). Her kommer ideen om Radix Sorter.

Algoritmen:

For hvert siffer jeg der jeg varierer fra de minst signifikante sifferet til de mest signifikante sifferet i et tall, sortere input-tabellen ved hjelp countsort algoritme i henhold til ed siffer. Vi brukte telle, sortere, fordi det er en stabil form.,

Eksempel: Anta at input-tabellen er:

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

Basert på algoritme, vil vi sortere inngang utvalg i henhold til ens siffer (minst signifikante sifre).

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

Så, matrisen blir 10, 21, 11, 123, 24, 44, 654, 17.

Nå, vil vi sortere i henhold til de ti ‘ s siffer:

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

Nå, matrisen blir : 10, 11, 17, 21, 123, 34, 44, 654.,

til Slutt, vi sortere i henhold til hundre er sifferet (mest signifikante siffer):

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

array blir : 10, 11, 17, 21, 34, 44, 123, 654 som er sortert. Dette er hvordan algoritmen fungerer.

En implementering i C:

Sorter Utvalget

Sorter Utvalget er en av de enkleste sorterings-algoritmer. Denne algoritmen har fått navnet sitt fra den måten den koden gjennom matrisen: det velger gjeldende minste element, og bytteavtaler det på plass.,

Her er hvordan det fungerer:

  1. Finn den minste elementet i matrisen og bytte det med det første elementet.
  2. Finn den nest minste element, og bytte med med det andre elementet i tabellen.
  3. Finn den tredje minste elementet og bytte vidd med det tredje elementet i tabellen.
  4. Gjenta prosessen med å finne den nest minste element og bytte det inn i riktig posisjon til hele tabellen er sortert.

Men, hvordan ville du skrive koden for å finne indeksen for den nest minste verdien i en tabell?,

En enkel måte er å legge merke til at den minste verdien har allerede blitt byttet inn i indeks 0, slik at problemet reduseres ved å finne den minste elementet i matrisen starter på indeks 1.

sorter Utvalget tar alltid samme antall viktige sammenligninger — N(N − 1)/2.

Implementering i C/C++

følgende C++ – program inneholder en iterativ samt en rekursiv gjennomføring av Utvalget Sortere algoritme. Både implementeringer er brukt i main() funksjon.,

Implementering i JavaScript

Implementering i Python

Implementasjon i Java

Implementering i MATLAB

Egenskaper

  • Plass Kompleksitet: O(n)
  • Tid Kompleksitet: O(n2)
  • Sortering på Plass: Ja
  • Stabil: Nei

Boble Sortere

Akkurat som den måten boblene stiger opp fra bunnen av et glass, boble-sortering er en enkel algoritme som sorterer en liste, slik at enten lavere eller høyere verdier til å boble opp til toppen., Algoritmen går gjennom en liste, og sammenligner tilstøtende verdier, bytte dem hvis de er ikke i riktig rekkefølge.

Med en verste-tilfelle kompleksitet O(n^2), boble-sortering er veldig treg i forhold til andre sorterings-algoritmer som quicksort. Oppsiden er at det er en av de enkleste sorterings-algoritmer for å forstå og kode fra bunnen av.

Fra teknisk perspektiv, boble-sortering er rimelig for sortering av små-sized matriser eller spesielt ved kjøring sortere algoritmer på datamaskiner med bemerkelsesverdig begrenset minne ressurser.,

Først passere gjennom listen:

Andre passere gjennom listen:

listen er allerede sortert, men boblen sortere algoritmen er ikke klar over dette. Snarere er det behov for å fullføre en hel passere gjennom listen uten å bytte noen verdier å vite listen er sortert.,

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., Gjennomsnittlig tilfelle tid kompleksiteten av Rask Sortering er O(nlog(n)) med verste fall tid kompleksitet blir O(n^2) avhengig av valg av pivot-element, som deler den gjeldende matrisen inn i to undergrupper-matriser.

For eksempel, den tid kompleksiteten av Rask Sortering er ca O(nlog(n)) når det utvalget av pivot deler opprinnelige matrisen inn i to nesten like store sub-matriser.,

På den annen side, hvis algoritmen, som velger av pivot-element av input-matriser, konsekvent utganger 2 sub-matriser med en stor forskjell i form av matrise størrelser, rask sortere algoritmen kan oppnå verste fall tid kompleksitet O(n^2).

trinnene som er involvert i Rask typen er:

  • Velg et element for å tjene som en pivot, i dette tilfellet, det siste elementet i matrisen er pivot.
  • Partisjonering: Sortere tabellen på en slik måte at alle elementer som er mindre enn pivot er til venstre, og alle elementer som er større enn pivot er til høyre.,
  • Anrop Quicksort undermapper, som tar hensyn til den forrige pivot riktig å dele venstre og høyre matriser. (En mer detaljert forklaring kan være funnet i kommentarfeltet nedenfor)

Eksempel Implementeringer i Ulike Språk

Implementering i JavaScript:

Implementering i C

Implementering i Python3

Implementering i MATLAB

plassen kompleksiteten av rask sortering er O(n) . Dette er en forbedring i forhold til andre splitt og hersk sorterings-algoritmer, som tar O(nlong(n)) plass.,

Rask sortere oppnår dette ved å endre rekkefølgen på elementer i en gitt matrise. Sammenlign dette med flette sortere algoritmen som lager 2-matriser, hver lengde n/2, i hver funksjon samtale.

Men det eksisterer problemet med denne sorteringen algoritme blir tid O(n*n) hvis pivot er alltid holdt på midten. Dette kan være overcomed ved å benytte en tilfeldig pivot

Kompleksitet

plassen kompleksiteten av rask sortering er O(n)., Dette er en forbedring i forhold til andre splitt og hersk sorterings-algoritmer, som tar O(n log(n)) plass.

Timsort

Timsort er en rask sortering algoritmen arbeider på et stabilt O(N log(N)) kompleksitet.

Timsort er en blanding av Innsetting Sortere og Mergesort. Denne algoritmen er implementert i Java-s-Matriser.sorter() samt Python er sortert() og sorter(). De mindre delene er sortert ved hjelp av Innsetting Sortere og er senere slått sammen med Mergesort.,

En rask implementering i Python:

Kompleksitet:

Tim sortere har en stabil Kompleksitet O(N log(N)), og sammenligner veldig godt med Quicksort. En sammenligning av kompleksiteten kan bli funnet på dette diagrammet.

slå sammen Sortere

slå sammen Sortering er en splitt og Hersk-algoritmen. Den deler inngang utvalg i to halvdeler, og kaller seg selv for de to halvdelene og deretter fusjonerer de to sortert halvdeler. Den største delen av algoritmen er gitt to sortert matriser, og vi er nødt til å flette dem inn i en enkelt sortert array., Hele prosessen med å sortere en array av N heltall kan oppsummeres i tre trinn-

– >

  • Dele utvalg i to halvdeler.
  • Sorter venstre side og høyre halvdel bruke samme tilbakevendende algoritme.
  • slå sammen sortert halvdeler.

Det er noe som er kjent som To Finger Algoritme som hjelper oss med å slå sammen to sortert matriser sammen. Ved hjelp av denne subrutinen og telefoni merge sortere funksjon på tabellen halvdeler med undermapper vil gi oss det endelige sortert array vi er ute etter.,

Siden dette er en recursion basert algoritme, vi har en gjentakelse forhold for det. En gjentakelse forhold er rett og slett en måte å representere et problem i forhold til sin subproblems.

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

Sette i vanlig engelsk, vi kan bryte ned subproblem i to deler på alle trinn, og vi har noen lineær mengden av arbeid som vi må gjøre for å slå sammen de to sortert halvdelene sammen på hvert trinn.

Kompleksitet

Den største fordelen med å bruke Flett sorter er at tiden kompleksitet er bare n*log(n) sorterer en hel Tabell., Det er mye bedre enn n^2 kjører tiden av boble sortere eller innsetting sorter.

Før vi skrive kode, la oss forstå hvordan slå sammen sortere fungerer ved hjelp av et diagram.

Egenskaper:

  • Plass Kompleksitet: O(n)
  • Tid Kompleksitet: O(n*log(n)). Tiden kompleksitet for Fusjonere Sorter kan ikke være opplagt fra første øyekast. Log(n) faktor som kommer i er på grunn av gjentakelse forhold vi har nevnt før.,
  • Sortering På Plass: Ingen i en typisk gjennomføring
  • Stabil: Ja
  • Parallelizable :ja (Flere parallelle varianter er diskutert i den tredje utgaven av Cormen, Leiserson, Rivest, og steins Introduksjon til Algoritmer.)

C++ – Implementering

JavaScript-Implementering

vi Først sjekke lengden på tabellen. Hvis det er 1 så vi bare returnere tabellen. Dette vil være vår base case. Annet, vil vi finne ut det midtre verdi og dele utvalg i to halvdeler. Vi vil nå sortere begge halvdelene med rekursive anrop til MergeSort funksjon.,

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);}

Når vi slå sammen de to halfs, vi lagrer resultatet i en teknisk utvalg. Vi vil sammenligne starter element av venstre utvalg til å starte element av høyre-matrise. Avhengig av hva som er mindre vil bli presset inn i resultat-tabellen, og vi vil fjerne den fra det respektive arrays med ; – konsollen.logg(mergeSort(test));>>

Merge Sortere YouTube Opplæringen

Her er en god YouTube-video som går gjennom temaet i detalj.,

Implementaion i JS

Implementering i C

implementert i C++

La oss se på matrisen A = {2,5,7,8,9,12,13} og matrisen B = {3,5,6,9,15} og vi vil matrisen C å være i stigende rekkefølge, så vel.

Implementering i Python

Implementasjon i Java

Eksempel i Java

Written by 

Legg igjen en kommentar

Din e-postadresse vil ikke bli publisert. Obligatoriske felt er merket med *