Bubble sort

인접한 두 요소를 비교하여 정렬하는 방식이다. 각 반복에서, 배열을 순회하며 각 요소를 그 다음 요소와 비교하여 필요한 경우 위치를 교환한다. 이 과정을 배열의 모든 요소가 정렬될 때까지 반복한다.

최악, 평균, 최선의 경우 모두 O(n²)의 시간 복잡도를 가진다.

버블 정렬은 데이터가 거의 정렬된 상태에 가까울수록 효율적이지만, 일반적으로 큰 데이터셋에 대해서는 매우 비효율적이다.

ex)

function bubbleSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 요소 교환
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

Quick Sort

분할 정복 알고리즘의 한 예로, '피벗'이라고 불리는 요소를 선택하고 피벗보다 작은 요소는 피벗의 왼쪽으로, 큰 요소는 오른쪽으로 이동시킨다. 이 과정을 재귀적으로 반복하여 전체 배열을 정렬한다.

평균적으로 O(n log n)의 시간 복잡도를 가지며, 최악의 경우에는 O(n²)가 될 수 있지만, 이는 피벗 선택 방법에 따라 달라진다.

퀵 정렬은 대규모 데이터셋에 대해 매우 높은 효율을 보이며, 평균적인 경우 가장 빠른 정렬 알고리즘 중 하나다.

ex)

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    const pivot = arr[0];
    const left = [];
    const right = [];

    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    return [...quickSort(left), pivot, ...quickSort(right)];
}