Q:

C program to implement Quick Sort using Arrays

robaa
Save to bookmark
|
2022-11-25
|
  147 
0

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.

C programming, examples, C programming examples,
login and add your own answer to this question

All Answers

robaa
2022-11-25
need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

C Sorting Solved Programs – C Programming
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
C Program to implement Merge Sort using Linked Lis... >>