C program to implement Quick Sort using Arrays

By | 10.10.2016

Quick Sort using Arrays


Write a C program to implement Quick Sort using Arrays. Here’s simple C program to implement Quick Sort using Arrays in C Programming Language.


Quick sort is a divide and conquer algorithm. Quick sort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quick sort can then recursively sort the sub-lists.

In c quick sort we take the one element called as pivot,then we list all the smaller elements than pivot, and greater than pivot. after partitioning we have pivot in the final position. After recursively sorting the partition array, we get the sorted elements.


C Quick Sort Algorithm : 


  1. If n < = 1, then return.
  1. Pick any element V in a[]. This is called the pivot.
  1. Rearrange elements of the array by moving all elements xi > V right of V and all elements x­i < = V left of V. If the place of the V after re-arrangement is j, all elements with value less than V, appear in a[0], a[1] . . . . a[j – 1] and all those with value greater than V appear in a[j + 1] . . . . a[n – 1].
  1. Apply quick sort recursively to a[0] . . . . a[j – 1] and to a[j + 1] . . . . a[n – 1].

Complexity : :

Best Case – O(n log n) 

Worst Case – O(n^2)

Average Case – O(n log n)

It is comparison sort which works on divide and conquer technique. It is in-place partitioning algorithm and one of the fastest sorting techniques available till date.


Here is the source code of the C program to implement Quick Sort using Arrays. The C program is successfully compiled and run(Codeblocks) on a Windows system. The program output is also shown below.


SOURCE CODE : :


/*  C program to implement Quick Sort using Arrays  */

#include<stdio.h>

void quicksort(int [],int,int);

int main(){
  int size,i;

  printf("Enter size of the array: ");
  scanf("%d",&size);

  int x[size];

  printf("Enter %d elements: ",size);
  for(i=0;i<size;i++)
    scanf("%d",&x[i]);

  quicksort(x,0,size-1);

  printf("Sorted elements: ");
  for(i=0;i<size;i++)
    printf(" %d",x[i]);

  return 0;
}

void quicksort(int x[],int first,int last){
    int pivot,j,temp,i;

     if(first<last){
         pivot=first;
         i=first;
         j=last;

         while(i<j){
             while(x[i]<=x[pivot]&&i<last)
                 i++;
             while(x[j]>x[pivot])
                 j--;
             if(i<j){
                 temp=x[i];
                  x[i]=x[j];
                  x[j]=temp;
             }
         }

         temp=x[pivot];
         x[pivot]=x[j];
         x[j]=temp;
         quicksort(x,first,j-1);
         quicksort(x,j+1,last);

    }
}

OUTPUT : :


/*  C program to implement Quick Sort using Arrays  */

Enter size of the array: 10

Enter 10 elements: 

5
8
1
2
0
4
9
2
3
7

Sorted elements:  0 1 2 2 3 4 5 7 8 9

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.


Thanks for reading the post….

5 2 votes
Article Rating
Category: C Programming Sorting Programs Tags:

About Tunde A

My name is Tunde Ajetomobi, a Tech Enthusiast and Growth Hacker. I enjoy creating helpful content that solves problem across different topics. Codezclub is my way of helping young aspiring programmers and students to hone their skills and find solutions on fundamental programming languages.

Subscribe
Notify of
guest
0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments