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

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

}

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, mid + 1, high);
        return found, index;
    }

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