GeeksforGeeks

I den här artikeln kommer vi att diskutera viktiga egenskaper hos olika sorteringstekniker, inklusive deras komplexitet, stabilitet och minnesbegränsningar. Innan du förstår den här artikeln bör du förstå grunderna för olika sorteringstekniker (se : Sorteringstekniker).

Tidskomplexitetsanalys –
Vi har diskuterat den bästa, genomsnittliga och värsta komplexiteten för olika sorteringstekniker med möjliga scenarier.

Sortering baserad på jämförelse –
I jämförelsebaserad sortering jämförs elementen i en matris med varandra för att hitta den sorterade matrisen.

• Bubble sort och Insertion sort –
  Genomsnittlig och värsta tidskomplexitet: n^2
  Bästa tidskomplexitet: n när matrisen redan är sorterad.
  Sämsta fall: när matrisen är omvänt sorterad.
• Selektionssortering –
  Bäst, genomsnittlig och värsta fall tidskomplexitet: n^2 vilket är oberoende av datafördelningen.
• Merge sort –
  Bästa, genomsnittliga och värsta fallets tidskomplexitet: nlogn som är oberoende av datafördelningen.
• Heap sort –
  Bästa, genomsnittliga och värsta fallets tidskomplexitet: nlogn som är oberoende av datafördelningen.
• Snabbsortering –
  Det är en del och härska-strategi med återfallsrelation:

   T(n) = T(k) + T(n-k-1) + cn

  Sämsta fall: När matrisen är sorterad eller omvänt sorterad delar partitionsalgoritmen upp matrisen i två delmatriser med 0 och n-1 element. Därför

  T(n) = T(0) + T(n-1) + cnSolving this we get, T(n) = O(n^2)

  Bästa fall och genomsnittligt fall: I genomsnitt delar partitionsalgoritmen upp matrisen i två delmatriser med samma storlek. Därför,

  T(n) = 2T(n/2) + cnSolving this we get, T(n) = O(nlogn)

Non-comparison based sorting –
I non-comparison based sorting, elements of array are not compared with each other to find the sorted array.

• Radix-sortering –
  Bästa, genomsnittliga och värsta tidskomplexitet: nk där k är det maximala antalet siffror i arrayens element.
• Count-sortering –
  Bästa, genomsnittliga och värsta tidskomplexitet: n+k där k är storleken på count array.
• Bucket sort –
  Bästa och genomsnittliga tidskomplexitet: n+k där k är antalet hinkar.
  Svärsta fallets tidskomplexitet: n^2 om alla element tillhör samma hink.

In-place/Outplace-teknik –
En sorteringsteknik är inplace om den inte använder något extra minne för att sortera matrisen.
Av de jämförelserelaterade tekniker som diskuteras är det bara sammanslagningssortering som är en outplace-teknik eftersom den kräver en extra matris för att slå samman de sorterade undermatriserna.
Av de icke-jämförelserelaterade tekniker som diskuteras är alla outplaced-tekniker. Counting sort använder en räknearray och bucket sort använder en hashtabell för att sortera arrayen.

Online/Offline-teknik –
En sorteringsteknik anses vara online om den kan ta emot nya data medan förfarandet pågår, dvs. fullständiga data krävs inte för att påbörja sorteringen.
Av de jämförelserelaterade tekniker som diskuteras är det bara Insertion Sort som kvalificerar sig för detta på grund av den underliggande algoritm den använder, dvs. Den behandlar matrisen (inte bara elementen) från vänster till höger och om nya element läggs till till höger påverkar det inte den pågående operationen.

Stabil/instabil teknik –
En sorteringsteknik är stabil om den inte ändrar ordningen för element med samma värde.
Om de jämförelsebaserade teknikerna är bubbelsortering, insättningssortering och sammanslagningssortering stabila tekniker. Selektionssortering är instabil eftersom den kan ändra ordningen på element med samma värde. Tänk till exempel på matrisen 4, 4, 1, 3.

I den första iterationen är det minsta elementet som hittas 1 och det byts ut mot 4 i 0:e positionen. Därför ändras ordningen för 4 i förhållande till 4 i 1:a positionen. På samma sätt är quick sort och heap sort också instabila.

Utav de tekniker som inte är baserade på jämförelser är Counting sort och Bucket sort stabila sorteringstekniker medan radix sort stabilitet beror på den underliggande algoritm som används för sortering.

Analys av sorteringstekniker :

• När matrisen är nästan sorterad kan insättningssortering föredras.
• När inmatningsordningen inte är känd föredras sammanslagningssortering eftersom den i värsta fall har en tidskomplexitet på nlogn och dessutom är den stabil.
• När matrisen är sorterad ger insättningssortering och bubbelsortering en komplexitet på n, men snabbsortering ger en komplexitet på n^2.

Que – 1. Vilken sorteringsalgoritm tar minst tid när alla element i matrisen är identiska? Överväg typiska implementeringar av sorteringsalgoritmer.
(A) Insertion Sort
(B) Heap Sort
(C) Merge Sort
(D) Selection Sort

Lösning: Som diskuterats har insättningssortering en komplexitet på n när inmatningsmatrisen redan är sorterad.

Que – 2. Överväg Quicksort-algoritmen. Anta att det finns ett förfarande för att hitta ett pivotelement som delar upp listan i två underlistor som var och en innehåller minst en femtedel av elementen. Låt T(n) vara det antal jämförelser som krävs för att sortera n element. Då (GATE-CS-2012)
(A) T(n) <= 2T(n/5) + n
(B) T(n) <= T(n/5) + T(4n/5) + n
(C) T(n) <= 2T(4n/5) + n
(D) T(n) <= 2T(n/2) + n

Lösning: Komplexiteten för snabbsortering kan skrivas som:

T(n) = T(k) + T(n-k-1) + cn

Som anges i frågan innehåller en lista 1/5 av de totala elementen. Därför kommer en annan lista att innehålla 4/5 av de totala elementen. Genom att sätta värden får vi:

T(n) = T(n/5) + T(4n/5) + cn, vilket stämmer med alternativ (B).

Jämförelsetabell för tids- och rymdkomplexitet :

Sorteringsalgoritm	Tidskomplexitet			Rymdkomplexitet
	Bästfall	Medelvärde Case	Sämsta fall	Sämsta fall
Bubble Sort	Ω(N)	Θ(N2)	O(N2)	O(N2)	O(1)
Selektionssortering	Ω(N2)	Θ(N2)	O(N2)	O(1)
Insättningssortering	Ω(N)	Θ(N2)	O(N2)	O(1)
Sortering av sammanfogning	Ω(N log N)	Θ(N log N)	O(N log N)	O(N)
Heap Sort	Ω(N log N)	Ω(N log N)	Θ(N log N)	O(N log N)	O(1)
Snabbsortering	Ω(N log N)	Θ(N log N)	O(N2)	O(N log N)
Radixsortering	Ω(N k)	Θ(N k)	O(N k)	O(N + k)
Count Sort	Ω(N + k)	Θ(N + k)	O(N + k)	O(N + k)	O(k)
Bucket Sort	Ω(N + k)	Θ(N + k)	O(N2)	O(N)