• Quick Sort

    Quick Sort

    Introduction:

    The Quick Sort is based on partition. It is also known as Partition Exchange sorting. The basic concept of quick sort process is pick one element from an array and rearranges the remaining elements around it. This element divides the main list into two sub lists. This chosen element is called pivot. Once pivot is chosen, then it shifts all the element less than pivot to left of value pivot and all the elements greater than pivot are shifted to the right side. This procedure of choosing pivot and partition the list is applied recursively until sub-lists consisting of only one element.

    Quick Sort Example

    Quick Sort Example

    Algorithm of Quick Sort:

    Q_SORT (Array, first, last)Where array -> Represents the list of elements;First -> Represents the position of the first elements in the list (Only at the starting point, it’s value changes during the excution of the function).

    Last -> Represents the position of the last elements in the list(Only at starting point the value of it’s changes during the execution of the function).

    Step 1: [initially]

    Low = first

    High = last

    Pivot = array[(low+high)/2] [middle elements of the elements of the list]

    Step 2: Repeat through Step 7 while (low <= high)

    Step 3: Repeat Step 4 while (array[low] < pivot)

    Step 4: low = low +1

    Step 5: Repeat Step 6 while (array[high] > pivot)

    Step 6:high = high – 1

    Step 7: if ( low<= high)

    (i)                               temp = array[low]

    (ii)                             array[low] = array[high]

    (iii)                            array[high] = temp

    (iv)                            low = low + 1

    (v)                             high = high – 1

    Step 8: if ( first < high ) Q_sort(array, first, high)

    Step 9: if ( low < lase ) Q_sort(array, low, lase)

    Step 10: exit

    Example of Quick Sort on List/Array using C Language

    #include<stdio.h>#include<stdlib.h>void quick_sort(int array[], int first, int last)

    {

    int temp, low, high, pivot;

    low = first;

    high = last;

    pivot = array[(first + lase) / 2];

    do{

    while (array[low] < pivot)

    low++;

    while (array[high] > pivot)

    high-;

    if(low <= high)

    {

    temp = array[low];

    array[low++] = array[high];

    array[high-] = temp;

    }

    }wihle(low <=high);

    if(first < high)

    quick_sort(arry, first, high);

    if (low < last)

    quick_sort(arry, low, last);

    }

    void main()

    {

    int values[100], i;

    printf(“\n Unsorted list is as follows \n”);

    for (i = 0; i < 20; i++)

    {

    values[i] = rand() % 100;

    peintf(“%d”, values[i]);

    }

    quick_sort(values, 0, 19);

    printf(“\n Sorted list as follows \n);

    for(i = 0; i < 20; i++)

    printf(“%d”, values[i]);

    }

    Appreciate my work :Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInPin on PinterestShare on RedditShare on StumbleUponShare on TumblrDigg thisShare on YummlyShare on VKFlattr the authorBuffer this page

One Responseso far.

  1. Shivam Soni says:

    Hello Sir,

    I cleared all my concepts about Data Structure. Very good & appreciable effort. Keep it up.

Leave a Reply

Your email address will not be published. Required fields are marked *