C LAB‎ > ‎(Sem2) Data Structures‎ > ‎

Qx19. WAP to perform Quick Sort.

posted May 2, 2011, 11:46 AM by Neil Mathew   [ updated May 2, 2011, 11:50 AM ]

SOURCE CODE:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<stdio.h>
 
void QuickSort(int *a, int first, int last)
{
     int low, high, pivot,temp,i;
     
     low=first;
     high=last;
     int pivot_pos= (int) (low+high)/2;
     
     pivot=a[pivot_pos];
     
printf("\n\n | First=%d | Last=%d | Pivot=%d | \n",first, last, pivot);
     
     while( low < high )
     {
      
       printf("\n Pass : ");
       for(i=first; i<=last; i++)
       printf(" %d",a[i]);
       
      
      while( a[low] < pivot )
      { low++; }
      
      while( a[high] > pivot )
      { high--;}
      
      if(low<high)
      { //swapping a[low] and a[high]
       temp=a[low];
       a[low]=a[high];
       a[high]=temp;
      }
         
     }
          
       if( first < high-1  )
       QuickSort(a,first,high-1); //last=high-1
     
       if( last > low+1 )
       QuickSort(a,low+1,last); //first=low+1
     
     
}  
 
 
int main()
{
    int i;
    int n;
    int a[20];
    
    printf("\n Enter the number of elements: ");
    scanf("%d",&n);
    
    printf("\n Enter the elements: ");
    for(i=0; i<n; i++)
    scanf("%d",&a[i]);
    
    printf("\n\n Steps in Sorting: ");
    QuickSort(a,0,n-1);
    
    printf("\n\n After Sorting:");
    for(i=0; i<n; i++)
    printf(" %d",a[i]);
    
}
 

OUTPUT:

  
 Enter the number of elements: 6

 Enter the elements: 6 0 8 2 4 10


 Steps in Sorting:

 | First=0 | Last=5 | Pivot=8 |

 Pass :  6 0 8 2 4 10
 Pass :  6 0 4 2 8 10

 | First=0 | Last=3 | Pivot=0 |

 Pass :  6 0 4 2
 Pass :  0 6 4 2

 | First=1 | Last=3 | Pivot=4 |

 Pass :  6 4 2
 Pass :  2 4 6

 After Sorting: 0 2 4 6 8 10






Comments