Data Structures using C Part 19 - Sorting | Quick sorting part 2 algorithm and program in c language
Quick Sort
#quicksort #sorting #datastructures
What is quick sort?
We use divide and Conquer approach in Quick sort.
Here First we find the pivot element from the list which divides the list into two halves such that the elements in the left half are smaller than pivot and elements in right half are greater than the pivot.
And we sort the left half and right half repeatedly until the list has been sorted.
Quick Sort Algorithm
1. TOP = -1
2. If N greater than 1, then TOP=TOP+1,
LOWER[TOP]=0,
UPPER[TOP]=N-1
3. Repeat Step 4 to 7 while (TOP != -1)
4. POP Sublist from from stack, Set BEG=LOWER[TOP],
END=UPPER[TOP],
TOP=TOP-1
5. Call Quick(A,N,BEG,END,LOC)
6. Push left sublist onto the stack, If(BEG less than LOC-1) then TOP=TOP+1
LOWER[TOP]=BEG
UPPER[TOP]=LOC-1
7. Push right sublist onto stack, If(LOC+1 less than END), then TOP=TOP+1
LOWER[TOP]=LOC+1
UPPER[TOP]=END
8. EXIT
QUICK(A,N,BEG,END,LOC)
1. Set LEFT=BEG, RIGHT=END, LOC=BEG
2. Scan from Right to Left
a) Repeat while A[LOC] less than or equal to A[RIGHT] and LOC!=RIGHT
RIGHT- -
b) If LOC==RIGHT then return
c) If A[LOC] greater than A[RIGHT], then Swap A[LOC] and A[RIGHT]
also Set LOC=RIGHT and Goto step 3
3. Scan from Left to Right
a) Repeat while A[LEFT] less than or equal to A[LOC] and LEFT != LOC
LEFT++
b) If LOC==LEFT then Return
C) If A[LEFT] greater than A[LOC] then Swap A[LOC] and A[LEFT]
also set LOC=LEFT and Goto Step 2