Quicksort is a part of Divide and
Conquer algorithm. It picks an array element as pivot and partitions the array
around the picked pivot and help to sort in ascending or descending
order.
Here I will share source code for
both ascending and descending order. If you have any query about these topics, please
comment or mail me at mazbaur15-2837@diu.edu.bd.
Source code for ascending order:
#include<stdio.h>
void swap(int* left, int* right)
{
int temp = *left;
*left = *right;
*right = temp;
}
void quicksort(int array[], int left, int right)
{
if(left <
right)
{
int pivot =
partition(array, left, right);
quicksort(array, left, pivot - 1);
quicksort(array,pivot + 1, right);
}
}
int partition(int array[], int left, int right)
{
int pivot =
array[left];
while(left != right)
{
if(pivot ==
array[left])
{
if(array[right]<pivot)
{
right
= right-1;
}
else
if(array[right] >= pivot)
{
swap(&array[left], &array[right]);
pivot
= array[right];
left =
left + 1;
}
}
else if(pivot
== array[right])
{
if(array[left] > pivot)
{
left =
left + 1;
}
else
if(array[left] <= pivot)
{
swap(&array[left], &array[right]);
pivot
= array[left];
right
= right - 1;
}
}
}
return left;
}
int main()
{
int n;
scanf("%d", &n);
int array[n];
for(int i = 0; i
< n; i++)
{
scanf("%d",&array[i]);
}
quicksort(array,
0, n - 1);
for(int i = n-1; i
>= 0; i--)
{
printf("%d ",array[i]);
}
}
Sample Input:
6
6 5 4 3 2 1
Sample Output:
1 2 3 4 5 6
Source code for descending order:
#include<stdio.h>
void swap(int* left, int* right)
{
int temp = *left;
*left = *right;
*right = temp;
}
void quicksort(int array[], int left, int right)
{
if(left <
right)
{
int pivot =
partition(array, left, right);
quicksort(array, left, pivot - 1);
quicksort(array,pivot + 1, right);
}
}
int partition(int array[], int left, int right)
{
int pivot =
array[left];
while(left != right)
{
if(pivot ==
array[left])
{
if(array[right]>pivot)
{
right
= right-1;
}
else
if(array[right] <= pivot)
{
swap(&array[left], &array[right]);
pivot
= array[right];
left =
left + 1;
}
}
else if(pivot
== array[right])
{
if(array[left] < pivot)
{
left =
left + 1;
}
else
if(array[left] >= pivot)
{
swap(&array[left], &array[right]);
pivot
= array[left];
right
= right - 1;
}
}
}
return left;
}
int main()
{
int n;
scanf("%d", &n);
int array[n];
for(int i = 0; i
< n; i++)
{
scanf("%d",&array[i]);
}
quicksort(array,
0, n - 1);
for(int i = n-1; i
>= 0; i--)
{
printf("%d ",array[i]);
}
}
Sample Input:
5
1 2 3 4 5
Sample Output:
5 4 3 2 1