Hvad er en sorteringsalgoritme?

sorteringsalgoritmer er et sæt instruktioner, der tager et array eller en liste som input og arrangerer elementerne i en bestemt rækkefølge.

hvorfor sorteringsalgoritmer er vigtige

da sortering ofte kan reducere kompleksiteten af et problem, er det en vigtig algoritme inden for Datalogi. Disse algoritmer har direkte applikationer i søgealgoritmer, databasealgoritmer, opdele og erobre metoder, datastrukturalgoritmer og mange flere.,

afvejninger af algoritmer

Når du bruger forskellige algoritmer, skal der stilles nogle spørgsmål. Hvor stor sorteres samlingen? Hvor meget hukommelse er til rådighed, der skal bruges? Skal samlingen vokse?

svarene på disse spørgsmål kan bestemme, hvilken algoritme der vil fungere bedst for situationen. Nogle algoritmer som merge sort kan have brug for meget plads til at køre, mens indsættelsessorter ikke altid er den hurtigste, men det kræver ikke mange ressourcer at køre.,

Du skal bestemme, hvad kravene i systemet er og dets begrænsninger, før du beslutter, hvilken algoritme der skal bruges.

Nogle Fælles Sortering Algoritmer

Nogle af de mest almindelige sortering algoritmer er:

  • Valg Form
  • Boble Form
  • Isætning Form
  • Merge sort
  • Hurtig Form
  • Bunke Form
  • Tælle Form
  • Radix Form
  • Spand Form

Men før vi kommer ind i hver af disse, så lad os lære lidt mere om, hvad der gør klassificerer en sorterings-algoritme.,

Klassifikation af en Sorterings-Algoritme

Sorterings algoritmer kan være kategoriseret baseret på følgende parametre:

  1. Baseret på Antallet af Swaps eller Inversion Dette er antallet af gange algoritmen swaps elementer til at sortere input. Selection Sort kræver det mindste antal s .aps.
  2. baseret på antallet af sammenligninger dette er antallet af gange algoritmen sammenligner elementer for at sortere input., Ved hjælp af Store-O-notation, sorterings-algoritme eksempler, der er anført ovenfor kræves, at mindst O(nlogn) sammenligninger (i bedste fald) og O(n^2) sammenligninger i værste fald for de fleste af resultaterne.
  3. baseret på rekursion eller ikke-rekursion nogle sorteringsalgoritmer, såsom Quick Sort , skal du bruge rekursive teknikker til at sortere input. Andre sorteringsalgoritmer, såsom Selection Sort eller Insertion Sort , bruger ikke-rekursive teknikker., Endelig gør nogle sorteringsalgoritmer, såsom Merge Sort, brug af både rekursive såvel som ikke-rekursive teknikker til at sortere input.
  4. baseret på Stabilitetssorteringsalgoritmer siges at være stable, hvis algoritmen opretholder den relative rækkefølge af elementer med lige nøgler. Med andre ord forbliver to ækvivalente elementer i samme rækkefølge i det sorterede output, 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 kan flytte elementer omkring pivot og faktisk ikke bruge en separat array, som er IKKE tilfældet i merge sort, hvor størrelsen af input skal være afsat på forhånd at gemme output i løbet af den slags.
  9. Merge Sort er et eksempel på out place sorter, da det kræver ekstra hukommelsesplads til dets operationer.,

bedst mulig tidskompleksitet for enhver sammenligningsbaseret sortering

enhver sammenligningsbaseret sorteringsalgoritme skal mindst foretage nlog2n-sammenligninger for at sortere inputarrayet, og Heapsort og merge sorter er asymptotisk optimale sammenligningssorter. Dette kan let bevises ved at tegne et beslutningstrædiagram.

Bucket Sort

Bucket Sort er en sammenligningssorteringsalgoritme, der fungerer på elementer ved at opdele dem i forskellige spande og derefter sortere disse spande individuelt., Hver spand sorteres individuelt ved hjælp af en separat sorteringsalgoritme eller ved at anvende skovlsorteringsalgoritmen rekursivt.

Bucket Sort er primært nyttigt, når input er ensartet fordelt over en rækkevidde.

Antag, at du har følgende problem foran dig

du har fået et stort udvalg af flydende heltal, der ligger ensartet mellem den nedre og øvre grænse. Denne Matri.skal nu sorteres.

en enkel måde at løse dette problem på ville være at bruge en anden sorteringsalgoritme, såsom Merge sort, Heap Sort eller Quickuick Sort., Disse algoritmer garanterer dog en Best case-tidskompleksitet af O (NlogN). Men ved hjælp af spand sortering, kan ovenstående opgave være afsluttet i O(N)tid.

lad os se nærmere på det.

overvej at du skal oprette en række lister, det vil sige spande. Elementer skal nu indsættes i disse spande på grundlag af deres egenskaber. Hver af disse spande kan derefter sorteres individuelt ved hjælp af Indsætningssortering.,

pseudokode til Bucket Sort:

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

Tællesortering

Tællesortering er en sorteringsteknik baseret på taster mellem et specifikt interval. Det virker ved at tælle antallet af objekter, der har forskellige nøgleværdier (slags hashing). Derefter gør nogle aritmetiske at beregne placeringen af 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. 

Egenskaber

Implementering er i JavaScript

C++ Gennemførelsen

Hurtig Gennemførelse

Isætning Sortere

Isætning form er en simpel sortering algoritme, der for et lille antal af elementer.

eksempel:

i indsættelses sortering sammenligner du key elementet med de foregående elementer. Hvis de foregående elementer er større end key – elementet, flytter du det forrige element til næste position.

Start fra indeks 1 til størrelsen af input 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., Her byttes elementet key i slutningen af iterationen (trin).

 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 detaljeret gennemførelse 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 hurtig gennemførelse i Swift er vist nedenfor:

Java eksempel er vist nedenfor:

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

Egenskaber:

Heapsort

Heapsort er en effektiv sortering algoritme baseret på brug af max/min dynger., En bunke er en træbaseret datastruktur, der tilfredsstiller heap-egenskaben – det vil sige for en ma. – bunke, nøglen til enhver knude er mindre end eller lig med nøglen til dens forælder (hvis den har en forælder).

denne egenskab kan udnyttes til at få adgang til det maksimale element i heapen I O(logn) tid ved hjælp af Ma .heapify-metoden. Vi udfører denne operation n gange, hver gang vi flytter det maksimale element i bunken til toppen af bunken og udtrækker det fra bunken og ind i et sorteret array. Således vil vi efter n iterationer have en sorteret version af inputarrayet.,

algoritmen er ikke en in-place algoritme og ville kræve en bunke datastruktur skal konstrueres først. Algoritmen er også ustabil, hvilket betyder, at når man sammenligner objekter med samme nøgle, vil den oprindelige bestilling ikke blive bevaret.

denne algoritme kører i O(nlogn) tid og O(1) ekstra plads, da alle operationer udføres helt på plads.

den bedste, værste og gennemsnitlige sagstidskompleksitet af Heapsort er O(nlogn). Selvom heapsort har en bedre dårligere kompleksitet end quickuicksort, kører en velimplementeret quickuicksort hurtigere i praksis., Dette er en sammenligningsbaseret algoritme, så den kan bruges til ikke-numeriske datasæt, for så vidt som noget forhold (heapegenskab) kan defineres over elementerne.

En implementation i Java er som vist nedenfor :

Implementering i C++

Radix Sortering

Forudsætning: at Tælle Sortere

QuickSort, MergeSort, og HeapSort sammenligning er baseret på sortering af algoritmer. CountSort er ikke. Det har kompleksiteten af O (N+k), hvor k er det maksimale element i inputarrayet., Så hvis k er O(n), bliver CountSort lineær sortering, hvilket er bedre end sammenligningsbaserede sorteringsalgoritmer, der har O(nlogn) tidskompleksitet.

ideen er at udvide CountSort-algoritmen for at få en bedre tidskompleksitet, når k går O(n2). Her kommer ideen om Radi.Sort.

algoritmen:

for hvert ciffer i, hvor jeg varierer fra det mindst signifikante ciffer til det mest signifikante ciffer i et tal, skal du sortere inputarray ved hjælp af countsort-algoritme i henhold til ith-ciffer. Vi brugte count sort, fordi det er en stabil sort.,eksempel: Antag, at inputarrayet er:

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

baseret på algoritmen sorterer vi inputarrayet i henhold til ens ciffer (mindst signifikant ciffer).

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

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

Nu, vi vil sortere i henhold til den ti ‘ s ciffer:

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

Nu, array bliver : 10, 11, 17, 21, 123, 34, 44, 654.,

Endelig, vi sortere i henhold til de hundrede s ciffer (mest betydende ciffer):

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

