Understanding Different Types of Sorting Algorithms

Introduction

Different types of sorting techniques are fundamental concepts in computer science that arrange data into a particular order, such as numerical order or lexicographic order. Efficient sorting is critical for optimising data retrieval, reducing search times, and streamlining many computational processes. This article provides a comprehensive overview of common types of sorting algorithms, their runtime complexity, advantages, use cases, and applications.

Fundamental Concepts

Sorting refers to algorithms that rearrange elements of a dataset into a specified order, such as ascending or descending. Sorting enables efficient searching, ordering, and selection operations to be performed on data.

The importance of efficient sorting cannot be understated. It enables databases to quickly order and retrieve records, search engines to return relevant results faster, and analytics applications to process data effectively.

Comparison Vs Non Comparison Based Types Of Sorting Algorithms

Types of Sorting algorithms are generally classified into comparison and non-comparison based algorithms. Comparison sorts evaluate the relative order of elements by directly comparing them. Non-comparison sorts use techniques like bucketing, counting Occurrences, or extracting digits to indirectly determine sort order.

Types of Sorting Algorithms

Elementary Sorting Algorithms

Elementary sorting algorithms conceptually demonstrate sorting, but have quadratic time complexity which limits efficiency.

Here are detailed explanations of bubble sort, selection sort, and insertion sort algorithms along with example working code implementations in Java, C, C++, and Python:

Bubble Sort

Bubble sort works by comparing adjacent elements in a list and swapping them if they are not in the intended order. This process is repeated until no more swaps are required, indicating the list is sorted.

Algorithm

Pseudocode

// PseudoCode For Bubble Sort

bubbleSort(arr[]):

  n = length(arr)

  for i = 0 to n-1 do:

    for j = 0 to n-i-1 do:

      if arr[j] > arr[j+1] 
        swap(arr[j], arr[j+1])

Walkthrough

Properties

• Time Complexity: O(n2) worst and average case.
• Space Complexity: O(1), in-place sorting.
• Stable sorting algorithm.
• Simple implementation but highly inefficient for large data sets.

Code Examples

Java

// Types of Sorting algorithms : Bubble Sort  Code in Java

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

C

// Types of Sorting algorithms : Bubble Sort  Code in C

void bubbleSort(int arr[], int n){

  for(int i=0; i<n-1; i++){
    for(int j=0; j<n-i-1; j++){
      if(arr[j] > arr[j+1]){
        // swap elements
        int temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
}

C++

// Types of Sorting algorithms :  Bubble Sort  Code in C++

void bubbleSort(int arr[], int n){

  for(int i=0; i<n-1; i++){
    for(int j=0; j<n-i-1; j++){
      if(arr[j] > arr[j+1]){
        // swap elements 
        int temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
}

Python

# Types of Sorting algorithms :  Bubble Sort  Code in Python

def bubbleSort(arr):
  n = len(arr)

  for i in range(n-1):
    for j in range(n-i-1):
      if arr[j] > arr[j+1]:
        # swap elements
        arr[j], arr[j+1] = arr[j+1], arr[j]

Selection Sort

Selection sort selects the minimum element from the unsorted portion in each pass and places it at the end of the sorted portion.

Algorithm

Pseudocode

//PseudoCode for Selection Sort

selectionSort(arr[]):

  n = length(arr)

  for i = 0 to n-1 do:

    minIndex = i

    for j = i+1 to n do:

      if arr[j] < arr[minIndex]
        minIndex = j

    swap(arr[i], arr[minIndex]) 

Walkthrough

Properties

• Time Complexity: O(n2) worst and average case.
• Space Complexity: O(1), in-place sorting.
• Unstable sorting algorithm.
• Simple implementation but inefficient for large data sets.

Code Examples

Java

// Types of Sorting algorithms: Selection Sort Code In Java

void selectionSort(int arr[]) {
   int n = arr.length;
   for(int i=0; i<n-1; i++) {
     int min = i;
     for(int j=i+1; j<n; j++){
       if(arr[j] < arr[min]) {
         min = j;
       }
     }
     // Swap min element with first element
     int temp = arr[min];
     arr[min] = arr[i];
     arr[i] = temp;
   }
}

C

// Types of Sorting algorithms: Selection Sort Code In C

void selectionSort(int arr[], int n) {
  int i, j, min;

  for(i=0; i<n-1; i++) {
    min = i;
    for(j=i+1; j<n; j++){
      if(arr[j] < arr[min]) {
        min = j;
      }
    }  
    // Swap min element with first element
    int temp = arr[min];
    arr[min] = arr[i];
    arr[i] = temp;
  }
}

C++

// Types of Sorting algorithms: Selection Sort Code In C++
void selectionSort(int arr[], int n){

  for(int i=0; i<n-1; i++){
    int min = i;
    for(int j=i+1; j<n; j++){
      if(arr[j] < arr[min]){
        min = j;  
      }
    }
    // Swap min element with first element
    int temp = arr[min];
    arr[min] = arr[i];
    arr[i] = temp;
  }
}

Python

# Types of Sorting algorithms: Selection Sort Code In Python

def selectionSort(arr):

  for i in range(len(arr)-1):
    min = i
    for j in range(i+1, len(arr)):
      if arr[j] < arr[min]:
        min = j
    # Swap minimum with first element        
    arr[i], arr[min] = arr[min], arr[i]

Insertion Sort

Insertion sort is a simple sorting algorithm that works by inserting each element into its correct position in the sorted portion of an array.

Algorithm

Pseudocode

// Types of Sorting techniques: Psuedocode for Insertion Sort

For i = 1 to n-1
  key = arr[i]
  j = i-1

  While j >= 0 and arr[j] > key
    arr[j+1] = arr[j] 
    j = j-1

  arr[j+1] = key

Walkthrough

Properties

• Space complexity: O(1), in-place sorting
• Stable sorting algorithm
• Adaptive algorithm – efficient for partially sorted data
• Best Case: O(n) – Array is already sorted
• Average Case: O(n^2)
• Worst Case: O(n^2)

Insertion sort is simple to implement but inefficient for large data sets. It is more efficient than bubble sort and selection sort. The algorithm is stable and adaptive, making it useful in practice, especially when data is mostly sorted.

Code Example

Java

// Types of Sorting techniques: Insertion Sort Code in Java

void insertionSort(int arr[]) {
  for(int i=1;i<arr.length;i++){
    int temp = arr[i];
    int j = i-1;
    while(j>=0 && arr[j]>temp){
      arr[j+1] = arr[j];
      j--;
    }
    arr[j+1] = temp;
  }
}

C

//  Types of Sorting techniques: Insertion Sort Code in C

void insertionSort(int arr[], int n){

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

C++

// Types of Sorting techniques: Insertion Sort Code in C++ 
void insertionSort(int arr[], int n){

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

Python

#  Types of Sorting techniques: Insertion Sort Code in Python

def insertionSort(arr):

  for i in range(1, len(arr)):
    temp = arr[i]
    j = i-1
    while j>=0 and arr[j]>temp:
      arr[j+1] = arr[j]
      j -= 1
    arr[j+1] = temp

Efficient Sorting Algorithms

Efficient algorithms use techniques like divide-and-conquer to achieve improved time complexities compared to elementary algorithms.

Merge Sort

Merge sort works by recursively splitting the array into halves, sorting each half, and merging them back together in sorted order.

Algorithm

PseudoCode

//  Types of Sorting techniques: PseudoCode for Merge Sort

mergeSort(arr[], left, right):

  if right > left:

    mid = (left + right)/2

    mergeSort(arr, left, mid)

    mergeSort(arr, mid+1, right)

    merge(arr, left, mid, right)


merge(arr[], left, mid, right):

  create temp arrays L[] and R[] 

  copy arr elements to L[] and R[]

  i = j = k = 0

  while i < n1 and j < n2:

    if L[i] <= R[j]:

      arr[k] = L[i]
      i++

    else:

      arr[k] = R[j]
      j++

    k++

  copy remaining elements of L[] and R[] to arr[] 

Walkthrough

Properties

• Space complexity: O(n) auxiliary
• Stable sorting algorithm
• In-place merging is complex
• Worst case performance: O(nlogn)

Overall, merge sort is an efficient, stable sorting algorithm optimal for larger datasets. Its divide and conquer strategy reduces time complexity.

Code Examples

Java

//  Types of Sorting techniques: Merge Sort Code in Java

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);
  }
}

void merge(int arr[], int l, int m, int r) {
  // Merge code
}

C

//  Types of Sorting techniques: Merge Sort Code in C 
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); 
  }
}

void merge(int arr[], int l, int m, int r){
  // Merge code
}

C++

//  Types of Sorting techniques: Merge Sort Code in C++
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);
  }  
}

