GeeksforGeeks

I denne artikel vil vi diskutere vigtige egenskaber ved forskellige sorteringsteknikker, herunder deres kompleksitet, stabilitet og hukommelsesbegrænsninger. Før du forstår denne artikel, bør du forstå det grundlæggende i forskellige sorteringsteknikker (se : Sorteringsteknikker).

Tidskompleksitetsanalyse –
Vi har diskuteret den bedste, gennemsnitlige og værst tænkelige kompleksitet for forskellige sorteringsteknikker med mulige scenarier.

Sammenligningsbaseret sortering –
I sammenligningsbaseret sortering sammenlignes elementerne i et array med hinanden for at finde det sorterede array.

• Bubble sort og Insertion sort –
  Gennemsnitlig og værst tænkelig tidskompleksitet: n^2
  Best tænkelig tidskompleksitet: n, når arrayet allerede er sorteret.
  Worst case: når arrayet er omvendt sorteret.
• Selection sort –
  Best, average and worst case time complexity: n^2 som er uafhængig af fordelingen af data.
• Merge sort –
  Bedste, gennemsnitlige og værste tilfælde tidskompleksitet: nlogn, som er uafhængig af fordelingen af dataene.
• Heap sort –
  Bedste, gennemsnitlige og værste tilfælde tidskompleksitet: nlogn, som er uafhængig af fordelingen af dataene.
• Heap sort –
  Bedste, gennemsnitlige og værste tilfælde tidskompleksitet: nlogn, som er uafhængig af fordelingen af dataene.
• Quick sort –
  Det er en del og hersk-tilgang med recidivrelation:

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

  Worst case: Når arrayet er sorteret eller omvendt sorteret, opdeler partitionsalgoritmen arrayet i to underarkiver med 0 og n-1 elementer. Derfor,

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

  Best case og Average case: I gennemsnit opdeler partitionsalgoritmen arrayet i to underarkiver med samme størrelse. Derfor,

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

Non-comparison based sortering –
I non-comparison based sortering sammenlignes arrayets elementer ikke med hinanden for at finde det sorterede array.

• Radix-sortering –
  Bedste, gennemsnitlige og værst tænkelige tidskompleksitet: nk, hvor k er det maksimale antal cifre i arrayets elementer.
• Count-sortering –
  Bedste, gennemsnitlige og værst tænkelige tidskompleksitet: n+k, hvor k er størrelsen af count-array.
• Bucket sort –
  Bedste og gennemsnitlige tidskompleksitet: n+k, hvor k er antallet af buckets.
  Sværste tilfælde tidskompleksitet: n^2, hvis alle elementer tilhører den samme bucket.

In-place/Outplace-teknik –
En sorteringsteknik er inplace, hvis den ikke bruger ekstra hukommelse til at sortere arrayet.
Af de sammenligningsbaserede teknikker, der er blevet diskuteret, er kun sammenlægningssortering en outplaced-teknik, da den kræver et ekstra array til sammenlægning af de sorterede underarrays.
Af de ikke-sammenligningsbaserede teknikker, der er blevet diskuteret, er alle outplaced-teknikker. Counting sort bruger et tællearray, og bucket sort bruger et hash-tabeller til at sortere arrayet.

Online/Offline-teknik –
En sorteringsteknik anses for at være online, hvis den kan acceptere nye data, mens proceduren er i gang, dvs. at der ikke kræves fuldstændige data for at starte sorteringen.
Af de sammenligningsbaserede teknikker, der er blevet diskuteret, er det kun Insertion Sort, der opfylder dette krav på grund af den underliggende algoritme, den anvender, dvs. den behandler arrayet (ikke kun elementer) fra venstre mod højre, og hvis der tilføjes nye elementer til højre, påvirker det ikke den igangværende operation.

Stabil/ustabil teknik –
En sorteringsteknik er stabil, hvis den ikke ændrer rækkefølgen af elementer med samme værdi.
Ud af de sammenligningsbaserede teknikker er bubble sort, insertion sort og merge sort stabile teknikker. Selection sort er ustabile, da den kan ændre rækkefølgen af elementer med samme værdi. For eksempel kan arrayet 4, 4, 1, 3 betragtes.

I den første iteration er det mindste element, der er fundet, 1, og det er byttet ud med 4 på 0. position. Derfor vil rækkefølgen af 4 i forhold til 4 på 1. position ændres. På samme måde er quick sort og heap sort også ustabile.

Ud af de ikke-sammenligningsbaserede teknikker er Counting sort og Bucket sort stabile sorteringsteknikker, mens radix sort stabilitet afhænger af den underliggende algoritme, der anvendes til sortering.

Analyse af sorteringsteknikker :

• Når arrayet er næsten sorteret, kan insertion sort foretrækkes.
• Når rækkefølgen af input ikke er kendt, foretrækkes merge sort, da den har worst case tidskompleksitet på nlogn, og den er også stabil.
• Når arrayet er sorteret, giver insertion og bubble sort en kompleksitet på n, men quick sort giver en kompleksitet på n^2.

Que – 1. Hvilken sorteringsalgoritme tager mindst tid, når alle elementer i input array er identiske? Overvej typiske implementeringer af sorteringsalgoritmer.
(A) Insertion Sort
(A) Insertion Sort
(B) Heap Sort
(C) Merge Sort
(D) Selection Sort

Løsning: Som beskrevet har insertion sort en kompleksitet på n, når input arrayet allerede er sorteret.

Que – 2. Overvej Quicksort-algoritmen. Antag, at der findes en procedure til at finde et pivot-element, som opdeler listen i to underlister, som hver indeholder mindst en femtedel af elementerne. Lad T(n) være det antal sammenligninger, der er nødvendige for at sortere n elementer. Så er (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: Kompleksiteten af hurtigsortering kan skrives som:

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

Som angivet i spørgsmålet indeholder en liste 1/5 af de samlede elementer. Derfor vil en anden liste indeholde 4/5 af de samlede elementer. Ved at sætte værdierne ind får vi:

T(n) = T(n/5) + T(4n/5) + cn, hvilket svarer til mulighed (B).

Sammenligningstabel for tids- og rumkompleksitet :

Sorteringsalgoritme	Tidskompleksitet			Rumkompleksitet
	Best case	Gennemsnit Case	Worst Case	Worst Case
Bubble Sort	Ω(N)	Θ(N2)	O(N2)	O(N2)	O(1)
Selektionssortering	Ω(N2)	Θ(N2)	O(N2)	O(1)
Indsætningssortering	Ω(N)	Θ(N2)	O(N2)	O(1)
Merge Sort	Ω(N log N)	Ω(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)
Snavsortering	Ω(N log N)	Θ(N log N)	O(N2)	O(N log N)	O(N log N)
Radix-sortering	Ω(N k)	Θ(N k)	O(N k)	O(N + k)
Count Sort	Ω(N + k)	Ω(N + k)	Θ(N + k)	O(N + k)	O(k)
Bucket Sort	Ω(N + k)	Θ(N + k)	O(N2)	O(N)