#quick-sort-algorithm-c-python-java-example-Data-Structures

Implementation of Quick Sort Using C in Data Structures

Updated: 01/02/2023 by Computer Hope

The Quick Sort algorithm is a highly efficient sorting technique widely used in various applications due to its fast processing capabilities. Quick Sort operates on the principle of divide and conquer, breaking down a large array into smaller subarrays to efficiently organize and sort the data.

In this article, we’ll dive deep into understanding the Quick Sort algorithm, its implementation in C, and its role in the realm of data structures.

What is Quick Sort?

Quick Sort is a recursive algorithm that works by partitioning an array into two subarrays. A pivot element is chosen, and the array is divided such that:

1. One subarray contains elements smaller than the pivot.
2. The other subarray contains elements larger than the pivot.

These subarrays are then sorted recursively until the entire array is sorted. The simplicity and speed of Quick Sort make it a preferred choice for sorting large datasets.

Key Features of Quick Sort

1. Efficiency: Quick Sort is faster than many other sorting algorithms, especially for large data sizes.
2. Divide and Conquer: The algorithm splits the dataset into smaller chunks, making sorting easier and faster.
3. In-Place Sorting: Quick Sort requires minimal additional memory, making it space-efficient.

Quick Sort Algorithm in C

Below is the implementation of Quick Sort in C:

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

// Partition function to sort and position pivot
int quick(int *p, int l, int u) {
    int pos = l, t;
    while (1) {
        while (p[u] > p[pos] && pos != u)
            u--;
        if (pos == u)
            return pos;
        else {
            t = p[pos];
            p[pos] = p[u];
            p[u] = t;
            pos = u;
        }
        while (p[l] <= p[pos] && pos != l)
            l++;
        if (pos == l)
            return pos;
        else {
            t = p[pos];
            p[pos] = p[l];
            p[l] = t;
            pos = l;
        }
    }
}

// Quick Sort function
void quicksort(int *p, int n) {
    int lb = 0, ub = n - 1, pos;
    int lower[10], upper[10], top = -1;
    lower[++top] = lb;
    upper[top] = ub;
    while (top != -1) {
        lb = lower[top];
        ub = upper[top--];
        pos = quick(p, lb, ub);
        if (pos + 1 < ub) {
            lower[++top] = pos + 1;
            upper[top] = ub;
        }
        if (pos - 1 > lb) {
            lower[++top] = lb;
            upper[top] = pos - 1;
        }
    }
}

void main() {
    int x[10], i;
    clrscr();
    printf("\n Enter Array X: ");
    for (i = 0; i < 10; i++)
        scanf("%d", &x[i]);
    quicksort(x, 10); // Call to quicksort
    printf("\n After Sorting: ");
    for (i = 0; i < 10; i++)
        printf("  %d", x[i]);
}

How Quick Sort Works

1. Choose a Pivot: Select an element (usually the first or last element) as the pivot.
2. Partition: Divide the array into two subarrays based on the pivot.
3. Recursive Sorting: Apply Quick Sort recursively to the subarrays.

The recursive nature of Quick Sort ensures that the array becomes sorted efficiently.

Advantages of Quick Sort

• High Performance: The average-case time complexity of Quick Sort is $O(n \log n)$, making it faster than other sorting methods like Bubble Sort or Insertion Sort.
• Space Efficiency: Quick Sort is an in-place sorting algorithm and requires only $O(\log n)$ additional memory for recursive function calls.
• Flexibility: Can be applied to a wide variety of datasets and works well with large datasets.

Conclusion

The Quick Sort algorithm is a robust and efficient sorting technique, ideal for handling large datasets in a variety of applications. By dividing data into smaller, manageable pieces and sorting them recursively, Quick Sort delivers high performance with minimal space requirements.

Whether you are sorting numerical data, organizing strings, or implementing data structure algorithms like heaps or binary search trees, Quick Sort proves to be an invaluable tool in the programmer’s arsenal.