void merge(int arr[], int l, int m, int r){
   // Merge code 
}

Python

#  Types of Sorting techniques: Merge Sort Code in Python

def mergeSort(arr,l,r):
  if l < r:
    m = (l+(r-1))//2
    mergeSort(arr, l, m)
    mergeSort(arr, m+1, r)
    merge(arr, l, m, r)

def merge(arr, l, m, r):
  # Merge code  

Quicksort

Quicksort is an efficient divide and conquer sorting algorithm. It works by selecting a ‘pivot’ element and partitioning the array around it such that elements less than the pivot are to the left and greater elements are to the right.

Algorithm

Pseudocode

//  Types of Sorting techniques: Pseudocode for QuickSort

quickSort(arr[], low, high) {

  if (low < high) {

    pivotIndex = partition(arr, low, high) 

    quickSort(arr, low, pivotIndex)

    quickSort(arr, pivotIndex + 1, high)
  }
}

partition(arr[], low, high) {

  // Partitioning logic

  return pivotIndex; 
}

Walkthrough

Properties

• Time Complexity:
• Best case: O(nlogn)
• Average case: O(nlogn)
• Worst case: O(n^2)
• Space Complexity: O(logn)
• In place sorting algorithm
• Unstable sorting algorithm

Quicksort is efficient in practice, provides good average case performance and extra space usage is only for recursive calls. However, worst case is quadratic making it unsuitable for certain scenarios.

Code Examples

Java

//  Types of Sorting techniques: Quick Sort Java Program

void quickSort(int arr[], int low, int high) {
  if (low < high) {
    int pivot = partition(arr, low, high);

    quickSort(arr, low, pivot-1);
    quickSort(arr, pivot+1, high);
  }
}

int partition(int arr[], int low, int high) {
  int pivot = arr[high]; 
  int i = (low-1);

  for (int j=low; j<high; j++) {
    if (arr[j] <= pivot) {
      i++;
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }

  int temp = arr[i+1];
  arr[i+1] = arr[high];
  arr[high] = temp;

  return i+1;
}

C++

//  Types of Sorting techniques: Quick Sort Java Program C++

void quickSort(int arr[], int low, int high) {
  if (low < high) {
    int pivot = partition(arr, low, high);

    quickSort(arr, low, pivot-1); 
    quickSort(arr, pivot+1, high);
  }
}

int partition (int arr[], int low, int high) {
  int pivot = arr[high];
  int i = (low - 1);

  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);
}

C

//  Types of Sorting techniques: Quick Sort Java Program C

void quickSort(int arr[], int low, int high){
  if (low < high) {
    int pivot = partition(arr, low, high);

    quickSort(arr, low, pivot-1);  
    quickSort(arr, pivot+1, high);
  }
}

int partition (int arr[], int low, int high) {
  int pivot = arr[high];
  int i = (low - 1);

  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);
}

Python

//  Types of Sorting techniques: Quick Sort Java Program Python 

def quickSort(arr, low, high):
  if low < high:
    pivot = partition(arr, low, high)

    quickSort(arr, low, pivot-1)
    quickSort(arr, pivot+1, high)

def partition(arr, low, high):
  pivot = arr[high]
  i = low-1

  for j in range(low, high):
    if arr[j] <= pivot:
      i += 1
      arr[i], arr[j] = arr[j], arr[i]

  arr[i+1], arr[high] = arr[high], arr[i+1]
  return i+1

Heapsort

Heapsort uses a binary heap data structure to efficiently sort an array. It converts the array into a max heap, repeatedly extracts the maximum element, and places it at the end of the array.

Algorithm Of Heap Sort

Pseudocode

 // Types of Sorting techniques : PseudoCode and algorithm of heap sort

heapSort(arr):

  buildMaxHeap(arr)

  for i = n to 1:

    swap arr[1] and arr[i] 

    heapify(arr, 1, i-1)

buildMaxHeap(arr):

  for i = n/2 to 1:

    heapify(arr, i, n) 

heapify(arr, i, n):

  largest = i 

  l = 2*i, r = 2*i + 1

  if l <= n and arr[l] > arr[largest]:

    largest = l

  if r <= n and arr[r] > arr[largest]: 

    largest = r

  if largest != i:

    swap arr[i] and arr[largest]

    heapify(arr, largest, n)

Walkthrough

The heapsort algorithm efficiently sorts the array in O(nlogn) time by exploiting the heap data structure.

Code Examples

Java

//  Types of Sorting algorithms : Heap Sort 

void heapSort(int[] arr, int n) {
  // heapify 
  for (int i = n/2 - 1; i >= 0; i--) 
    heapify(arr, n, i);

  // extract elements
  for (int i=n-1; i>=0; i--) { 
    int temp = arr[0];
    arr[0] = arr[i]; 
    arr[i] = temp;
    heapify(arr, i, 0);
  }
}

C++

// Heap Sort C++
void heapSort(int arr[], int n) {
  // heapify
  for (int i = n/2 - 1; i >= 0; i--)
    heapify(arr, n, i);

  // extract elements
  for (int i=n-1; i>=0; i--) {
    int temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    heapify(arr, i, 0);
  } 
}

C

// Heap Sort in C

void heapSort(int arr[], int n) {
  
  // heapify
  for (int i = n/2 - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // extract elements
  for (int i=n-1; i>=0; i--) {
    int temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    heapify(arr, i, 0);
  }
}

Python

# Heap Sort
def heapify(arr, n, i):
  # heapify logic

def heapSort(arr):
  n = len(arr)

  # heapify
  for i in range(n//2 - 1, -1, -1):
    heapify(arr, n, i)

  # extract elements
  for i in range(n-1, 0, -1):
    arr[i], arr[0] = arr[0], arr[i] 
    heapify(arr, i, 0)

Non-Comparison Based Sorting

Non-comparison sorts use alternative techniques like counting, radixes, or bucketing. These allow improved efficiency for certain data types.

Here are detailed explanations of counting sort, bucket sort, radix sort, timsort and shellsort algorithms including the algorithm, walkthrough and properties:

Counting Sort

Counting sort is an efficient non-comparison sorting algorithm that sorts elements in linear time by determining the count of each unique element in the array.

Algorithm

Pseudocode

//  Types of Sorting algorithms: Pseudocode for counting sort

countSort(array):

  max = find largest element in array
  min = find smallest element in array

  count = create array of size (max-min+1) with all 0s

  for each element in array:
    count[element]++

  for i = 1 to max-min: 
    count[i] += count[i-1]

  for i = n-1 to 0:
    output[count[array[i]]-1] = array[i]
    count[array[i]]--

  return output

Walkthrough

Code Examples

Java

//  Types of Sorting algorithms: Counting Sort In Java

void countingSort(int[] arr) {
  int max = Arrays.stream(arr).max().getAsInt();
  int min = Arrays.stream(arr).min().getAsInt();
  int range = max - min + 1;
  int count[] = new int[range];
  int output[] = new int[arr.length];
  // count occurrences
  for (int i = 0; i < arr.length; i++) {
    count[arr[i] - min]++;
  }
  // cumulative count 
  for (int i = 1; i < count.length; i++) {
    count[i] += count[i - 1];
  }
  // fill output array
  for (int i = arr.length - 1; i >= 0; i--) {
    output[count[arr[i] - min] - 1] = arr[i];
    count[arr[i] - min]--;
  } 
}

C++

//  Types of Sorting algorithms: Counting Sort In C++

void countingSort(int arr[], int n) {
  int max = *max_element(arr, arr+n);
  int min = *min_element(arr, arr+n);
  int range = max - min + 1;
  int count[range], output[n];
  fill(count, count + range, 0);

  // store counts
  for (int i = 0; i < n; i++)
    count[arr[i]-min]++;
  
  // cumulative counts
  for (int i = 1; i < range; i++) 
    count[i] += count[i-1];

  // fill output array
  for (int i = n-1; i >= 0; i--) {
    output[count[arr[i]-min]-1] = arr[i];
    count[arr[i]-min]--;
  }
}

C

//  Types of Sorting algorithms: Counting Sort In C

void countingSort(int arr[], int n) {
  
  int max = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] > max) 
      max = arr[i];
  }

  int min = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] < min)
      min = arr[i]; 
  }

  int range = max - min + 1;
  int count[range];
  int output[n];

  for (int i = 0; i < range; i++) {
    count[i] = 0;
  }

  // store counts of each element
  for (int i = 0; i < n; i++) {
    count[arr[i] - min]++; 
  }

  // cumulative counts
  for (int i = 1; i < range; i++) {
    count[i] += count[i - 1];
  }

  // fill output array
  for (int i = 0; i < n; i++) {
    output[count[arr[i] - min] - 1] = arr[i];
    count[arr[i] - min]--; 
  }
}

