Implement quick sort using array |Data Structure in C|

Introduction

     Sorting is a fundamental operation in computer science, and various algorithms address this task efficiently. One such algorithm is Quick Sort, known for its speed and effectiveness. In this blog post, we'll explore a C program that implements Quick Sort to sort an array of elements. We'll break down the code and understand how Quick Sort efficiently rearranges elements, making it a popular choice for sorting large datasets.  

Code

    
     
    #include<stdio.h>
    #include<conio.h>
    
    void quick_sort(int[], int, int);
    int partition(int[], int, int);

    void main() {
        int a[50], n, i;
        clrscr();

        // Input
        printf("How many elements: ");
        scanf("%d", &n);
        printf("Enter the array elements: ");
        for (i = 0; i < n; i++)
            scanf("%d", &a[i]);

        // Sorting
        quick_sort(a, 0, n - 1);

        // Output
        printf("\nArray after sorting:\n");
        for (i = 0; i < n; i++)
            printf("%d\n", a[i]);

        getch();
    }

    void quick_sort(int a[], int l, int u) {
        int j;
        if (l < u) {
            j = partition(a, l, u);
            quick_sort(a, l, j - 1);
            quick_sort(a, j + 1, u);
        }
    }

    int partition(int a[], int l, int u) {
        int v, i, j, temp;
        v = a[l];
        i = l;
        j = u + 1;

        do {
            do
                i++;
            while (a[i] < v && i <= u);

            do
                j--;
            while (v < a[j]);

            if (i < j) {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        } while (i < j);

        a[l] = a[j];
        a[j] = v;
        return (j);
    }
       
     

Output

    How many elements: 6
    Enter the array elements: 3 1 6 2 4 5

    Array after sorting:
    1
    2
    3
    4
    5
    6
       

Explanation

1. Header Files:

The program includes the standard input/output header <stdio.h> and the console input/output header <conio.h>.

2. Function Prototypes:

Two functions are declared - quick_sort for the main sorting logic and partition for the partitioning step.

3. Main Function:

The main function serves as the entry point of the program.

Users input the number of elements and the array itself.

4. Quick Sort Algorithm:

The quick_sort function recursively calls itself to sort subarrays.

The partition function identifies a pivot and rearranges elements around it.

5. Input and Output:

The program inputs elements, sorts them using Quick Sort, and displays the sorted array.

Conclusion

     Quick Sort stands out for its speed and efficiency in sorting large datasets. This C program exemplifies the implementation of Quick Sort, providing a practical illustration of the algorithm's effectiveness in rearranging elements. Feel free to run the program with different sets of elements to observe how Quick Sort efficiently sorts the array in ascending order. This example serves as a valuable introduction to the Quick Sort algorithm in C. Happy coding!