Assignment 00 - Sorting Algorithms

Introduction to Basic Sorting Algorithms
This page provides basic information and JavaScript implementations of four fundamental sorting algorithms: Insertion Sort, Selection Sort, Merge Sort, and Quick Sort.

Insertion Sort

Insertion sort is a simple sorting algorithm that builds the sorted array one item at a time. It is much like sorting playing cards in your hands.

// Insertion Sort Implementation
function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

Selection Sort

Selection sort is a simple algorithm that repeatedly selects the smallest element from the unsorted portion and places it in the sorted portion.

// Selection Sort Implementation
function selectionSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
    return arr;
}

Merge Sort

Merge sort is a divide-and-conquer algorithm that splits the array into halves, recursively sorts them, and then merges the sorted halves.

// Merge Sort Implementation
function mergeSort(arr) {
    if (arr.length <= 1) return arr;
         
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
          
    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    let i = 0, j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }

    return result.concat(left.slice(i)).concat(right.slice(j));
}

Quick Sort

Quick sort is a divide-and-conquer algorithm that selects a pivot element, partitions the array around the pivot, and recursively sorts the partitions.

// Quick Sort Implementation
function quickSort(arr) {
    if (arr.length <= 1) return arr;
            
    const pivot = arr[arr.length - 1];
    const left = [];
    const right = [];
        
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
        
    return [...quickSort(left), pivot, ...quickSort(right)];
}