Python

#  Types of Sorting algorithms: Counting Sort  In Python

def countingSort(arr):
  max_val = max(arr)
  min_val = min(arr)
  range_val = max_val - min_val + 1

  count = [0 for _ in range(range_val)]
  output = [0 for _ in range(len(arr))]

  # store count of each element
  for i in arr:
    count[i-min_val] += 1
  
  # cumulative counts
  for i in range(1, len(count)):
    count[i] += count[i-1]

  # fill output array
  for i in range(len(arr)-1, -1, -1):
    output[count[arr[i] - min_val] - 1] = arr[i]
    count[arr[i] - min_val] -= 1

  for i in range(len(arr)):
    arr[i] = output[i]

Properties:

• Time Complexity: O(n+k) where n is number of elements, k is range of input
• Space Complexity: O(n+k) for count array
• Stable sorting algorithm
• Efficient for small integer keys within a specific range
• Not in-place, requires extra memory

Counting sort works well for sorting small positive integers with a tight range by exploiting the frequency data of input elements.

Bucket Sort

Bucket sort partitions elements into buckets representing ranges, then sorts each bucket individually.

Algorithm

Pseudocode

//  Types of Sorting algorithms: Pseudocode for bucketsort

bucketSort(array, k):

// k is the number of buckets 

initialize k empty buckets  

for each element in array:

  insert element into appropriate bucket

for i = 1 to k:

  sort elements in bucket i using insertion sort

concatenate sorted buckets 

return concatenated array

Walkthrough

Properties

• Time Complexity: O(n+k)
• Space Complexity: O(n+k)
• Stable sort based on sub-sort

Bucket allows sorting of floats and non-uniform distributions efficiently.

Code Examples

Java

//  Types of Sorting algorithms: Bucket Sort In Java

void bucketSort(float[] arr) {
  int n = arr.length;
  @SuppressWarnings("unchecked")
  List<Float>[] buckets = new List[n];

  // initialize buckets  
  for (int i = 0; i < n; i++) {
    buckets[i] = new ArrayList<>(); 
  }

  // distribute elements into buckets
  for (int i = 0; i < n; i++) {
    int bucketIdx = (int)arr[i] * n;
    buckets[bucketIdx].add(arr[i]);
  }

  // sort individual buckets
  for (int i = 0; i < n; i++) {
    Collections.sort(buckets[i]);
  }

  // concatenate buckets
  int index = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0, size = buckets[i].size(); j < size; j++) {
      arr[index++] = buckets[i].get(j);
    }
  }
}

