Quicksort: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
No edit summary
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 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>
</div>
==== Invariant ====
At the beginning of each iteration of the loop of lines 3-6, for any array index ''k'',
:1. If ''p'' ≤ ''k'' ≤ ''i'', then ''A''[''k''] ≤ x.
:2. If ''i'' +1 ≤ ''k'' ≤ ''j'' - 1, then ''A''[''k''] > x
:3. If ''k'' = ''r'', then ''A''[''k''] = ''x''
==== Initialization ====
Prior to the first iteration of the loop, ''i'' = ''p'' -1 and ''j'' = ''p''. Because no values lie between ''p'' and ''i'' and no values lie between ''i'' +1 and ''j'' -1, the first two conditions of the loop invariant are trivially satisfied. The assignment in line 1 satifies the third condition.
==== Quicksort(''A'',''p'',''r'') ====
:'''if''' ''p'' < ''r''
::Partition(''A'',''p'',''r'')
::Quicksort(''A'',''p'',''q'' - 1)
::Quicksort(''A'',''q'' + 1,''r'')
==== Partition(''A'',''p'',''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
==== Example ====
{|
|aaa
|aaa
|aasas
|-
|bbbb
|kdas
|kdas


== General Information ==
'''Algorithmic problem:''' [[Sorting based on pairwise comparison]]


|}
'''Type of algorithm:''' recursion
 
== Abstract View ==
 
'''Invariant:''' After a recursive call, the input sequence of this recursive call is sorted.
 
'''Variant:''' In each recursive call, the sequence of the callee is strictly shorter than that of the caller.
 
'''Break condition:''' The sequence is empty or a singleton.
 
== Induction Basis ==
 
'''Abstract view:''' Nothing to do on an empty sequence or a singleton.
 
'''Implementation:''' Ditto.
 
'''Proof:''' Empty sequences and singletons are trivially sorted.
 
== Induction Step ==
 
== Complexity ==
 
== Further Information ==

Revision as of 13:26, 2 October 2014

Quick Sort
whatever

General Information

Algorithmic problem: Sorting based on pairwise comparison

Type of algorithm: recursion

Abstract View

Invariant: After a recursive call, the input sequence of this recursive call is sorted.

Variant: In each recursive call, the sequence of the callee is strictly shorter than that of the caller.

Break condition: The sequence is empty or a singleton.

Induction Basis

Abstract view: Nothing to do on an empty sequence or a singleton.

Implementation: Ditto.

Proof: Empty sequences and singletons are trivially sorted.

Induction Step

Complexity

Further Information

Retrieved from "https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Quicksort&oldid=582"