Quick sort

In Quick sort algorithm ,main array is divided into sub-arrays using divide and conquer approach and they are called recursively

1)pick a key element in an array and lets call it pivot (in this example we take last element as a pivot)

2)pivot should divide the array into sub arrays where left sub array should be lesser than pivot and right sub array should be greater than the pivot

3)for the left sub and right sub array apply the same algorithm pick a pivot and array its sub array to left and right

Worst Case Time Complexity [ Big-O ]: O(n2)

Best Case Time Complexity [Big-omega]: O(n*log n)

Average Time Complexity [Big-theta]: O(n*log n)

Space Complexity: O(n*log n)

Program for Merge sort#

#include<stdio.h>
void quicksort(int number[25], int first, int last) {
int i, j, pivot, temp;
if (first < last) {
pivot = first;
i = first;
j = last;
while (i < j) {
while (number[i] <= number[pivot] && i < last)
i++;
while (number[j] > number[pivot])
j--;
if (i < j) {
temp = number[i];
number[i] = number[j];
number[j] = temp;
}
}
temp = number[pivot];
number[pivot] = number[j];
number[j] = temp;
quicksort(number, first, j - 1);
quicksort(number, j + 1, last);
}
}
int main() {
int i, count, number[25];
printf("Enter some elements (Max. - 25): ");
scanf("%d", & count);
printf("Enter %d elements: ", count);
for (i = 0; i < count; i++)
scanf("%d", & number[i]);
quicksort(number, 0, count - 1);
printf("The Sorted Order is: ");
for (i = 0; i < count; i++)
printf(" %d", number[i]);
return 0;
}