C

//  Types of Sorting algorithms: Bucket Sort In C

void bucketSort(float arr[], int n) {

  int i, j;
  float buckets[n][n];

  // put elements into buckets
  for (i = 0; i < n; i++) {
    int bucketIdx = n * arr[i];
    buckets[bucketIdx][j++] = arr[i]; 
  }

  // sort individual buckets
  for (i = 0; i < n; i++) {
    qsort(buckets[i], j, sizeof(float), compare); 
  }

  // concatenate buckets
  j = 0; 
  for (i = 0; i < n; i++) {
    int k;
    for (k = 0; k < n; k++) {
      arr[j++] = buckets[i][k];
    }
  }
}

C++

//  Types of Sorting algorithms: Bucket Sort In C++ 

void bucketSort(float arr[], int n) {
  vector<float> buckets[n];

  // put elements in buckets
  for (int i=0; i<n; i++) {
    int bucketIdx = arr[i] * n;
    buckets[bucketIdx].push_back(arr[i]);
  }

  // sort individual buckets
  for (int i = 0; i < n; i++) 
    sort(buckets[i].begin(), buckets[i].end());

  // concatenate buckets
  int index = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < buckets[i].size(); j++) {
      arr[index++] = buckets[i][j];
    }
  }
}

Python

# Types of Sorting algorithms: Bucket Sort In Python

def bucketSort(arr):
  max_val = max(arr)
  size = len(arr)
  buckets_list = [[] for _ in range(size)]

  # put elements in different buckets
  for i in range(size):
    j = int(size * arr[i])
    if j != size:
      buckets_list[j].append(arr[i])
    else:
      buckets_list[size - 1].append(arr[i])

  # sort individual buckets
  for i in range(size):
    buckets_list[i] = sorted(buckets_list[i]) 

  # concatenate buckets
  k = 0
  for i in range(size):
    for j in range(len(buckets_list[i])):
      arr[k] = buckets_list[i][j]
      k += 1

  return arr

Radix Sort

Radix sort stably sorts array by digits at each position iteratively from least to most significant.

Algorithm

Pseudocode

 // Types of Sorting algorithms: Pseudocode For Radixsort

radixSort(array, d):
 // d is number of digits in largest number
 for i = 1 to d:
   use counting sort on array by ith digit
   return array

Walkthrough

Properties

• Time Complexity: O(nk)
• Space Complexity: O(n+k)
• Stable sort

Radix efficiently sorts integers stably in linear time.

Code Example

Java

//  Types of Sorting algorithms: Radix Sort 

void radixSort(int[] arr) {
  int max = Arrays.stream(arr).max().getAsInt();
  // sort by each digit
  for (int exp = 1; max/exp > 0; exp *= 10) {
    countSort(arr, exp);
  }
}

void countSortForRadix(int[] arr, int exp) {
  // count sort logic using digit at exp
}

C

//  Types of Sorting algorithms: Radix Sort
void radixSort(int arr[], int n) {

  int m = getMax(arr, n);

  // sort by each digit
  for (int exp = 1; m/exp > 0; exp *= 10) {
    countSort(arr, n, exp);
  }
}

// count sort logic for radix

C++

//  Types of Sorting algorithms: Radix Sort
void radixSort(int arr[], int n) {
  int max = *max_element(arr, arr+n);

  // sort by each digit
  for (int exp = 1; max/exp > 0; exp *= 10)
    countSort(arr, n, exp); 
}

void countSort(int arr[], int n, int exp) {
  // count sort logic on digit at exp
}

Python

#  Types of Sorting algorithms: Radix Sort
def countingSortForRadix(exp, arr):
  # count sort logic for radix

def radixSort(arr):
  max_element = max(arr)
  place = 1
  while max_element // place > 0:
    countingSortForRadix(place, arr)
    place *= 10