array bliver : 10, 11, 17, 21, 34, 44, 123, 654 der er sorteret. Sådan fungerer vores algoritme.

en implementering i C:

Selection Sort

Selection Sort er en af de enkleste sorteringsalgoritmer. Denne algoritme får sit navn fra den måde, den gentager gennem arrayet: den vælger det nuværende mindste element og bytter det på plads.,

Sådan fungerer det:

  1. Find det mindste element i arrayet, og skift det med det første element.
  2. Find det andet mindste element og skift med med det andet element i arrayet.
  3. Find det tredje mindste element og byt med det tredje element i arrayet.
  4. gentag processen med at finde det næste mindste element og bytte det til den rigtige position, indtil hele arrayet er sorteret.

men hvordan ville du skrive koden for at finde indekset for den næstmindste værdi i en Matri??,

en nem måde er at bemærke, at den mindste værdi allerede er byttet til indeks 0, så problemet reduceres til at finde det mindste element i arrayet, der starter ved indeks 1.

Selection sort altid tager det samme antal centrale sammenligninger — N(N − 1) / 2.

implementering i C/C++

følgende C++ – program indeholder en iterativ såvel som en rekursiv implementering af Udvælgelsessorteringsalgoritmen. Begge implementeringer påberåbes i funktionen main().,

Implementering er i JavaScript

Gennemførelse i Python

Implementeringen i Java

Implementering i MATLAB

Egenskaber

  • Plads Kompleksitet: O(n)
  • tidskompleksitet O(n2)
  • Sortering af Sted i: Ja
  • Stabil: Ingen

Boble Sortere

ligesom boblerne til at stige fra bunden af et glas, boble form er en simpel algoritme, der sorterer en liste, så enten lavere eller højere værdier til at boble op til toppen., Algoritmen krydser en liste og sammenligner tilstødende værdier, bytte dem, hvis de ikke er i den rigtige rækkefølge.

med en complexityorst-case kompleksitet af O(n^2) er bubble sort meget langsom sammenlignet med andre sorteringsalgoritmer som quickuicksort. Fordelen er, at det er en af de nemmeste sorteringsalgoritmer at forstå og kode fra bunden. fra teknisk perspektiv er bubble sort rimelig til sortering af små arrays eller specielt ved udførelse af sorteringsalgoritmer på computere med bemærkelsesværdigt begrænsede hukommelsesressourcer.,

først passere gennem listen:

andet passere gennem listen:

listen er allerede sorteret, men bubble sort algoritmen er ikke klar over dette. Det skal snarere udfylde et helt pass gennem listen uden at bytte nogen værdier for at vide, at listen er sorteret.,

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., Gennemsnitlige fald tid kompleksitet Hurtig Slags er O(nlog(n)) med værst tænkelige tidspunkt kompleksiteten bliver O(n^2), afhængig af valg af pivot element, der dividerer den aktuelle array i to sub-arrays.

For eksempel, den tid, kompleksitet Hurtig Slags er omtrent O(nlog(n)), når udvælgelsen af pivot deler oprindelige array i to næsten lige store sub-arrays.,

På den anden side, hvis den algoritme, som vælger af pivot element i input arrays, konsekvent udgange 2 sub arrays med en stor forskel i form af array størrelser, hurtig slags algoritme kan opnå værste tilfælde tidskompleksitet O(n^2).

de trin, der er involveret i hurtig sortering, er:

  • Vælg et element, der skal fungere som en pivot, i dette tilfælde er det sidste element i arrayet pivot.partitionering: Sorter arrayet på en sådan måde, at alle elementer, der er mindre end pivoten, er til venstre, og alle elementer, der er større end pivoten, er til højre.,
  • Ring Quickuicksort rekursivt under hensyntagen til den forrige pivot for korrekt at opdele venstre og højre arrays. (En mere detaljeret beskrivelse findes i kommentarerne nedenfor)

Eksempel Implementeringer i Forskellige Sprog

Implementering er i JavaScript:

Implementering i C

Gennemførelse i Python3

Implementering i MATLAB

Den plads kompleksitet hurtig slags er O(n) . Dette er en forbedring i forhold til andre divide and con .uer sorteringsalgoritmer, der tager O(nlong(n)) mellemrum.,

hurtig sortering opnår dette ved at ændre rækkefølgen af elementer inden for det givne array. Sammenlign dette med merge sorteringsalgoritmen, der opretter 2 arrays, hver længde n/2, i hvert funktionskald.

