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)