Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c
communitycreator

How to implement quicksort in C

221910308018

QuickSort is an in-place sorting algorithm with worst-case time complexity of n2n^{2}.

Implementation

Quicksort follows the divide and conquer algorithm. Quicksort can be done in iteratively as well as recursively, but we will be focusing on the recursive method as it is easy and simple.

First, we will partition the array about the pivot and sort the array such that the elements that are lesser than the pivot are on the left side of the pivot, and the elements that are greater than the pivot are on the right side.

Let the first element be i and the last element be j – the pivot is n. Now, we will sort the elements from i to n-1 and n+1 to j.

1 of 16

Code

We will take input in a text file for the program. In the text, we will keep -1 as the last element so that the while loop ends, as soon as it gets to -1, and sorts the elements before it. Here, -1 is the endpoint for sorting.

quick_sort.c
quicksort.txt
#include<stdio.h>
#include<stdlib.h>
void quicksort(int a[100],int first,int last)
{
    int i,j,pivot,temp;
    if(first<last)
    {
        pivot=first;
        i=first;
        j=last;
        while(i<j)
        {
            while(a[i]<=a[pivot] && i<last)
            {
                i++;
            }
            while(a[j]>a[pivot])
            {
                j--;
            }
            if(i<j)
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
        temp=a[pivot];
        a[pivot]=a[j];
        a[j]=temp;
        quicksort(a,0,j-1);
        quicksort(a,j+1,last);
    }
}
void main()
{
    FILE *ptr;
    int n,a[100],i=0,num;
    ptr=fopen("quicksort.txt","r");
        if(ptr==NULL)
            {
                printf("Unable to open the file");
                exit(0);

            }
        else{
                while((fscanf(ptr,"%d",&n))!=-1) //In text file we will take -1 as the last element so that only elements until -1 will be considered.// 
                {
                   a[i]=n;
                   i++; 
                }
                num=i-1;
                printf("elements of array are:\n");
                for(i=0;i<num;i++)
                {
                    printf("%d \n",a[i]);
                }
            }
    quicksort(a,0,num-1);
    printf("sorted elements are:\n");
    for(i=0;i<num;i++)
    {
        printf("%d\n",a[i]);
    }
}

RELATED TAGS

c
communitycreator
RELATED COURSES

View all Courses

Keep Exploring