Der findes dog problemet med, at denne sorteringsalgoritme er af tid O(n*n) hvis pivoten altid holdes i midten. Dette kan overvindes ved at bruge en tilfældig pivot

kompleksitet

rumkompleksiteten af quickuick sort er o(n)., Dette er en forbedring i forhold til andre divide and con .uer sorteringsalgoritmer, som tager o(n log(n)) plads.

Timsort

Timsort er en hurtig sorteringsalgoritme, der arbejder med stabil o(N log(n)) kompleksitet.

Timsort er en blanding af indsættelse Sort og Mergesort. Denne algoritme er implementeret i Javas Arrays.sortere () samt Python sorteret () og sortere (). De mindre dele sorteres ved hjælp af Indsætningssortering og slås senere sammen ved hjælp af Mergesort.,

En hurtig gennemførelse i Python:

Kompleksitet:

Tim form har en stabil Kompleksitet på O(N log(N)) og sammenligner rigtig godt med Quicksort. En sammenligning af kompleksiteter kan findes på dette diagram.

Flet Sort

Flet Sort er en kløft og erobre algoritme. Det deler input array i to halvdele, kalder sig selv for de to halvdele og fusionerer derefter de to sorterede halvdele. Den største del af algoritmen er givet to sorterede arrays, og vi er nødt til at flette dem ind i en enkelt sorteret array., Hele processen med at sortere en række N-heltal kan opsummeres i tre trin-

  • Opdel arrayet i to halvdele.Sorter den venstre halvdel og den højre halvdel ved hjælp af den samme tilbagevendende algoritme.
  • Flet de sorterede halvdele.

Der er noget kendt som T .o Finger algoritmen, der hjælper os med at flette to sorterede arrays sammen. Brug af denne subrutine og kalde Flet sorteringsfunktionen på arrayhalvdelene rekursivt vil give os det endelige sorterede array, vi leder efter.,

da dette er en rekursionsbaseret algoritme, har vi en gentagelsesrelation for den. En gentagelsesrelation er simpelthen en måde at repræsentere et problem med hensyn til dets delproblemer.

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

Når vi sætter det på almindeligt engelsk, nedbryder vi underproblemet i to dele ved hvert trin, og vi har en vis lineær mængde arbejde, som vi skal gøre for at slå de to sorterede halvdele sammen ved hvert trin.

kompleksitet

den største fordel ved at bruge Merge sort er, at tidskompleksiteten kun er n*log(n) for at sortere et helt Array., Det er meget bedre end n^2 køretid for boble sortering eller indsættelse sort.

før vi skriver kode, lad os forstå, hvordan merge sort fungerer ved hjælp af et diagram.

Egenskaber:

  • Plads Kompleksitet: O(n)
  • tidskompleksitet O(n*log(n)). Tidskompleksiteten for Fusionssorten er måske ikke indlysende fra første øjekast. Log (n) faktor, der kommer i er på grund af gentagelse forhold, vi har nævnt før.,
  • Sortering På Plads: Nej i en typisk gennemførelsen
  • Stabil: Ja
  • Parallelizable :ja (Flere parallelle varianter er beskrevet i den tredje udgave af Cormen, Leiserson, Rivest og Stein ‘ s Introduktion til Algoritmer.)

C++ implementering

JavaScript implementering

først kontrollerer vi længden af arrayet. Hvis det er 1, returnerer vi simpelthen arrayet. Dette ville være vores base sag. Ellers vil vi finde ud af den midterste værdi og opdele arrayet i to halvdele. Vi vil nu sortere begge halvdele med rekursive opkald til MergeSort-funktion.,

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 fusionerer de to halvdele, gemmer vi resultatet i et hjælpearray. Vi sammenligner startelementet i venstre array med startelementet i højre array. Alt efter hvad der er mindre, vil blive skubbet ind i resultatarrayet, og vi vil fjerne det derfra respektive arrays ved hjælp af; konsol.log(mergeSort(test));>>

Merge sort YouTube Tutorial

Her er en god YouTube-video, der går gennem den emne i detaljer.,

Implementeringen i JS

Implementering i C

Implementering i C++

Lad os overveje array A = {2,5,7,8,9,12,13} og array B = {3,5,6,9,15}, og vi ønsker array C for at være i opstigende rækkefølge, som godt.

implementering i Python

implementering i Java

eksempel i Java

Written by 

Skriv et svar

Din e-mailadresse vil ikke blive publiceret. Krævede felter er markeret med *