Quick Sort Alogorithm With C Programming

ALGORITHM FOR QUICK SORT

1.) Make a list of items that need to be sorted, lets apply in an array.

2.) Choose any element as pivot element from the array list.

3.) Rearrange the array list so that all the elements with value less than the pivot will come before the pivot and the element with value greater will come after the pivot with in the same array, which make pivot element in the sorted position.

4.) Apply recursively the 3rd step to the sub array of the element with smaller values and separate the sub array of the elements with the greater values.

C PROGRAM FOR QUICK SORT

#include<stdio.h>
#include<conio.h>

//quick Sort function to Sort Integer array list
void quicksort(int array[], int firstIndex, int lastIndex)
{
    //declaaring index variables
    int pivotIndex, temp, index1, index2;

    if(firstIndex < lastIndex)
    {
        //assigninh first element index as pivot element
        pivotIndex = firstIndex;
        index1 = firstIndex;
        index2 = lastIndex;

        //Sorting in Ascending order with quick sort
        while(index1 < index2)
        {
            while(array[index1] <= array[pivotIndex] && index1 < lastIndex)
            {
                index1++;
            }
            while(array[index2]>array[pivotIndex])
            {
                index2--;
            }

            if(index1<index2)
            {
                //Swapping opertation
                temp = array[index1];
                array[index1] = array[index2];
                array[index2] = temp;
            }
        }

        //At the end of first iteration, swap pivot element with index2 element
        temp = array[pivotIndex];
        array[pivotIndex] = array[index2];
        array[index2] = temp;

        //Recursive call for quick sort, with partiontioning
        quicksort(array, firstIndex, index2-1);
        quicksort(array, index2+1, lastIndex);
    }
}

int main()
{
    //Declaring variables
    int array[100],n,i;

    //Number of elements in array form user input
    printf("Enter the number of element you want to Sort : ");
    scanf("%d",&n);

    //code to ask to enter elements from user equal to n
    printf("Enter Elements in the list : ");
    for(i = 0; i < n; i++)
    {
        scanf("%d",&array[i]);
    }

    //calling quickSort function defined above
    quicksort(array,0,n-1);

    //print sorted array
    printf("Sorted elements: ");
    for(i=0;i<n;i++)
    printf(" %d",array[i]);

    getch();
    return 0;
}