Quick Sort

 

It is an algorithm of the divide and conquer type. That is the problem of sorting a set is reduced to the problem of sorting two smaller sets.

ALGORITHM:

Step 1 choose the highest index value as the pivot value

Step 2 take two variable to point left Android off the list excluding the pivot value

Step 3 left points to the low index

Step 4 write points to the height index

Step 5 while the value at left is less than pivot move right

Step 6 while value at the right is greater and pivot move left

Step 7 if both 5 and 6 step doesn't match swap left and right

Step 8 if the left is greater than equal to write the point where they meet in a new pivot.

PSEUDOCODE:

Step 1: [Initialize]

        TOP=NULL

Step 2: [Push boundary values of A onto stacks when A has 2 or more elements.]

        If N>1, then: TOP=TOP+1, LOWER [1] =1, UPPER[1] = N

Step 3: Repeat step 4 to 7 while TOP != NULL

Step 4: [Pop sublist from stacks]

        Set BEG=LOWER[TOP],END=UPPER[TOP]

        TOP=TOP-1

Step 5: Call QUICK(A,N,BEG,ENG,LOC)

Step 6: [Push left sublist onto stacks when it has 2 or more elements]

        If BEG<LOC-1, then

        TOP=TOP+1, LOWER[TOP]=BEG,

        UPPER[TOP]=LOC-1

Step 7: [Push right sublist onto stacks when it has 2 or more elements]

        If LOC+1<END, then

        TOP=TOP+1, LOWER[TOP]=LOC+1,

        UPPER[TOP]=END

        [End of if structure]

Step 8: Exit

PROTOTYPE CODE:

quicksort(array a, int left, int right) { if ( left < right ) { pivotindex = partition(a,left,right) quicksort(a,left,pivotindex-1) quicksort(a,pivotindex+1,right) } }

FUNCTIONING DIAGRAM

COMPLEXITY ANALYSIS:

The running time of a sorting algorithm is usually measured by the number f(n) of comparisons required to sort n elements. The algorithm has a worst-case running time of order n^2/2, but an average-case running time of order n log n. The worst case occurs when the list is already sorted. Then the first element will require n comparison to recognize that it remains in the first position. The first sublist will be empty, but the second sublist will have n-1 elements. Accordingly, the second element will require n-1 comparison to recognize that it remains in the second position, and so on.

F(n)=n+(n-1)+….+n(n+1)/2=n^2/2+O(n)=O(n^2)

STABILITY:

EXAMPLE: