Principles of Quick Sort and Merge Sort in C Language

In computer science, sorting algorithms are fundamental knowledge. Today, we will provide a detailed introduction to two commonly used sorting algorithms: Quick Sort and Merge Sort. Each of these algorithms has its advantages and disadvantages, making them suitable for different scenarios.

1. Quick Sort

1. Principle

Quick Sort is an efficient sorting algorithm that follows the Divide and Conquer strategy. It divides the array into two subarrays using an element called the “pivot,” such that all elements in the left subarray are less than the pivot, and all elements in the right subarray are greater than the pivot. It then recursively applies the same operation to these two subarrays.

2. Steps

1. Select an element from the array as the pivot.
2. Place elements smaller than the pivot to the left and those greater than the pivot to the right.
3. Repeat steps 1 and 2 for the left and right subarrays until the entire array is sorted.

3. Code Example

Below is the implementation of Quick Sort in C language:

#include <stdio.h>
void swap(int *a, int *b) {    int temp = *a;    *a = *b;    *b = temp;}
int partition(int arr[], int low, int high) {    int pivot = arr[high]; // Choose the last element as pivot    int i = (low - 1); // Index of smaller element
    for (int j = low; j < high; j++) {        if (arr[j] < pivot) {            i++;            swap(&arr[i], &arr[j]);        }    }
    swap(&arr[i + 1], &arr[high]);    return (i + 1);}
void quickSort(int arr[], int low, int high) {    if (low < high) {        // Find the partition point        int pi = partition(arr, low, high);
        // Recursively sort elements before and after partition        quickSort(arr, low, pi - 1);        quickSort(arr, pi + 1, high);    }}
void printArray(int arr[], int size) {    for (int i = 0; i < size; i++)        printf("%d ", arr[i]);    printf("\n");}
int main() {    int arr[] = {10, 7, 8, 9, 1, 5};    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Original array: \n");    printArray(arr, n);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: \n");   printArray(arr,n);   return 0;}

Output

After running the above code, you will see the following output:

Original array: 10 7 8 9 1
Sorted array: 1 5 7 8 9 10

2. Merge Sort

Principle

Merge Sort is also a Divide and Conquer strategy that splits the dataset into two halves, recursively sorts each half, and then merges the sorted halves back together.

Steps

1. Split the dataset into two halves from the middle.
2. Recursively call to continue splitting until each part has only one element.
3. Merge the sorted datasets.

C Language Implementation Code Example

Below is the implementation of Merge Sort in C language:

#include <stdio.h>
void merge(int arr[], int leftIndex,int middleIndex,int rightIndex){     int leftSize=middleIndex-leftIndex+1;     int rightSize=rightIndex-middleIndex;
     int leftArr[leftSize],rightArr[rightSize];
     for(int i=0;i<leftSize;i++)         leftArr[i]=arr[leftIndex+i];     for(int j=0;j<rightSize;j++)         rightArr[j]=arr[middleIndex+1+j];
     int i=0,j=0,k=leftIndex;
     while(i<leftSize && j<rightSize){         if(leftArr[i]<=rightArr[j]){             arr[k]=leftArr[i];             i++;         }else{             arr[k]=rightArr[j];             j++;         }         k++;     }
     while(i<leftSize){         arr[k]=leftArr[i];         i++;         k++;     }
     while(j<rightSize){          arr[k]=rightArr[j];          j++;          k++;      }}
void mergeSort(int arr[],int left,int right){    if(left<right){       int middle=(left+right)/2;
       mergeSort(arr,left,middle);         mergeSort(arr,middle+1,right);
       merge(arr,left,middle,right);     }}
void printArray(int A[],int size){    for (int i=0;i<size;i++)    printf("%d ",A[i]);    printf("\n");}
int main(){    int array[]={12 ,11 ,13 ,5 ,6 ,7};    int array_size=sizeof(array)/sizeof(array[0]);
    printf("Original array:\n");    printArray(array,array_size);
    mergeSort(array ,0,array_size-1);
    printf("\nSorted array:\n");    printArray(array,array_size);    return(0);}

Output

After running the above code, you will see the following output:

Original array: 12 11 13 5 6 7
Sorted array: 5 6 7 11 12 13

3. Summary Comparison

• Time Complexity:

• Quick Sort: Average O(n log n), Worst O(n^2)
• Merge Sort: O(n log n)

• Space Complexity:

• Quick Sort: O(log n)
• Merge Sort: O(n)

• Stability:

• Quick Sort is unstable; Merge Sort is stable.

Choosing the appropriate method based on specific needs can enhance program performance. In practical applications, both algorithms are very useful and widely used tools. We hope this article helps you gain a deeper understanding of these fundamental concepts.