How to Sort Arrays in C Programming

Sorting arrays is an essential skill for effective C programming. Whether organizing data for readability or implementing algorithms like search and data structures, understanding array sorting techniques can save significant time and effort. This article examines several methods for sorting arrays in C.

Bubble Sort

Bubble sort is one of the simplest sorting algorithms. It works by comparing adjacent elements and swapping them if they are out of order. This continues repeating through the array until sorted.

void bubbleSort(int arr[], int n){
  int i, j;
  for(i=0; i<n-1; i++){
    for(j=0; j<n-i-1; j++){
      if(arr[j]>arr[j+1]){
        swap(arr[j], arr[j+1]);
      }
    }
  }
}

Bubble sort has worst-case time complexity of O(n²). While simple, it is inefficient for large datasets. Bubble sort is best suited for small arrays.

Insertion Sort

Insertion sort iterates through an array, inserting each element into its correct, sorted position. Although efficient for small datasets, insertion sort also has O(n²) worst-case time complexity.

void insertionSort(int arr[], int n){
  int i, key, j;
  for(i=1; i<n; i++){
    key = arr[i];
    j = i - 1;
    while(j>=0 && arr[j]>key){
      arr[j+1] = arr[j];
      j--;
    }
    arr[j+1] = key;
  }
}

Like bubble sort, insertion sort works best with small arrays. It adapts well to datasets that are already substantially sorted.

Merge Sort

Merge sort is an efficient, divide-and-conquer algorithm. It works by recursively splitting the array in half until there are "n" single element arrays. Adjacent elements are then merged together in sorted order.

void merge(int arr[], int l, int m, int r){
  // Merge subarrays arr[l...m] and arr[m+1...r]
}

void mergeSort(int arr[], int l, int r){
  if(l < r){
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr , m+1, r);
    merge(arr, l, m, r);
  }  
}

With an overall time complexity of O(nlogn), merge sort is substantially faster than bubble and insertion sorts for large datasets. It also requires less swaps than other algorithms.

Quicksort

Quicksort uses a divide-and-conquer strategy by selecting a "pivot" element and partitioning the array into two subarrays of less than and greater than pivot. It then recursively sorts the subarrays.

int partition(int arr[], int low, int high){
  int pivot = arr[high]; 
  int i = (low - 1);
  for(int j = low; j <= high- 1; 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){
    int pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}  

Like merge sort, quicksort has an average time complexity of O(nlogn). However, its worst-case performance is O(n²). Quicksort is known for efficient sorting of large arrays and works well on average.

Conclusion

Understanding array sorting algorithms is vital for effective C programming. While bubble, insertion, and selection sorts are simple, they scale poorly to large datasets. Merge sort and quicksort are substantially faster for most applications with their O(nlogn) time complexity. Choosing the right sorting algorithm requires analyzing dataset size, efficiency requirements, and implementation complexity.