quickSort( A, low, high )
if( high > low )
pivot ← partition( A, low, high ) //
quickSort( A, low, pivot-1 )
quickSort( A, pivot+1, high )
|
int partition( A, low, high )
pivot_value A[low]
left ← low
pivot ← left
right ← high
while ( left < right )
// Move left while item < pivot
while( left < high && A[left] ≤ pivot_value)
left++
// Move right while item > pivot
while( A[right] > pivot_value)
right--
if( left < right ) Make sure right has not passed left
SWAP(A,left,right)
// right is final position for the pivot
A[low] ← A[right]
A[right] ← pivot_item
return right
|
quickSort(A,0,length(A)-1)
stable sorting algorithms: maintain the relative order of records with equal keys
in place algorithms: need only O(log N) extra memory beyond the items being sorted and they don't need to create auxiliary locations for data to be temporarily stored
QuickSort version above is not stable.
Question 3
Given a multi-set S of n integer elements and an index k (1 ≤ k ≤ n), we define the k-smallest element to be the k-th element when the elements are sorted from the smallest to the largest.
Suggest an O(n) on average time algorithm for finding the k-smallest element.
Example:
For the given set of numbers: 
The 4-smallest element is 2 since in the 2 is the 4’th element in the sorted set
 .
Solution:
The algorithm is based on the Quick-Sort algorithm.
Quick-Sort : //Reminder
quicksort(A,p, r)
If (p
q ← partition(A,p,r) // Partition into two parts in  time.
quicksort(A,p,q-1)
quicksort(A,q+1,r)
|
Select(k, S) // returns k-th element in S.
pick x in S
partition S into: // Slightly different variant of partition()
max(L) < x, E = {x}, x < min(G)
if k ≤ length(L) // Searching for item ≤ x.
return Select(k, L)
else if k ≤ length(L) + length(E) // Found
return x
else // Searching for item ≥ x.
return Select(k - length(L) - length(E), G)
|
In the worst case: the chosen pivot x is the maximal element in the current array and there is only one such element. G is empty  and 
The solution of the recursive equation: 
In the average case: similar to quick-sort, half of the elements in S are good pivots, for which the size of L and G are each less than  .
Therefore,  , (master theorem, case c).
Share with your friends: |
