Quicksort: Difference between revisions

Revision as of 13:20, 11 September 2014

Quick Sort

whatever

if p < r

Partition(A,p,r)

Quicksort(A,p,q - 1)

Quicksort(A,q + 1,r)

x = A[r]

i = p - 1

for j = p to r - 1

if A[j] ≤ x

i = i + 1

exchange A[i] with A[j]

exchange A[i + 1] with A[r]

return i + 1

@@ Line 8: / Line 8: @@
 <div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[https://openlearnware.tu-darmstadt.de/#!/resource/quick-sort-1945 Openlearnware]</div>
 </div>
-<syntaxhighlight lang="io" line start="1">
+==== Quicksort(''A'',''p'',''r'') ====
-Quicksort(A, p, r)
+:'''if''' ''p'' < ''r''
-if p < r
+::Partition(''A'',''p'',''r'')
- q = Partition(A, p, r)
+::Quicksort(''A'',''p'',''q'' - 1)
- Quicksort(A, p, q - 1)
+::Quicksort(''A'',''q'' + 1,''r'')
- Quicksort(A, q + 1, r)
+==== Partition(''A'',''p'',''r'') ====
-</syntaxhighlight>
+:''x'' = ''A''[''r'']
-<syntaxhighlight lang="io" line start="1">
+:''i'' = ''p'' - 1
-Partition(A, p, r)
+:'''for''' ''j'' = ''p'' '''to''' ''r'' - 1
-x = A[r]
+::'''if''' ''A''[''j''] ≤ ''x''
-i = p-1
+:::''i'' = ''i'' + 1
-for j = p to r - 1
+:::exchange ''A''[''i''] with ''A''[''j'']
- if A[j] <= x
+:exchange ''A''[''i'' + 1] with ''A''[''r'']
-  i = i + 1
+:'''return''' ''i'' + 1
-  exchange A[i] with A[j]
-exchange A[i + 1] with A[r]
-return i + 1
-</syntaxhighlight>