Getting started with sorting algorithms

Written By: 0xMahabub

Some important sorting algorithms for developers or cs-students

# Sorting Algorithms

There are many sorting algorithms out there. But we need to learn some basic sorting algorithms first. Then we can also go for further move. For now,
We will learn Bubble Sort, Selection Sort, and Insertion Sort first. Then we also touch the Divide & Conquer => Merge Sort & Quick Sort too.

Table of Contents:

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort

# Bubble Sort

Complexity: Big O(n²)

function bubbleSort(arr: number[]): void {
  for (let i:number = 0; i<arr.length - 1; i++) {
    for (let j:number = 0; j<arr.length - 1 - i; j++) {
      if (arr[j] > arr[j+1]) {
        // using a temp variable
        let temp = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = temp;
        // or by swaping
        // [arr[j+1], arr[j]] = [arr[j], arr[j+1]]
      }
    }
  }
}

public void bubbleSort(List<Integer> arr) {
  for (int i=0; i<arr.size() - 1; i++) {
    for (int j=0; j<arr.size() - 1 - i; j++) {
      if (arr.get(j) > arr.get(j+1)) {
        int temp = arr.get(j+1);
        arr.set(j+1, arr.get(j));
        arr.set(j, temp);
      }
    }
  }
}

def bubbleSort(arr: List[int]) -> None:
  for i in range(0, len(arr) - 1):
    for j in range(0, len(arr) - 1 - i):
      if arr[j] > arr[j+1]:
        arr[j], arr[j+1] = arr[j+1], arr[j] # swaped

# Done

# Selection Sort

Complexity: Big O(n²)

function selectionSort(arr: number[]): void {
  for (let i:number = 0; i<arr.length - 1; i++) {
    let minIndex: number = i;
    for (let j:number = i+1; j<arr.length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    // now swap
    [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
  }
}

public void selectionSort(List<Integer> arr) {
  for (int i=0; i<arr.size() - 1; i++) {
    int minIndex = i;
    for (int j=i+1; j<arr.size(); j++) {
      if (arr.get(minIndex) > arr.get(j)) {
        minIndex = j;
      }
    }
    // swap
    int temp = arr.get(minIndex);
    arr.set(minIndex, arr.get(i));
    arr.set(i, temp);
  }
}

def selectionSort(arr: List[int]) -> None:
  for i in range(0, len(arr) - 1):
    minIndex: int = i
    for j in range(i+1, len(arr)):
      if arr[minIndex] > arr[j]:
        minIndex = j
    
    # now swap
    arr[minIndex], arr[i] = arr[i], arr[minIndex]

# Done

# Insertion Sort

Complexity: Big O(n²)

function insertionSort(arr: number[]): void {
  for (let i: number = 1; i<arr.length; i++) {
    let key: number = arr[i];
    let j: number = i-1;
    while(j >= 0 && arr[j] > key) {
        arr[j+1] = arr[j];
        j--;
    }
    arr[j+1] = key;
  }
}

public void insertionSort(List<Integer> arr) {
  for (int i=0; i<arr.size(); i++) {
    int key = arr.get(i);
    int j: number = i-1;
    while(j>=0 && arr.get(j) > key){
      arr.get(j+1) = arr.get(j);
      j--;
    }
    arr.set(j+1, key);
  }
}

def insertionSort(arr: List[int]) -> None:
  for i in range(0, len(arr)):
    key: int = arr[i]
    j: int = i-1
    while (j>=0 and arr[j] > key):
      arr[j+1] = arr[j]
      j -= 1

    arr[j+1] = key

# Done

# Merge Sort

Complexity: Big O(n * log n)

function mergeSort(arr: number[]): void {
  // merge sort
}

public void mergeSort(List<Integer> arr) {
  // comming soon
}

def mergeSort(arr: List[int]) -> None:
  # comming soon

#done

# Quick Sort

Complexity: Big O(n * log n)

function quickSort(arr: number[]): void {
  // quick sort
}

public void quickSort(List<Integer> arr) {
  // comming soon
}

def quickSort(arr: List[int]) -> None:
  # comming soon

#done