C Programming Tutorial

### C Sorting Algorithms - Quick Sorting

Quick Sort Algorithm is an example of divide-and-conquer algorithmic technique. It is partition exchage sort.

Algorithm
• if array has zero or 1 element return it
• pick an element in the array to serve as a "pivot" point.
• Split the array into 2 sub-arrays. 1.one with larger the pivot and 2. another one is smaller than pivot
• Recursively repeat the algorithm for both halves of the original array.

Built-in qsort function is located in stdlib.h

```           void qsort(void*, size_t, size_t, int (*)(const void*, const void *));
param 1-> pointer to an array
param 2 -> size of the array
param 3 -> size of each element
param 4 -> compare function which returns a number, takes 2 input void pointers
return value is 0 if 2 inputs are equal
-1 if input 1 is less than input 2
1 if input 1 is greater than input 2
*** above logic is for Ascending Order
*** for Descending Order change return value if ip1>ip2 to 1 else -1
```
qsort using built-in function
```#include <stdio.h>
#include <stdlib.h>

int cmp(const void * n1, const void * n2)
{
// convert to appropriate  data type, here we have integer array.

int* n11 = (int*)(n1);
int* n12 = (int*)(n2);

if (*n11 == *n12) return 0;
else if(*n11 < *n12) return -1;
else return 1;
}

int main()
{

int a[]={5,1,2,3,4};
int n = sizeof(a)/sizeof(a[0]);

qsort(a,n,sizeof(int),cmp);

for (int i=0; i < n; i++) printf("%d ",a[i]);
puts("");

return 0;
}
```
Output:
```1 2 3 4 5
```
Quick Sort Custom Implementation
---------------------------------------------------------
```#include <stdio.h>

void display(char*msg,int*a);
void quick_sort(int* a);
int main(void)
{

int a[10]={1,10,20,12,15,13,78,88,99,-1};

display("before sorting...",a);
quick_sort(a);
display("After sorting...",a);

return 0;
}

void display(char*msg,int*a)
{
printf("%s  ",msg);

for(int i=0; i < 10; i++)
{

printf("%d ",a[i]);

}

printf("\n");

}

void quick_sort(int* a){

}
```
output:
```before sorting...  1 10 20 12 15 13 78 88 99 -1
After sorting...  -1 1 10 12 13 15 20 78 88 99
```

### Time and Space Complexity

space: no Auxilary space required
Time: o(nsup2)