Source Code
#include<stdio.h>
#include<stdlib.h>
void swap(int *list, int left, int right) {
int temp;
temp = list[left];
list[left] = list[right];
list[right] = temp;
}
void quicksort(int *list, int low, int high) {
int pivot, i;
if(high>low)
{
pivot=partition(list, low, high);
/*when pivot is correctly placed at the position this means left subarray elements are less
than pivot and right subarray elements are greater than pivot*/
quicksort(list, low, pivot - 1); /*divide and conquer repeatedly until all the elements are arranged*/
quicksort(list, pivot + 1, high);
}
}
int partition(int *list, int low, int high) {
int left, right;
int pv_item;
int pivot = left = low;
pv_item = list[low]; /*first positional element is taken as pivot*/
right = high;
while(left<right)
{
while(list[left]<=pv_item) /*left pointer will move towards right unless it finds an element which is greater or equal to pivot.Take that position*/
left++;
while(list[right]>pv_item) /*right pointer will move towards left unless it finds an element which is less than pivot.Take that position*/
right--;
if(left<right)
swap(list, left, right); /*postion of left pointer and position of right pointer will be swapped*/
}
/*if it is found that right pointer positional index is lower than right pointer positional index then swap pivot with right pointer's position*/
list[low] = list[right];
list[right] = pv_item;
return right;
}
int main() {
int *list, i, n;
printf("\nenter the no of elements:");
scanf("%d",&n);
list = (int*) malloc(sizeof(int) * n);
printf("\nenter the values:");
for(i=0;i<n;i++)
scanf("%d",&list[i]);
quicksort(list, 0, n - 1);
for(i=0;i<n;i++)
printf("%d ",list[i]);
return 0;
}
Posts
No comments:
Post a Comment