Hoare metodas – Greitas rūšiavimas. Greitas rūšiavimas ir kas jis naudojamas masyvo rūšiavimo algoritmams greitai rūšiuoti
Greitas rūšiavimas greitas rūšiavimas), dažnai vadinamas qsort(pavadintas C standarto bibliotekoje) yra gerai žinomas rūšiavimo algoritmas, kurį sukūrė anglų kompiuterių mokslininkas Charlesas Hoare'as, dirbdamas Maskvos valstybiniame universitete 1960 m.
Vienas greičiausių žinomų universalių masyvų rūšiavimo algoritmų: vidutiniškai O(n log n) apsikeitimų tvarkant n elementų; Dėl daugybės trūkumų praktiškai jis dažniausiai naudojamas su tam tikrais pakeitimais.
Išskirtinis greito rūšiavimo bruožas yra masyvo padalijimas į dvi dalis, palyginti su atskaitos elementu. Pavyzdžiui, jei seką reikia rūšiuoti didėjimo tvarka, tada visi elementai, kurių reikšmės yra mažesnės už atskaitos elemento reikšmę, bus dedami kairėje pusėje, o elementai, kurių reikšmės yra didesnės arba lygios atskaitos elementas bus dedamas dešinėje pusėje. Nepriklausomai nuo to, kuris elementas pasirinktas kaip atskaitos elementas, masyvas bus rūšiuojamas, tačiau sėkmingiausia situacija, kai abiejose atskaitos elemento pusėse yra maždaug vienodas elementų skaičius. Jei kurios nors iš gautų dalių ilgis viršija vieną elementą, tada jį reikia rekursyviai sutvarkyti, t. y. iš naujo paleisti algoritmą kiekviename segmente.
Taigi greitojo rūšiavimo algoritmą sudaro du pagrindiniai etapai:
- masyvo padalijimas atskaitos elemento atžvilgiu;
- rekursinis kiekvienos masyvo dalies rūšiavimas.
Algoritmo įgyvendinimas įvairiomis programavimo kalbomis:
C
Veikia savavališkam n sveikųjų skaičių masyvui.
Int n, a[n]; //n – elementų skaičius void qs(int* s_arr, int pirmas, int paskutinis) ( int i = pirmas, j = paskutinis, x = s_arr[(pirmas + paskutinis) / 2]; do ( while (s_arr[i) ]< x) i++; while (s_arr[j] >x)j--; jeigu aš<= j) { if (s_arr[i] >s_arr[j]) apsikeitimas(&s_arr[i], &s_arr[j]); i++; j--; ) ) kol aš<= j); if (i < last) qs(s_arr, i, last); if (first < j) qs(s_arr, first, j); }
Pradinis n elementų masyvo funkcijos qs iškvietimas atrodytų taip.
Java/C#
Int skaidinys (int masyvas, int pradžia, int pabaiga) ( int žymeklis = pradžia; for (int i = pradžia; i<= end; i++) { if (array[i] <= array) { int temp = array; // swap array = array[i]; array[i] = temp; marker += 1; } } return marker - 1; } void quicksort (int array, int start, int end) { if (start >= pabaiga) ( return; ) int pivot = skaidinys (masyvas, pradžia, pabaiga); greitas rūšiavimas(masyvas, pradžia, sukimasis-1); quicksort(masyvas, suktis+1, pabaiga); )
C# su bendraisiais tipais, T tipas turi įdiegti sąsają IComparable
Int skaidinys
C# naudojant lambda išraiškas
Sistemos naudojimas; naudojant System.Collections.Generic; naudojant System.Linq; statinė viešoji klasė Qsort (viešoji statinė IEnumerable
C++
Greitas rūšiavimas pagal STL biblioteką.
#įtraukti
Java
importuoti java.util.Comparator; importuoti java.util.Random; public class Quicksort ( public static final Random RND = new Random(); private void swap(Object array, int i, int j) ( Object tmp = masyvas[i]; masyvas[i] = masyvas[j]; masyvas[j ] = tmp; ) privatus int skaidinys (Objekto masyvas, int pradžia, int pabaiga, Comparator cmp) ( int indeksas = pradžia + RND.nextInt(pabaiga - pradžia + 1); Objekto sukimasis = masyvas; swap (masyvas, indeksas, pabaiga) ); for (int i = indeksas = pradžia; i< end; ++ i) { if (cmp.compare(array[i], pivot) <= 0) { swap(array, index++, i); } } swap(array, index, end); return (index); } private void qsort(Object array, int begin, int end, Comparator cmp) { if (end >pradžia) ( int index = skirsnis(masyvas, pradžia, pabaiga, cmp); qsort(masyvas, pradžia, indeksas - 1, cmp); qsort(masyvas, indeksas + 1, pabaiga, cmp); ) ) public void sort(Object masyvas, Comparator cmp) ( qsort(masyvas, 0, masyvas.ilgis - 1, cmp); )„Java“ su masyvo inicijavimu ir maišymu bei masyvo rūšiavimo laiko matavimu naudojant nanotimerį (veikia tik jei nėra atitinkamų masyvo elementų)
<=N;i=i+1) { A[i]=N-i; System.out.print(A[i]+" "); } System.out.println("\nBefore qSort\n"); // перемешивание массива Random r = new Random(); //инициализация от таймера int yd,xs; for (int i=0;i<=N;i=i+1) { yd=A[i]; xs=r.nextInt(N+1); A[i]=A; A=yd; } for (int i=0;i<=N;i=i+1) System.out.print(A[i]+" "); System.out.println("\nAfter randomization\n"); long start, end; int low=0; int high=N; start=System.nanoTime(); // получить начальное время qSort(A,low,high); end=System.nanoTime(); // получить конечное время for (int i=0;i<=N;i++) System.out.print(A[i]+" "); System.out.println("\nAfter qSort"); System.out.println("\nTime of running: "+(end-start)+"nanosec"); } //описание функции qSort public static void qSort(int A, int low, int high) { int i = low; int j = high; int x = A[(low+high)/2]; do { while(A[i] < x) ++i; while(A[j] >x) -j; jeigu aš<= j){ int temp = A[i]; A[i] = A[j]; A[j] = temp; i ++ ; j --; } } while(i <= j); //рекурсивные вызовы функции qSort if(low < j) qSort(A, low, j); if(i < high) qSort(A, i, high); } }
JavaScript
Importuoti java.util.Random; public class QuickSort ( public static void main(String args) ( int N=10; int A; A = new int; // masyvo užpildymas for (int i=0;i<=N;i=i+1) { A[i]=N-i; System.out.print(A[i]+" "); } System.out.println("\nBefore qSort\n"); // перемешивание массива Random r = new Random(); //инициализация от таймера int yd,xs; for (int i=0;i<=N;i=i+1) { yd=A[i]; xs=r.nextInt(N+1); A[i]=A; A=yd; } for (int i=0;i<=N;i=i+1) System.out.print(A[i]+" "); System.out.println("\nAfter randomization\n"); long start, end; int low=0; int high=N; start=System.nanoTime(); // получить начальное время qSort(A,low,high); end=System.nanoTime(); // получить конечное время for (int i=0;i<=N;i++) System.out.print(A[i]+" "); System.out.println("\nAfter qSort"); System.out.println("\nTime of running: "+(end-start)+"nanosec"); } //описание функции qSort public static void qSort(int A, int low, int high) { int i = low; int j = high; int x = A[(low+high)/2]; do { while(A[i] < x) ++i; while(A[j] >x) -j; jeigu aš<= j){ int temp = A[i]; A[i] = A[j]; A[j] = temp; i ++ ; j --; } } while(i <= j); //рекурсивные вызовы функции qSort if(low < j) qSort(A, low, j); if(i < high) qSort(A, i, high); } }
Python
Naudojant generatorius:
Def qsort(L): if L: grąžina qsort(jei x
Matematinė versija:
Def qsort(L): jei L: grąžina qsort(filter(lambda x: x< L, L)) + L + qsort(filter(lambda x: x >= L, L)) grąžinti
Džiaugsmas
NUSTATYTI rūšiavimą == padalijimas] [ dip concat] binrec .PHP
funkcija qsort($s) ( for($i=0, $x=$y=masyvas(); $iQsort = qsort(x:xs) = qsort(filter(< x) xs) ++ [x] ++ qsort (filter (>= x)xs)
Matematinė versija – naudojant generatorius:
Qsort = qsort (x:xs) = qsort ++ [x] ++ qsort
Paprastasis Lisp
Skirtingai nuo kitų čia pateiktų funkcinių kalbų įgyvendinimo parinkčių, nurodytas algoritmo įgyvendinimas Lisp yra „sąžiningas“ - jis negeneruoja naujo surūšiuoto masyvo, o rūšiuoja tą, kuris buvo gautas kaip įvestis, „toje pačioje vietoje. “ Kai pirmą kartą iškviečiate funkciją, turite perduoti apatinį ir viršutinį masyvo (arba jo dalies, kurią reikia rūšiuoti) indeksus į l ir r parametrus. Kode naudojamos „Common Lisp“ „būtinai“ makrokomandos.
(defun QuickSort (masyvas l r) (leisk ((i l) (j r) (p (svref array (round (+ l r) 2)))) (while (<= i j) (while (< (svref array i) p) (incf i)) (while (>(svref masyvas j) p) (decf j)) (kai (<= i j) (rotatef (svref array i) (svref array j)) (incf i) (decf j))) (if (>= (- j l) 1) (greito rūšiavimo masyvas l j)) (jei (>= (- r i) 1) (greito rūšiavimo masyvas i r))) masyvas)
Paskalis
Šiame pavyzdyje parodyta pati išsamiausia algoritmo forma, išvalyta nuo ypatybių, nustatytų pagal naudojamą kalbą. Komentarai rodo keletą variantų. Pateiktoje algoritmo versijoje atskaitos elementas parenkamas pseudoatsitiktiniu būdu, o tai teoriškai sumažina blogiausio atvejo ar prie jo priartėjimo tikimybę iki minimumo. Jo trūkumas yra tas, kad algoritmo greitis priklauso nuo pseudoatsitiktinių skaičių generatoriaus įgyvendinimo. Jei osciliatorius veikia lėtai arba sukuria blogas PNG sekas, veikimas gali sulėtėti. Komentaras suteikia galimybę pasirinkti vidutinę reikšmę masyve – taip paprasčiau ir greičiau, nors teoriškai galėtų būti ir blogiau.
Vidinė sąlyga, pažymėta komentaru „šią sąlygą galima pašalinti“, yra neprivaloma. Jo buvimas turi įtakos veiksmams situacijoje, kai paieška randa du vienodus raktus: jei yra čekis, jie liks vietoje, o jei ne, jie bus sukeisti. Kas užtruks daugiau laiko – patikros ar papildomos permutacijos – priklauso ir nuo architektūros, ir nuo masyvo turinio (aišku, jei bus daug vienodų elementų, papildomų permutacijų bus daugiau). Ypač reikėtų pažymėti, kad sąlyga nepadaro šio rūšiavimo metodo stabiliu.
Const max=20; (galima ir daugiau...) type list = sveikųjų skaičių masyvas; procedura quicksort(var a: sąrašas; Lo,Hi: integer); procedura sort(l,r: sveikasis skaičius); var i,j,x,y: sveikasis skaičius; pradėti i:=l; j:=r; x:=a; ( x:= a[(r+l) div 2]; - norėdami pasirinkti vidurinį elementą ) pakartokite, kol a[i] Tvirta parinktis (reikia papildomos O (n) atminties) Const max=20; (galima ir daugiau...) type list = sveikųjų skaičių masyvas; procedura quicksort(var a: sąrašas; Lo,Hi: integer); procedura sort(l,r: sveikasis skaičius); var i,j,x,xval,y: sveikasis skaičius; pradėti i:=l; j:=r; x:=atsitiktinis(r-l+1)+l; xval:=a[x]; xvaln:=num[x]( x:=(r+l) div 2; - norėdami pasirinkti vidurinį elementą ) pakartokite, kol (a[i] Greitas rūšiavimas, nerekursyvus pasirinkimas Nerekursyvus greito rūšiavimo per dėklas įgyvendinimas. Palyginimo ir keitimo funkcijos įgyvendinamos priklausomai nuo duomenų tipo. Procedūra quickSort(var X: itemArray; n: integer); įveskite p_node = ^mazgas; mazgas = įrašo mazgas: sveikasis skaičius; kitas: p_mazgo pabaiga; var l,r,i,j: sveikasis skaičius; krūva: p_mazgas; temp:item; procedūra push(i: sveikasis skaičius); var temp: p_mazgas; pradėti naują(temp); temp^.node:=i; temp^.next:=stack; stack:=temp end; funkcija pop: sveikasis skaičius; var temp: p_mazgas; begin if stack=nil then pop:=0 else begin temp:=stack; pop:=stack^.mazgas; stack:=stack^.kitas; dispose(temp) end end; start stack:=nil; stumti(n-1); stumti(0); kartoti l:=pop; r:=pop; jei r-l=1 tada pradėkite jei palyginkite(X[l],X[r]), tada keiskite(X[l],X[r]) end else pradėti temp:=x[(l+r) div 2]; (atsitiktinis(r-l+1)+l) i:=l; j:=r; pakartokite, kol palyginkite(temp,X[i]) do i:=i+1; o palyginti (X[j],temp) do j:=j-1; jeigu aš<=j then
begin
change(X[i],X[j]);
i:=i+1;
j:=j-1
end;
until i>j; jei l Šis pavyzdys parodo savavališko predikato naudojimą funkcinėje kalboje. Linksmas greitas rūšiavimas lt lst = tegul val rec rūšiuoti = fn => | (x::xs) => tegul val (kairėje, dešinėje) = Sąrašo skaidinys (fn y => lt (y, x)) xs rūšiuoti kairėje @ x:: rūšiuoti dešinėje pusėje rūšiuoti lst pabaigoje @out=(5,2,7,9,2,5,67,1,5,7,-8,5,0); sub sortQ( my($s, $e) = @_; mano $m = $s - 1; for($s..$e - 1)( if($out[$_] lt $out[$e ])( ++$m; ($out[$m], $out[$_]) = ($out[$_], $out[$m]); ) ) ++$m; ($out [$m], $out[$e]) = ($out[$e], $out[$m]); rūšiuotiQ($s, $m-1), jei $s< $m-1;
sortQ($m+1, $e) if $m+1 < $e;
}
sortQ(0, $#out); Tegul rec Quicksort = funkcija -> | h::t -> greitas rūšiavimas ([ x in t, kai x<=h ->x]) @ [h] @ greitas rūšiavimas ([ x in t, kai x>h -> x]);; Tegul rec qsort l=atitinka l su -> |a::b-> (qsort (List.filter ((>=) a) b) lt) @ [a] @ (qsort (List.filter ((<) a) b));; Qsort() -> ; qsort() -> qsort() ++ [H] ++ qsort(). Masyvo qsort(masyvas)(masyvas _a) ( slapyvardis(masyvo.init) _type; masyvo filtras(bool delegate(_type) dg, masyvas a)( masyvo buferis = null; foreach(value; a) ( if(dg(value) ))( buferis ~= reikšmė; ) ) grąžinti buferį; ) if(_a.length<= 1) {
return _a;
}
else {
return qsort(filter((_type e){ return _a >= e; ), _a)) ~ _a ~ qsort(filter((_type e)( return _a< e; }, _a));
}
} Trumpesnė versija naudojant standartinę Phobos biblioteką: Importuoti std.algoritmą; T_qsort3(T)(T a) ( if(a.length<= 1)
return a;
else
return _qsort3(a.filter!(e =>a >= e).masyvas) ~ a ~ _qsort3(a.filter!(e => a< e).array);
} Numatytasis qsort](sąrašas: Sąrašas[A]): Sąrašas[A] = sąrašo atitiktis ( didžiosios raidės pavadinimas::uodega => ( qsort(uodegos filtras(head>=)) ::: head:: qsort(uodegos filtras (galva<))
}
case _ =>sąrašas; ) Kitas variantas: Numatytasis rūšiavimas(xs: Masyvas): Masyvas = ( if (xs.length<= 1) xs
else {
val pivot = xs(xs.length / 2)
Array.concat(sort(xs filter (pivot >)), xs filtras (pivot ==), rūšiuoti (xs filtras (sukti<)))
}
} Tingus įgyvendinimas: (defn qsort [] (letfn [(f [g] (qsort (filtras #(g % x) xs))))] (kai x (tinginys-katė (f)<) [x] (f >=))))) (apibrėžti filtrą ((A --> loginis) --> (sąrašas A) --> (sąrašas A)) _ -> T? -> (pridėti [A] (filtras T? B)) kur (T? A ) T? [_|B] -> (filtras T? B)) (apibūdinti q-sort ((sąrašo numeris) --> (sąrašo numeris)) -> -> (pridėti (q-rūšiuoti (filtras (> A)) ) )) [A] (q-rūšiavimas (filtras ()< A) )))) Sprendžiant iš testų, burbulų rūšiavimas 5000 užtrunka 8 su puse karto ilgiau nei qSort Sub Swap (ByRef Val1, ByRef Val2) Dim Proc = Val1 Val1 = Val2 Val2 = Proc pabaigos subfunkcijos skaidinys (ByRef a() Kaip sveikasis skaičius, ByVal kairėje kaip sveikasis skaičius, ByVal dešinėje kaip sveikasis skaičius, ByRef sukimasis kaip sveikasis skaičius) Dim i Dim piv Pritemdyta saugykla piv = a(suvestis) Sukeisti(a(dešinė - 1), a(suvestis)) parduotuvė = kairė For i = kairė Į dešinę - 2 Jei a(i)<= piv Then
Swap(a(store), a(i))
store = store + 1
End If
Next
Swap(a(right - 1), a(store))
Return store
End Function
Function getpivot(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer)
Return New System.Random().Next(left, right - 1)
End Function
Sub quicksort(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer)
Dim pivot As Integer
If right - left >1 Tada sukimas = getpivot(a, kairėn, dešinėn) susukimas = skaidinys(a, kairėn, dešinėn, suktis) quicksort(a, left, pivot) quicksort(a, pivot + 1, right) End If End Sub Sub qSort(ByVal) a() Kaip sveikasis skaičius) Dim i Dim ii Kai i = 0 Iki a.Length() - 1 ii = Nauja sistema.Atsitiktinis().Next(0, a.Length() - 1) Jei i<>ii Tada Sukeisti(a(i), a(ii)) Pabaiga, jei kitas greitas rūšiavimas(a, 0, a.Length()) Pabaigos sub Funkcijos skambutis: QSort (rūšiuojamo masyvo pavadinimas) Funkcijos greitas rūšiavimas (& $masyvas , $l = 0, $r = 0 ) ( if($r === 0) $r = count($masyvas)-1; $i = $l; $j = $r; $x = $masyvas[($l + $r) / 2]; do ( while ($masyvas[$i]< $x) $i++;
while ($array[$j] >$x) $j--; jei ($i<= $j) {
if ($array[$i] >$masyvas[$j]) list($masyvas[$i], $masyvas[$j]) = masyvas($masyvas[$j], $masyvas[$i]); $i++; $j--; ) ) o ($i<= $j);
if ($i < $r) quicksort ($array, $i, $r);
if ($j >$l) greitas rūšiavimas ($masyvas, $l, $j); ) Čia yra rūšiavimo algoritmas, naudojant „Verčių sąrašo“ tipo objekto pavyzdį, tačiau jį galima modifikuoti, kad jis veiktų su bet kokiu objektu; norėdami tai padaryti, turite pakeisti „CompareValues“, „GetValue“ kodą. , „SetValue“ veikia atitinkamai. Funkcija Lyginti Vertes(reikšmė1, Reikšmė2) Jei Reikšmė1>Vertė2 Tada grąžina 1; endIf; Jei reikšmė1<Знач2 Тогда
Возврат -1;
КонецЕсли;
Возврат 0;
КонецФункции
Функция ПолучитьЗначение(Список, Номер)
Возврат Список.Получить(Номер-1).Значение;
КонецФункции
Процедура УстановитьЗначение(Список, Номер, Значение)
Список[Номер-1].Значение = Значение;
КонецПроцедуры
Процедура qs_0(s_arr, first, last)
i = first;
j = last;
x = ПолучитьЗначение(s_arr, Окр((first + last) / 2, 0));
Пока i <= j Цикл
Пока СравнитьЗначения(ПолучитьЗначение(s_arr, i), x)=-1 Цикл
i=i+1;
КонецЦикла;
Пока СравнитьЗначения(ПолучитьЗначение(s_arr, j), x)=1 Цикл
j=j-1;
КонецЦикла;
Если i <= j Тогда
Если i < j Тогда
к=ПолучитьЗначение(s_arr, i);
УстановитьЗначение(s_arr, i, ПолучитьЗначение(s_arr, j));
УстановитьЗначение(s_arr, j, к);
КонецЕсли;
i=i+1;
j=j-1;
КонецЕсли;
КонецЦикла;
Если i < last Тогда
qs_0(s_arr, i, last);
КонецЕсли;
Если first < j Тогда
qs_0(s_arr, first,j);
КонецЕсли;
КонецПроцедуры
Процедура Сортировать(Список, Размер="", Первый="", Последний="")
Если Не ЗначениеЗаполнено(Первый) Тогда
Первый=1;
КонецЕсли;
Если НЕ ЗначениеЗаполнено(Последний) Тогда
Последний=Размер;
КонецЕсли;
qs_0(Список, Первый, Последний);
КонецПроцедуры DEF FN QSORT(ŽEMAS, AUKŠTAS) VIETINIS I,J,X,TEMP.J=AUKŠTAS X=Y[(ŽEMAS+AUKŠTAS)/2] DO WHILE Y[I] Funkcijos FN QSORT(LOW, HIGH) iškvietimo pavyzdys, įvesties ir išvesties duomenys DIM Y masyve LOW = N1 AUKŠTAS = N2 F = FN QSORT (žemas, AUKŠTAS) Verta paminėti, kad greitas rūšiavimas gali būti neveiksmingas masyvuose, kuriuos sudaro nedidelis elementų skaičius, todėl dirbant su jais protingiau šio metodo atsisakyti. Apskritai, algoritmas yra nestabilus, o rekursijos naudojimas neteisingai parašytame kode gali sukelti krūvos perpildymą. Tačiau, nepaisant šių ir kai kurių kitų trūkumų, greitas rūšiavimas vis dar yra vienas efektyviausių ir dažniausiai naudojamų būdų. Rašant šį straipsnį buvo naudojami atvirieji šaltiniai internete: Jei programuojate ir jūsų kodas neapsiriboja skaičiuotuvo rašymu, ne kartą susidursite arba susidūrėte su poreikiu rūšiuoti tą ar kitą duomenų masyvą. Yra daug būdų rūšiuoti. Šiame straipsnyje išanalizuosime pagrindinius ir sutelksime dėmesį į greitą rūšiavimą. Greitas rūšiavimas – Greitas rūšiavimas arba qsort. Pavadinimas aiškiai parodo, kas tai yra ir kodėl. Bet jei tai neaišku, tai yra greito masyvo rūšiavimo algoritmas; algoritmo efektyvumas yra vidutiniškai O(n log n). Ką tai reiškia? Tai reiškia, kad vidutinė algoritmo veikimo trukmė didėja ta pačia trajektorija kaip ir šios funkcijos grafikas. Kai kurios populiarios kalbos turi integruotas bibliotekas su šiuo algoritmu, o tai jau rodo, kad jis yra labai efektyvus. Tai yra tokios kalbos kaip Java, C++, C#. Greitojo rūšiavimo metodas naudoja rekursiją ir strategiją „skaldyk ir valdyk“. 1. Masyve ieškoma tam tikro atskaitos elemento, dėl paprastumo geriau paimti centrinį, bet jei norite dirbti su optimizavimu, turėsite išbandyti įvairias parinktis. 2. Į kairę nuo atramos ieškome didesnio už atramą elemento, dešinėje - mažesnio už atramą, tada juos sukeičiame. Tai darome tol, kol maksimumas dešinėje bus mažesnis nei kairėje esantis minimumas. Taigi pradžioje metame visus mažus elementus, o pabaigoje – didelius. 3. Šį algoritmą rekursyviai pritaikome kairiajai ir dešiniajai mūsų algoritmo dalims, tada vėl ir vėl, kol pasiekiame vieną elementą arba tam tikrą elementų skaičių. Koks yra šis elementų skaičius? Yra dar vienas būdas optimizuoti šį algoritmą. Kai išrūšiuota dalis tampa maždaug lygi 8 arba 16, tada ją galima apdoroti įprastiniu rūšiavimu, pavyzdžiui, burbuliniu rūšiavimu. Taip padidinsime savo algoritmo efektyvumą, nes Jis neapdoroja mažų masyvų taip greitai, kaip norėtume. Tokiu būdu visas masyvas bus apdorojamas ir rūšiuojamas. Dabar aiškiai išstudijuokime šį algoritmą Ar greitasis rūšiavimas yra greičiausias rūšiavimo algoritmas? Tikrai ne. Dabar atsiranda vis daugiau rūšiavimo, šiuo metu greičiausias rūšiavimas yra Timsort, itin greitai veikia masyvams, kurie iš pradžių buvo surūšiuoti kitaip. Tačiau nepamirškite, kad greito rūšiavimo metodas yra vienas iš paprasčiausių rašymo būdų; tai labai svarbu, nes paprastai įprastam projektui tereikia paprasto rašymo, o ne didžiulio algoritmo, kurio negalėtumėte parašyti. save. Timsort taip pat nėra pats sudėtingiausias algoritmas, tačiau jis tikrai negaus paprasčiausio titulo. Na, mes pasiekėme „skaniąją“ dalį. Dabar pažiūrėkime, kaip šis algoritmas įgyvendinamas. Kaip minėta anksčiau, tai nėra labai sunku įgyvendinti, greičiau net paprasta. Tačiau mes vis tiek išsamiai išanalizuosime kiekvieną savo kodo veiksmą, kad suprastumėte, kaip veikia greitas rūšiavimas. Mūsų metodas vadinamas greituoju rūšiavimu. Jis vykdo pagrindinį algoritmą, į kurį perduodame masyvą, pirmąjį ir paskutinįjį jo elementus. Pirmuosius ir paskutinius surūšiuoto segmento elementus saugome kintamuosiuose i ir k, kad šie kintamieji nepakeistų, nes mums jų reikia. Tada patikriname atstumą tarp pirmo ir paskutinio patikrinto: ar jis didesnis ar lygus vienetui? Jei ne, tada mes pasiekėme centrą ir turime išeiti iš šio segmento rūšiavimo, o jei taip, tada tęsiame rūšiavimą. Tada pirmąjį rūšiuojamo segmento elementą imame kaip atraminį elementą. Darome kitą ciklą, kol pasieksime centrą. Jame darome dar du ciklus: pirmasis - kairiajai daliai, o antrasis - dešinei. Juos atliekame tol, kol yra sąlygą atitinkančių elementų arba kol pasiekiame atraminį elementą. Tada, jei minimalus elementas vis dar yra dešinėje, o maksimalus elementas yra kairėje, mes juos sukeičiame. Ciklui pasibaigus, pakeičiame pirmąjį elementą ir atskaitos elementą, jei atskaitos elementas yra mažesnis. Tada mes rekursyviai atliekame savo algoritmą dešiniajai ir kairiajai masyvo dalims ir tęsiame tol, kol pasieksime 1 elemento ilgio skyrių. Tada visi mūsų rekursiniai algoritmai grįš ir mes visiškai išeisime iš rūšiavimo. Taip pat apačioje yra apsikeitimo metodas - visiškai standartinis masyvo rūšiavimo būdas pakeičiant. Kad nerašytume pakeičiančių elementų kelis kartus, mes rašome vieną kartą ir keičiame elementus šiame masyve. Apibendrinant galima teigti, kad pagal kokybės ir sudėtingumo santykį greitasis rūšiavimas užima pirmaujančias pozicijas tarp visų algoritmų, todėl tikrai turėtumėte įsidėmėti šį metodą ir prireikus jį panaudoti savo projektuose. Funkcija qsort surūšiuoja masyvo elementų skaičių, į kuriuos nukreipia pirmasis žymeklis. Kiekvienam masyvo elementui suteikiamas dydis baitais, kuris perduodamas per dydžio parametrą. Paskutinis funkcijos qsort parametras yra lyginamoji rodyklė į palyginimo funkciją, kuri naudojama elementų tvarkai surūšiuotame masyve nustatyti. Šios funkcijos naudojamas rūšiavimo algoritmas lygina reikšmių poras, iškviesdamas nurodytą palyginimo funkciją, su dviem rodyklėmis į masyvo elementus. Ši funkcija negrąžina jokios reikšmės, bet pakeičia masyvo, į kurį pirmiausia nurodė, turinį. Taigi masyvo elementai užima naujas vietas pagal rūšiavimo tvarką. Funkcija turi užimti du parametrus – rodykles į masyvo elementus, kurių tipas void*. Šie parametrai turi būti perduoti tam tikriems duomenų tipams. Šios funkcijos grąžinimo vertė turi būti neigiama, nulis arba teigiama. Jei val1 yra mažesnis, lygus arba didesnis nei val2 , funkcija turi atitinkamai grąžinti neigiamą reikšmę, nulį arba teigiamą reikšmę. Pastaba: praktikoje surūšiuotas rinkinys paprastai skirstomas ne į tris, o į dvi dalis: pavyzdžiui, „mažesnis už atskaitą“ ir „lygus ir didesnis“. Bendru atveju šis metodas pasirodo esąs efektyvesnis, nes tokiam padalijimui atlikti pakanka vieno praėjimo per surūšiuotą rinkinį ir vieno apsikeitimo tik kai kuriais pasirinktais elementais. „Quicksort“ naudoja „skaldyk ir valdyk“ strategiją. Algoritmo žingsniai yra šie: Kadangi kiekvienoje iteracijoje (kiekviename kitame rekursijos lygyje) apdorojamo masyvo segmento ilgis sumažėja bent vienu, galutinis rekursijos atšakas visada bus pasiektas ir apdorojimas bus garantuotas. Įdomu tai, kad Hoare'as sukūrė šį metodą, susijusį su mašininiu vertimu: faktas yra tas, kad tuo metu žodynas buvo saugomas magnetinėje juostoje, o jei tekste išdėstysite visus žodžius, jų vertimus bus galima gauti vienu juostos paleidimu. Algoritmą Hoare'as sugalvojo būdamas Sovietų Sąjungoje, kur Maskvos universitete studijavo kompiuterinį vertimą ir kūrė rusų-anglų kalbų sąsiuvinį (sakoma, kad šį algoritmą jis girdėjo iš rusų studentų). //algoritmas Java public static void qSort(int A, int low, int high) ( int i = žemas; int j = didelis; int x = A[ (žemas+ aukštas) / 2 ] ; do ( while (A[ i])<
x)
++
i;
while
(A[
j]
>x) -- j; jeigu aš<=
j)
{
int
temp =
A[
i]
;
A[
i]
=
A[
j]
;
A[
j]
=
temp;
i++;
j--;
}
}
while
(i <
j)
;
if
(low <
j)
qSort(A, low, j)
;
if
(i <
high)
qSort(A, i, high)
;
}
//algoritmas Paskalio kalba procedūra qSort(var ar: realaus masyvas ; žemas, aukštas: sveikasis skaičius ) ; var i, j: sveikasis skaičius ; m, wsp: realus ; start i: = žemas; j: = didelis; m: = ar[ (i+ j) div 2 ] ; kartoti kol (ar[i] //algoritmas Visual Basic kalba
//pirmojo skambučio metu 2-asis argumentas turi būti lygus 1
//3-asis argumentas turi būti lygus masyvo elementų skaičiui Sub qSort(ByVal ar() Kaip double, ByVal low As Integer , ByVal high As Integer ) Dim i, j Kaip sveikasis skaičius Dim m, wsp Kaip double i = žemas j = didelis m = ar((i + j) \ 2 ) Daryti iki i > j Daryti, kol ar(i)< m
i +=
1
Loop
Do
While
ar(j)
>m j - = 1 kilpa Jei (t. y<=
j)
Then
wsp =
ar(i)
ar(i)
=
ar(j)
ar(j)
=
wsp
i +=
1
j -=
1
End
If
Loop
If
(low < j)
Then
qSort(ar,
low,
j)
If
(i < high)
Then
qSort(ar,
i,
high)
End
Sub „QuickSort“ yra žymiai patobulinta tiesioginio mainų rūšiavimo algoritmo versija (jo variantai žinomi kaip „Bubble Sort“ ir „Shaker Sort“), žinoma, be kita ko, dėl mažo efektyvumo. Esminis skirtumas yra tas, kad po kiekvieno praėjimo elementai yra suskirstyti į dvi nepriklausomas grupes. Įdomus faktas: patobulinus neefektyviausią tiesioginio rūšiavimo metodą, buvo gautas efektyvus patobulintas metodas. Privalumai: Trūkumai: Sveiki visi! Pakalbėsiu apie greitojo rūšiavimo algoritmą ir parodysiu, kaip jį galima įgyvendinti programiškai. // qsort (0, n-1); Šis įgyvendinimas turi nemažai trūkumų, pvz., galimą dėklo perpildymą dėl didelio įdėtos rekursijos kiekio ir tai, kad atskaitos elementas visada laikomas viduriniu. Pavyzdžiui, tai gali būti normalu, bet sprendžiant, pavyzdžiui, olimpiados uždavinius, gudri žiuri gali specialiai atrinkti tokius testus, kad šis sprendimas jiems veiktų per ilgai ir neperžengtų ribos. Iš esmės kaip atskaitos elementą galite paimti bet kurį elementą, tačiau geriau, kad jis būtų kuo arčiau medianos, kad galėtumėte jį pasirinkti atsitiktinai arba paimti vidutinę reikšmę iš pirmos, vidutinės ir paskutinės. Našumo priklausomybė nuo atskaitos elemento yra vienas iš algoritmo trūkumų, nieko negalima padaryti, tačiau labai retai įvyksta didelis našumo pablogėjimas, dažniausiai rūšiuojant specialiai pasirinktą skaičių rinkinį. Jei vis tiek reikia rūšiavimo, kuris garantuotai veiks greitai, galite naudoti, pavyzdžiui, heapsort, kuris visada veikia griežtai O(n log n). Paprastai Qsort vis tiek pranoksta kitus, nereikalauja daug papildomos atminties ir yra gana paprasta įdiegti, todėl yra pelnytai populiarūs. Rašiau pats, retkarčiais žvilgtelėdamas į Vikipediją. Naudodamasis proga, norėčiau išreikšti savo padėką nuostabiems PetrSU dėstytojams ir studentams, kurie išmokė mane daug naudingų dalykų, įskaitant ir šį algoritmą! Žymos: Qsort, greitas rūšiavimas, rūšiavimo algoritmai, algoritmai, CProlog
padalijimas(H, , , Z) :- tvarka(A, H), padalijimas(H, X, Y, Z). padalinti(H, , Y, ) :- ne(tvarka(A, H)), padalijimas(H, X, Y, Z). padalinti (_, , , ). greitas rūšiavimas (, X, X). greitas rūšiavimas (, S, X) : - padalijimas (H, T, A, B), greitas rūšiavimas (A, S, ), greitas rūšiavimas (B, Y, X). Rubinas
def sort(masyvas) return if array.empty? kairėje, dešinėje = masyvas.skirstymas ( |y| y<= array.first }
sort(left) + [ array.first ] + sort(right)
end
SML
JavaScript
funkcija QuickSort(A, p, r) ( if(p Perl
F#
OCaml
Erlang
D
Scala
Clojure
Shen / Qi II
VB.NET
PHP
Integruota kalba 1C 8.*
Turbo Basic 1.1
Greito rūšiavimo sąvoka
Algoritmas
Greito rūšiavimo efektyvumas
Algoritmo įgyvendinimas
apibūdinimas
Galimybės:
int funccmp(const void * val1, const void * val2);
Rodyklė į pirmąjį rūšiuojamo masyvo elementą.
Elementų skaičius rūšiuojamajame masyve, į kurį nukreipta pirmoji žymeklis.
Vieno masyvo elemento dydis baitais.
Funkcija, lyginanti du elementus. Funkcija turi turėti tokį prototipą:Grąžinimo vertė
Pavyzdys: programos šaltinio kodas
//funkcijos qsort naudojimo pavyzdys #include Trumpas algoritmo aprašymas
Algoritmas
Efektyvumo ženklas
Praktiškai (tuo atveju, kai mainai yra brangesnė operacija nei palyginimai), greitas rūšiavimas yra žymiai greitesnis nei kiti algoritmai su O( n lg n), dėl to, kad vidinė algoritmo kilpa gali būti efektyviai įgyvendinta beveik bet kurioje architektūroje. 2C N/2 padengia dviejų gautų pogrupių rūšiavimo išlaidas; N yra kiekvieno elemento apdorojimo naudojant vieną ar kitą žymeklį kaina. Taip pat žinoma, kad apytikslė šios išraiškos reikšmė yra C N = N log N.
Blogiausiu atveju suteikia O( n²) mainai. Tačiau keitimų skaičius ir atitinkamai veikimo laikas nėra didžiausias jo trūkumas. Blogiausia tai, kad tokiu atveju rekursijos gylis vykdant algoritmą sieks n, o tai reikš n kartų išsaugoti masyvo padalijimo procedūros grąžinimo adresą ir vietinius kintamuosius. Esant didelėms n reikšmėms, blogiausiu atveju gali pritrūkti atminties, kol veikia algoritmas. Tačiau naudojant daugumą realių duomenų galima rasti sprendimus, kurie sumažintų tikimybę, kad prireiks kvadratinio laiko.Patobulinimai
Privalumai ir trūkumai
Pastabos
Literatūra
svetimas 2011 m. gegužės 30 d., 15.24 val Greitas rūšiavimas ir su kuo jį valgyti
Taigi greitasis rūšiavimas arba, pagal funkcijos pavadinimą C, Qsort yra rūšiavimo algoritmas, kurio sudėtingumas vidutinis yra O(n log(n)). Jo esmė itin paprasta: pasirenkamas vadinamasis atskaitos elementas, o masyvas suskirstomas į 3 pogrupius: mažesnį už atskaitą, lygų atskaitai ir didesnį už nuorodą. Tada šis algoritmas rekursyviai taikomas posistemiams.Algoritmas
Na, neatrodo taip sunku. Ar galime tai įgyvendinti C? Jokiu problemu! void qsort(int b, int e)
{
int l = b, r = e;
int piv = arr[(l + r) / 2]; // Pavyzdžiui, paimkime vidurinį kaip atskaitos elementą
kol (l<= r)
{
o (arr[l]< piv)
l++;
while (arr[r] > piv)
r--;
jei (l<= r)
apsikeisti (arr, arr);
}
jei (b< r)
qsort(b,r);
jei (e > l)
qsort(l, e);
} /* ----- funkcijos qsort pabaiga ----- */
* Šis šaltinio kodas buvo paryškintas naudojant šaltinio kodo žymėjimą .