Hitro urejanje
Iz Wikipedije, proste enciklopedije
Hitro urejanje ali QuickSort je eden od najbolj znanih in uporabljenih algoritmov za sortiranje, razvil ga je C. A. R. Hoare.
Algoritem razdeli zaporedje na dve podzaporedji tako, da lahko uredimo vsak del posebej. To je možno, ker so v prvem delu tabele vsi elementi manjši od vseh elementov v drugem delu tabele. Za mejo se uporablja delilni element ali pivot, katerega izberemo iz zaporedja. Poseben pivot se imenuje mediana, ki pa je ravno v sredini med vsemi elementi.
Vsebina |
[uredi] Izbiranje pivota
- prvi element
- zadnji element
- naključno izbran element
- sredinski element ali mediana.
[uredi] Delovanje
Zaporedje pregledujemo z leve in desne strani. Levi indeks povečujemo, dokler ne naletimo na element, ki je večji ali enak od delilnega. Zatem zmanjšujemo desni indeks, dokler ne naletimo na element, ki je manjši ali enak od delilnega elementa. Ko naletimo na takšna elementa in se indeksa ne prekrižata, zamenjamo položaj teh dveh elementov. Kadar pa sta se prekrižala pa zamenjamo desni indeks z mejnim elementom in rekurzivno kličemo proceduro HitroUredi.
Nobeno od zaporedij ne vsebuje delilnega elementa, saj je le-ta že na pravilnem mestu.
[uredi] Zahtevnost
Časovna zahtevnost je Θ(n log n), v najslabšem primeru pa O(n2).
[uredi] Psevdokoda
procedure HitroUredi(a, dno, vrh)
begin
if dno < vrh then
begin
j=vrh+1
Deli(a,dno,j)
HitroUredi(a, dno, j-1)
HitroUredi(a, j+1m vrh)
end
end
procedure Deli(a, dno, vrh)
begin
w := a[dno]
i := dno
p := vrh
loop
repeat
i := i+1
until a[i] >= w
repeat
p := p-1
until a[p] <= w
if i<p then
begin
b := a[i]
a[i] := a[p]
a[p] := b
end
forever
a[dno] := a[p]
a[p] := w
vrh := p
end
[uredi] Implementacija v programskih jezikih
[uredi] Haskell
quicksort [] = []
quicksort (x:xs) = quicksort [y | y <- xs, y < x] ++ [x] ++ quicksort [y | y <- xs, y >= x]
[uredi] Perl
sub qsort {
@_ or return ();
my $p = shift;
(qsort(grep $_ < $p, @_), $p, qsort(grep $_ >= $p, @_));
}
[uredi] Perl 6
multi quicksort () { () }
multi quicksort (*$x, *@xs) {
my @pre = @xs.grep:{ $_ < $x };
my @post = @xs.grep:{ $_ >= $x };
(@pre.quicksort, $x, @post.quicksort);
}
[uredi] Python
#s ist eine Liste
def quicksort(s):
if len(s) <= 1:
return s
else:
return quicksort([x for x in s[1:] if x < s[0]]) + [s[0]] + quicksort([y for y in s[1:] if y >= s[0]])
[uredi] Java
import java.util.Comparator;
import java.util.Random;
public class Quicksort {
public static final Random RND = new Random();
private void swap(Object[] array, int i, int j) {
Object tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
private int partition(Object[] array, int begin, int end, Comparator cmp) {
int index = begin + RND.nextInt(end - begin + 1);
Object pivot = array[index];
swap(array, index, end);
for (int i = index = begin; 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 > begin) {
int index = partition(array, begin, end, cmp);
qsort(array, begin, index - 1, cmp);
qsort(array, index + 1, end, cmp);
}
}
public void sort(Object[] array, Comparator cmp) {
qsort(array, 0, array.length - 1, cmp);
} }
[uredi] Delphi
procedure quicksort(var a:array of integer;l,r:integer);
var lpos,rpos,tmp,pivot:integer;
begin
pivot:=a[(l+r) div 2];
lpos:=l;
rpos:=r;
while lpos<=rpos do
begin
while a[lpos]<pivot do inc(lpos);
while a[rpos]>pivot do dec(rpos);
if lpos<=rpos then
begin
tmp:=a[lpos];
a[lpos]:=a[rpos];
a[rpos]:=tmp;
inc(lpos);
dec(rpos);
end;
end;
if l<rpos then quicksort(a,l,rpos);
if lpos<r then quicksort(a,lpos,r);
end;
[uredi] Visual Basic 6
Public Sub QuickSort(ByVal LB As Long, ByVal UB As Long)
Dim P1 as Long, P2 As Long
Dim Ref as String, TEMP As String
P1 = LB
P2 = UB
Ref = Feld((P1 + P2) / 2)
Do
Do While (Feld(P1) < Ref)
P1 = P1 + 1
Loop
Do While (Feld(P2) > Ref)
P2 = P2 - 1
Loop
If P1 <= P2 Then
TEMP = Feld(P1)
Feld(P1) = Feld(P2)
Feld(P2) = TEMP
P1 = P1 + 1
P2 = P2 - 1
End If
Loop Until (P1 > P2)
If LB < P2 Then Call QuickSort(LB, P2)
If P1 < UB Then Call QuickSort(P1, UB)
End Sub
[uredi] C
void quicksort(int a[], int links, int rechts) {
int li=links, re=rechts, test = a[(links + rechts)/2];
int i, swap;
printf("\n\nQuicksort-Aufruf, Testzahl ist %d\n", test);
ausgabe(links, rechts, li, re);
do {
while (a[li] < test) li++;
while (a[re] > test) re--;
if (li <= re) {
printf("Zu tauschen:\n");
ausgabe(links, rechts, li, re);
swap = a[li];
a[li] = a[re];
a[re] = swap;
li++;
re--;
printf("Nach Tausch:\n");
ausgabe(links, rechts, li, re);
}
} while (li <= re);
printf("Quicksort beendet!\n");
if (links < re) quicksort(a, links, re);
if (li < rechts) quicksort(a, li, rechts);
}
[uredi] Ruby
def quicksort(feld,links,rechts)
if (links.to_i < rechts.to_i)
m = teile(feld,links,rechts)
quicksort(feld,links,m-1)
quicksort(feld,m+1,rechts)
end
end
def teile(feld,links,rechts)
i = links-1
j = rechts
pivot = rechts
while (true) do
i = i + 1
while (feld[i].to_i<feld[pivot].to_i) do
i = i + 1
end
j = j - 1
while (feld[j].to_i>feld[pivot].to_i && j.to_i>links.to_i) do
j = j - 1
end
if (i>=j)
break
end
tausche(feld,i,j)
end
tausche(feld,i,rechts)
return i
end
def tausche(feld,a,b)
temp = feld[a]
feld[a] = feld[b]
feld[b] = temp
end
