Sorting is a way of arranging items in a systematic manner.Quick sort is a sorting algorithm based on the divite and conquer approch where an array is divided into subarrays by selecting
a pivot element.Pivot is a element selected from the array.While dividing the array the pivot element should be positioned in such a way that elements less than pivot are kept on the left side and elements greater than pivot are on the side of the pivot.The process contains a single element
Working procedure:
lets take an array example
24 9 29 14 19 27
27= right
take 24 as pivot
Now arr[pivot]<arr[right]
24=arr[left]
19=arr[right]
arr[pivot]=24
because ,arr[pivot]>arr[right]
so algorithm will swap arr[pivot] with arr[right]
and pivot moves to right as
19 9 29 14 24 27
Now
arr[left]=19
arr[right]=24
arr[pivot]=24
since pvot is at right side so algorithm starts from left and moves right
as arr[pivot]>arr[left]
19 9 29 14 24 27
here
arr[left]=9
arr[right]=24
arr[pivot]=24
19 9 29 14 24 27
arr[left]= 29
arr[right]=24
arr[pivot]=24
as arr[pivot]<arr[left]
so swap arr[pivot] and arr[left] now pivot is at left
19 9 24 14 29 27
arr[left]=24
arr[right]=29
arr[pivot]=24
as arr[pivot]<arr[right]
19 9 24 14 29 27
arr[pivot]=24
arr[left]=24
arr[right]=14
as arr[pivot]>arr[right]
19 9 14 24 29 27
arr[pivot]=24
arrr[left]=14
arr[right]=24
19 9 14 24 29 27
arr[pivot]=24
arr[left]=24
arr[right]=24
19 9 14 = left sub array
29 27 = right sub array
9 14 19 24 27 29
Algorithm:
QUICKSORT(array,A,Start,end)
{
1. if(start<end)
2. {
3. p= partition(A,Start,end)
4. QUICKSORT(A,Start,p-1)
5.QUICKSORT(A,p+1,end)
6.}
}
partition algorithm:
PARTITION(array A, start, end)
{
1 pivot ? A[end]
2 i ? start-1
3 for j ? start to end -1 {
4 do if (A[j] < pivot) {
5 then i ? i + 1
6 swap A[i] with A[j]
7 }}
8 swap A[i+1] with A[end]
9 return i+1
}
Implementation:
#include <stdio.h>
int partition (int a[], int start, int end)
{
int pivot = a[end]; // pivot element
int i = (start - 1);
for (int j = start; j <= end - 1; j++)
{
// If current element is smaller than the pivot
if (a[j] < pivot)
{
i++;
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
int t = a[i+1];
a[i+1] = a[end];
a[end] = t;
return (i + 1);
}
void quick(int a[], int start, int end)
{
if (start < end)
{
int p = partition(a, start, end);
quick(a, start, p - 1);
quick(a, p + 1, end);
}
}
/* function to print an array */
void printArr(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main()
{
int a[] = { 24, 9, 29, 14, 19, 27 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
quick(a, 0, n - 1);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
output:
Before sorting array elements are -
24 9 29 14 19 27
After sorting array elements are -
9 14 19 24 27 29
Process returned 0 (0x0) execution time : 0.074 s
Press any key to continue.
0 Comments