// Program by Akash Tripathi (@proakash256)
// To Sort an Array using Quick Sort Technique
// Quick Sort is a Divide and Conquer Algorithm.
// It picks an Element as a pivot point,
// and partitions the given Array
// around the pivot point.
// It puts the Pivot Element at its correct position
// in the Sorted Array and puts all the
// smaller elements before and all the
// greater elements after the Pivot Element,
// depending upon Ascending or Descending.
// Now the process is repeated for the two
// partitions formed , until the Array is Sorted.
// quickSort() function (Recursive) is used
// to break the Array around the Pivot Element.
// partition() funcion brings the Pivot Element to
// its correct position in the Sorted Array and
// returns the index of the Pivot Element to quickSort()
// so that it can divide the Array around that Element.
// Algorithm :
// 1. Call partition() to get
// the index of Pivot Element.
// int partitionIndex = partition(ar , low , high)
// 2. Call quickSort() for the left side of Pivot Element
// quickSort(ar , low , (partitionIndex - 1))
// 3. Call quickSort() for the Right side of Pivot Element
// quickSort(ar , (partitionIndex + 1) , high)
// Best Case Time Complexity - O(n logn)
// (When Array is divided into exactly half)
// Worst Case Time Complexity - O(n^2) (Already Sorted)
// Space Complexity - O(n)
#include <stdio.h>
int partition(int ar[], int low, int high, char c)
{
int i, j , temp;
int pivot = ar[low];
i = low + 1;
j = high;
if (c == '1')
{
do
{
while(ar[i] <= pivot)
{
i = i + 1;
}
while(ar[j] > pivot)
{
j = j - 1;
}
if(i < j)
{
temp = ar[i];
ar[i] = ar[j];
ar[j] = temp;
}
} while (i < j);
temp = ar[low];
ar[low] = ar[j];
ar[j] = temp;
}
else if (c == '2')
{
do
{
while(ar[i] >= pivot)
{
i = i + 1;
}
while(ar[j] < pivot)
{
j = j - 1;
}
if(i < j)
{
temp = ar[i];
ar[i] = ar[j];
ar[j] = temp;
}
} while (i < j);
temp = ar[low];
ar[low] = ar[j];
ar[j] = temp;
}
return j;
}
void quickSort(int ar[], int low, int high, char c)
{
int partitionIndex;
if (low < high)
{
partitionIndex = partition(ar , low , high , c);
quickSort(ar, low, (partitionIndex - 1), c);
quickSort(ar, (partitionIndex + 1), high, c);
}
}
int main()
{
int n;
printf("Enter the number of elements you
want to enter in the array : ");
scanf("%d", &n);
int ar[n];
printf("\nEnter the elements :\n");
for (int i = 0; i < n; i = i + 1)
scanf("%d", &ar[i]);
int low = 0, high = n - 1;
printf("\nEnter 1 to Sort in Ascending Order\n");
printf("Enter 2 to Sort in Descending Order\n");
printf("Enter your Choice : ");
char c;
scanf(" %c", &c);
if (c == '1')
{
quickSort(ar, low, high, c);
}
else if (c == '2')
{
quickSort(ar, low, high, c);
}
else
printf("Sorry Wrong Choice...\n");
printf("\nThe Sorted array is :\n");
for (int i = 0; i < n; i = i + 1)
printf("%d\n", ar[i]);
return 0;
}
Comments
Post a Comment