Tuesday, 22 October 2013

Quick Sort (concept & algorithm )

Quick sort is an algorithm of the divide-and-conquer type

The problem of sorting a set  is reduced to the problem of sorting two smaller sets.

Quick Sort Approach :

To select the pivot :

Select the first number FIRST in the list, beginning with the last number in the list, scan from right to left, comparing with each number and stopping at the first number less than FIRST.  Then interchange the two number. 

Related post :bubble sort in c

Example Demo : see algorithm & example togather step by step

Quick Sort Algorithm :

Input: Unsorted sub-array A[first..last]
Output: Sorted sub-array A[first..last]

QUICKSORT (A, first, Last)
   if first < last
      then  locPARTITION(A, first, last)
           QUICKSORT (A, first, loc-1)
           QUICKSORT (A, loc+1, last)

Partition Algorithm :

Input: Sub-array A[first..last]
Output: Sub-array A[first..loc] where each element of A[first..loc-1] is ≤ to each element of A[(q+1)..r]; returns the index loc

PARTITION (A, first, last)
1    x ←  A[first]
2    i ←  first -1
3    j ← last +1
4    while  TRUE
5             repeat  j ←  j  - 1
6                  until  A[j]   ≤  x
7                 repeat   i  ←  i + 1 
8                   until   A[i]  ≥  x
9                 if    i < j 
10                 then   exchange A[i] ↔A[j]
11  else return   j

C Program for Quick sort. : quick-sort- C PROgram

No comments:

Post a Comment


Blogger Widgets