ソートアルゴリズムの基礎

バブルソート (O(n²))

安定なソートアルゴリズムで、隣接する要素を比較・交換しながら最大値を末尾に移動させる

const data = [5, 2, 8, 1, 9];

// 基本バブルソート
for (let outer = 0; outer < data.length - 1; outer++) {
    for (let inner = 0; inner < data.length - 1 - outer; inner++) {
        if (data[inner] > data[inner + 1]) {
            [data[inner], data[inner + 1]] = [data[inner + 1], data[inner]];
        }
    }
}

選択ソート (O(n²))

非安定なソートで、未ソート部分から最小値を探し先頭と交換する

const numbers = [7, 3, 5, 1, 4];

for (let current = 0; current < numbers.length - 1; current++) {
    let minimumIndex = current;
    for (let search = current + 1; search < numbers.length; search++) {
        if (numbers[search] < numbers[minimumIndex]) {
            minimumIndex = search;
        }
    }
    [numbers[current], numbers[minimumIndex]] = [numbers[minimumIndex], numbers[current]];
}

挿入ソート (O(n²))

安定なソートで、各要素を適切な位置に挿入しながらソートする

const values = [6, 4, 1, 3, 2];

for (let index = 1; index < values.length; index++) {
    const currentValue = values[index];
    let position = index - 1;
    
    while (position >= 0 && values[position] > currentValue) {
        values[position + 1] = values[position];
        position--;
    }
    values[position + 1] = currentValue;
}

シェルソート (O(n^(1.3-2)))

挿入ソートの改良版で、間隔を設けて部分ソートを行う

const array = [9, 6, 3, 8, 5, 2, 7, 4, 1];
let gap = Math.floor(array.length / 2);

while (gap > 0) {
    for (let i = gap; i < array.length; i++) {
        const temp = array[i];
        let j = i;
        
        while (j >= gap && array[j - gap] > temp) {
            array[j] = array[j - gap];
            j -= gap;
        }
        array[j] = temp;
    }
    gap = Math.floor(gap / 2);
}

クイックソート (平均O(n log n))

分割統治法を用いた高速なソートアルゴリズム

function quickSort(items, start = 0, end = items.length - 1) {
    if (start >= end) return;
    
    const pivotIndex = partition(items, start, end);
    quickSort(items, start, pivotIndex - 1);
    quickSort(items, pivotIndex + 1, end);
}

function partition(arr, low, high) {
    const pivot = arr[high];
    let i = low - 1;
    
    for (let j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
}

const dataset = [10, 7, 8, 9, 1, 5];
quickSort(dataset);

マージソート (O(n log n))

安定なソートで、配列を分割してソート後にマージする

function mergeSort(input) {
    if (input.length <= 1) return input;
    
    const middle = Math.floor(input.length / 2);
    const left = mergeSort(input.slice(0, middle));
    const right = mergeSort(input.slice(middle));
    
    return merge(left, right);
}

function merge(leftArr, rightArr) {
    const result = [];
    let leftIndex = 0;
    let rightIndex = 0;
    
    while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
        if (leftArr[leftIndex] < rightArr[rightIndex]) {
            result.push(leftArr[leftIndex++]);
        } else {
            result.push(rightArr[rightIndex++]);
        }
    }
    
    return result.concat(leftArr.slice(leftIndex), rightArr.slice(rightIndex));
}

const unsorted = [38, 27, 43, 3, 9, 82, 10];
const sorted = mergeSort(unsorted);