Common Sort Algorithms

There are many different sorting algorithms, but some of the most common ones include:

• Bubble sort
• Selection sort
• Insertion sort
• Merge sort
• Quick sort
• Heap sort
• Counting sort
• Radix sort
• Bucket sort

Bubble Sort

Bubble sort is a simple sorting algorithm that works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. The algorithm starts at the beginning of the array and compares the first two elements. If the first element is greater than the second element, they are swapped. The algorithm then moves on to the next two elements and repeats the process. This continues until the end of the array is reached.

def bubble_sort(array):
  for i in range(len(array) - 1):
    for j in range(len(array) - i - 1):
      if array[j] > array[j + 1]:
        array[j], array[j + 1] = array[j + 1], array[j]

  return array

void bubble_sort(int array[], int size) {
  int i, j;
  for (i = 0; i < size - 1; i++) {
    for (j = 0; j < size - i - 1; j++) {
      if (array[j] > array[j + 1]) {
        int temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
}

Selection Sort

Selection sort is another simple sorting algorithm that works by repeatedly finding the minimum element in the array and swapping it with the first element. The algorithm starts at the beginning of the array and finds the minimum element. It then swaps the minimum element with the first element and moves on to the next element. This continues until the end of the array is reached.

def selection_sort(array):
  for i in range(len(array) - 1):
    min_index = i
    for j in range(i + 1, len(array)):
      if array[j] < array[min_index]:
        min_index = j

    array[i], array[min_index] = array[min_index], array[i]

  return array

void selection_sort(int array[], int size) {
  int i, j, min_index;
  for (i = 0; i < size - 1; i++) {
    min_index = i;
    for (j = i + 1; j < size; j++) {
      if (array[j] < array[min_index]) {
        min_index = j;
      }
    }

    int temp = array[i];
    array[i] = array[min_index];
    array[min_index] = temp;
  }
}

Insertion Sort

Insertion sort is a sorting algorithm that works by repeatedly inserting elements into their correct position in a sorted array. The algorithm starts at the beginning of the array and compares the first element to the elements in the sorted array. If the first element is smaller than any of the elements in the sorted array, it is inserted into the sorted array at the correct position. The algorithm then moves on to the next element and repeats the process. This continues until the end of the array is reached.

def insertion_sort(array):
  for i in range(1, len(array)):
    j = i - 1
    key = array[i]
    while j >= 0 and array[j] > key:
      array[j + 1] = array[j]
      j -= 1
    array[j + 1] = key

  return array

void insertion_sort(int *array, int n) {
    for (int i = 1; i < n; i++) {
        int j = i - 1;
        int current = array[i];
        while (j >= 0 && array[j] > current) {
            array[j + 1] = array[j];
            j -= 1;
        }
        array[j + 1] = current;
    }
}

Merge sort

Merge sort is a divide-and-conquer sorting algorithm that works by recursively splitting an array into two halves, sorting each half, and then merging the sorted halves back together.

def merge_sort(array):
    if len(array) <= 1:
        return array

    middle = len(array) // 2
    left = merge_sort(array[:middle])
    right = merge_sort(array[middle:])

    return merge(left, right)


def merge(left, right):
    result = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result += left[i:]
    result += right[j:]

    return result

void merge_sort(int *array, int n) {
    if (n <= 1) {
        return;
    }

    int middle = n / 2;
    merge_sort(array, middle);
    merge_sort(array + middle, n - middle);

    merge(array, array + middle, n);
}

void merge(int *array, int *left, int left_size) {
    int *right = array + left_size;
    int *result = array;

    int i = 0;
    int j = 0;
    while (i < left_size && j < right_size) {
        if (left[i] <= right[j]) {
            *result++ = left[i++];
        } else {
            *result++ = right[j++];
        }
    }

    while (i < left_size) {
        *result++ = left[i++];
    }

    while (j < right_size) {
        *result++ = right[j++];
    }
}