Sorting and Searching Algorithms

Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the array, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted.

The following bubble sort algorithm below sorts all the elements in an array in ascending order.

bubble_sort :: (array: [] int) {

    sorted := false;

    while !sorted {
        i := 0;
        j := 1;
        sorted = true;
        while j < array.count {
            if array[j] < array[i] {
                array[j], array[i] = array[i], array[j];
                sorted = false;
            }
            i += 1;
            j += 1;
        }
    }
}

Insertion Sort

Insertion sort that builds a sorted array one element at a time. Insertion sort iterates, consuming one input element each repetition, and grows a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the correct location within the sorted list, and inserts it there. It repeats until no input elements remain.

The following insertion sort algorithm below sorts all the elements in an array in ascending order.

insertion_sort :: (array: [] int) {
    i := 1;
    while i < array.count {
        key := array[i];
        j := i - 1;
        while j >= 0 && key < array[j] {
            array[j + 1] = array[j];
            j -= 1;
        }
        array[j + 1] = key;
        i += 1;
    }
}

Selection Sort

Selection Sort is a simple comparison-based sorting algorithm. It works by dividing the input list into two parts: the sorted portion and the unsorted portion. The algorithm repeatedly selects the smallest (or largest, depending on the order) element from the unsorted portion and swaps it with the first unsorted element, gradually growing the sorted portion.

The following selection sort algorithm below sorts all the elements in an array in ascending order.

selection_sort :: (array: [] int) {
    N := array.count - 1;
    for i : 0..N {
        ele := i;
        for j : (i+1)..N {
            if array[j] < array[ele] {
                ele = j;
            }
        }
        array[ele], array[i] = array[i], array[ele];
    }

}

Mergesort

Mergesort is an efficient and general purpose sorting algorithm. The algorithm time complexity of mergesort is O(n log n).

A merge sort works as follows:

• Divide the unsorted list into n sub-lists, each containing one element.
• Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.

merge_sort :: (arr: [] int) {
    // Merge two subarrays L and M into arr
    merge :: (arr: [] int, p: int, q: int, r: int) {
        n1 := q - p + 1;
        n2 := r - q;
        L := NewArray(n1, int);
        M := NewArray(n2, int);

        for i : 0..(n1-1) {
            L[i] = arr[p + i];
        }

        for j : 0..(n2-1) {
            M[j] = arr[q + 1 + j];
        }

        // Maintain current index of sub-arrays and main array
        i := 0;
        j := 0;
        k := p;
        while i < n1 && j < n2 {
            if L[i] <= M[j] {
                arr[k] = L[i];
                i += 1;
            } else {
                arr[k] = M[j];
                j += 1;
            }
            k += 1;
        }

        while i < n1 {
            arr[k] = L[i];
            i += 1;
            k += 1;
        }

        while (j < n2) {
            arr[k] = M[j];
            j += 1;
            k += 1;
        }
    }

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

    merge_sort_helper(arr, 0, arr.count - 1);
}

Quicksort

Quicksort is an efficient, general-purpose sorting algorithm with a time complexity of O(n log n). It is one of the most commonly used algorithms for sorting.

Steps Involved in quicksort

Quicksort selects a pivot element from the array and partitions the other elements into two sub-arrays:

• Elements less than the pivot
• Elements greater than the pivot It then recursively applies the same logic to the sub-arrays.

quicksort :: (array: [] int) {

    partition :: (array: [] int, low: int, high: int) -> int {
        pivot := array[high];

        i := low;
        j := low;
        while j < high {
            if array[j] < pivot {
                array[i], array[j] = array[j], array[i];
                i += 1;
            }
            j += 1;
        }
        array[i], array[high] = array[high], array[i];
        return i;
    }

    quicksort_helper :: (array: [] int, low: int, high: int) {
        if (low >= high || low < 0) {
            return;
        }

        p := partition(array, low, high);
        quicksort_helper(array, low, p - 1);
        quicksort_helper(array, p + 1, high);
    }

    quicksort_helper(array, 0, array.count - 1);
}

Linear Search

A linear search is a basic search algorithm that examines each element of an array one by one until it finds the correct value.

linear_search :: (array: [] int, value: int) -> found: bool, index: int {
    index := -1;
    i := 0;
    while i < array.count {
        if array[i] == value {
            return true, i;
        }
        i += 1;
    }
    return false, -1;
}

Binary Search

Binary search is a search algorithm that efficiently finds the position of a target value within a sorted array within O(log n) time.

Iterative Binary Search

binary_search :: (array: [] int, value: int) -> found: bool, index: int {
    low := 0;
    high := array.count - 1;
    while low <= high {
        mid := (low + high) / 2;
        if array[mid] == value {
            return true, mid;
        } else if array[mid] < value {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return false, -1;
}

Recursive Binary Search

binary_search :: (array: [] int, value: int) -> found: bool, index: int {
    binary_search_helper :: (array: [] int, value: int, low: int, high: int) -> found: bool, index: int {
        if low > high {
            return false, -1;
        }

        mid := (low + high) / 2;
        if array[mid] == value {
            return true, mid;
        } else if array[mid] < value {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
        found, index := binary_search_helper(array, value, low, high);
        return found, index;
    }

    found, index := binary_search_helper(array, value, 0, array.count - 1);
    return found, index;
}