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.
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 loc← PARTITION(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
No comments:
Post a Comment
THANKS FOR UR GREAT COMMENT