Shellsort

Shellsort sorts array by comparing elements separated by gaps that are reduced each iteration.

Algorithm

Pseudocode

// PseudoCode For Shell Sort

shellSort(array, n):
 initialize gap = n/2
 while gap > 0:

   for i = gap to n:

   insert array[i] among previous using insertion sort and gap
   reduce gap to gap/2

   return array

Shell sort improves on insertion sort by comparing across gaps.

Properties

• Time Complexity: O(nlogn) down to O(n^1.25)
• Space Complexity: O(1)
• Unstable sort

Shell sort code

Sorting in Programming Languages

Built-in sorting functions and libraries are optimized for convenience and efficiency.

Here are different ways of using different types of sorting in different programming languages:

Python

• sorted() – Returns a sorted list from an iterable
• list.sort() – Sorts a list in-place
• Uses Timsort (hybrid of mergesort and insertion sort)
• key and reverse params for custom sorting logic

Java

• Arrays.sort() – Sorts primitive arrays
• Collections.sort() – Sorts object collections
• Uses optimized quicksort and merge sort implementations
• Comparator interfaces for custom sorting

C++

• std::sort() – General purpose sort function
• std::stable_sort() – Stable sort function
• Internally uses introsort – introspective sort
• Overload comparison operators or provide comparator function for custom sorts

Types of Sorting In C

• qsort() – Implements quicksort algorithm
• comparator function required for custom sorting logic
• Not a stable sort
• Pointer friendly for arrays

JavaScript

• array.sort() – Sorts array in-place
• compareFunction optional for custom sort order
• Uses quicksort V8 engine optimization
• Works on any iterable objects

Go

• sort package – Sort() and Stable() functions
• sort.Interface interface for custom sorts
• Hybrid merge+insertion sort for efficiency
• Concurrency-safe versions available

Most languages provide built-in highly optimised sorting functions while allowing customisation like comparator functions.

Comparison of Different Types Of Sorting Techniques

Here is a comparison of different types of sorting techniques :

• Bubble, insertion and selection sorts are elementary sorts with quadratic time complexity.
• Merge, quick, heap are efficient general purpose sorts with O(nlogn) complexity.
• Counting, bucket and radix exploit properties of input for improved efficiency.
• Shell and timsort use hybrid approaches for real-world optimization.
• Stability, in-place requirements, input size etc. factor into choosing the best sort.

Applications of Sorting

• Databases rely on efficient sorting for quickly ordering and indexing records.
• Web search engines use sorting to return most relevant results first.
• Analytics tasks require sorting for summarization, pattern analysis, and data processing.

Conclusion

Sorting is an essential concept in computer science with widespread applications. Efficient sorting enables processing and retrieval of data in diverse computing areas. Further exploration of advanced sorting, implementations, and real-world use cases is encouraged.In this articile we covered types of sorting algorithms along with algorithms and code in various programming language.

Try out our free resume checker service where our Industry Experts will help you by providing resume score based on the key criteria that recruiters and hiring managers are looking for.

References

• Introduction to Algorithms by Thomas H. Cormen et al.
• Algorithms by Robert Sedgewick and Kevin Wayne
• The Art of Computer Programming by Donald Knuth

FAQ Regarding Types Of Sorting Techniques

When should I use a stable vs unstable sorting algorithm?

Stable algorithms maintain order of elements with equal keys. Use stable sort when relative order needs to be maintained, like sorting names by surname.

When would bucket sort be more efficient than quicksort?

Bucket sort works well when input is uniformly distributed. It can achieve linear time complexity compared to quicksort’s nlogn.

What are some examples of adaptive sorting algorithms?

Timsort and introsort are examples of adaptive sorts that can optimize based on partially sorted data.

How does radix sort achieve linear time complexity?

Radix sort exploits the integer digit structure by sorting on each position iteratively. This avoids comparisons between elements.

What is a hybrid sorting algorithm?

Hybrid algorithms combine approaches from multiple sorting techniques like timsort using insertion sort and merge sort.