6.10 Sorting Technique Methods

Program Definition
A Program for implementing the following sorting methods:
1. Quick sort 2. Merge sort 3. Heap sort
6.10.A Quick sort ALGORITHM:
,Quicksort splits the array into two pieces. However, Quicksort takes the additional step of placing all the low values in the left piece and all the high values in the right piece. Consequently, no merge step is needed after the two halves have been sorted. The partition() function (below) is responsible for dividing the array into two pieces.

1. Algorithm QUICK sort(p, q)
2. //sorts the elements a[p],……a[q] which
3. Reside in the global array a[1:n] into
4. ascending order; a[n+1] is considered to
5. be defined and must be greater than or equal to all the
6. elements in a[1:n]
7. {
8. if (p9. {
10. //divide p into two sub problems
11. j:= partition (a,p,q+1);
12. //j is the position of the partitioning element
13. //solve the sub problems
14. QUICK sort (p,j-1);
15. QUICK sort (j+1,q);
16. //There is no need for combining solutions
17. }
18. }


ALGORITHM FOR PARTITION
1. Algorithm partition (a, m, p);
2. //within a[m], a[m+1],…. A[p-1] the elements
3. //are rearranged in such a manner that
4. //if initially t=a[m], then after completion
5. //a[q]=t for some q between m and
6. //p-1, a[k]<=t for m<=k<=q and a[k]>=t
7. //for q8. {
9. v:= a[m]; I := m; j:= p;
10. repeat
11. {
12. repeat
13. I : =i+1;
14. until (a[j]<=v);
15. repeat
16. j: =j-1;
17. until (a[j]<=v);
18. if (i19. } until(i>=j);
20. a[m]:= a[j]; a[j]:v; return j;
21. }

ALGORITHM FOR INTERCHANGE
1. Algorithm interchange(a, I, j);
2. //exchange a[i] with a[j]
3. {
4. p:=a[j];
5. a[i]: = a[j];a[j]:=p;
6. }


Sample input and output
Output for quick sort
enter n values:5
array elements
6
7
5
8
4
the sorted array
4 5 6 7 8