vendredi 20 mars 2015

Which of these two partition algorithms (for sorting) is best for speed?


One step of the Quicksort algorithm is to partition the items against a pivot. After paritionning, all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it.


There is many in-place partition algorithms. Here is the two of them very common (see pseudocode). I never found any paper or theoritical comparaison of both of them. I'd like to know if there is any difference.


A) we move pivot to end of array, then we compare each element against pivot. If element is smaller than pivot we move it to the left. After comparing all elements we move pivot to its final place.



partition(array, low, high)
pivot = choosepivot(array, low, high)

//move pivot to end of array
swap array[pivot] and array[high]

//compare elements against pivot
storeindex = low
for i = low to high - 1
if array[i] < pivot
swap array[i] and array[storeindex]
storeindex = storeindex + 1

//move pivot to final place
swap a[storeindex] and array[high]
return storeindex




B) we start at left side of array and compare elements against pivot. We move the to right until we found an element which is bigger than pivot. We do the same starting from right side : we compare elements against pivot and we move to the left until we found an element which is smaller than pivot. From this point we have one element to the left of pivot bigger than pivot and one element to the right smaller than pivot. We swap them. We repeat the process until we left and right side has crossed (thus we have processed all element).



partition(array, low, high)
pivot = choosepivot(array, low, high)
i = low
j = high

do
//compare left side against pivot
while(i < arraysize and pivot > array[i]) i = i + 1

//compare right side against pivot
while(j >= 0 and pivot < array[j]) j = j - 1

if i < j
swap array[i] and array[j]
while i < j
return i


Here is my question : which one of these is best for performance ? Is there any difference in practice ?





Aucun commentaire:

Enregistrer un commentaire