정렬(sort)

[lukasjhan]

1. 버블 정렬 (Bubble Sort)

예시 배열: [5, 3, 8, 4, 2]

실행 과정:

1. 첫 번째 패스:

   • (5,3) 비교 → 교환 [3,5,8,4,2]
   • (5,8) 비교 → 유지 [3,5,8,4,2]
   • (8,4) 비교 → 교환 [3,5,4,8,2]
   • (8,2) 비교 → 교환 [3,5,4,2,8]
     가장 큰 수 8이 맨 끝으로 이동

2. 두 번째 패스:

   • (3,5) 비교 → 유지 [3,5,4,2,8]
   • (5,4) 비교 → 교환 [3,4,5,2,8]
   • (5,2) 비교 → 교환 [3,4,2,5,8]
     두 번째로 큰 수 5가 맨 끝에서 두 번째로 이동

이런 식으로 계속 진행되어 최종적으로 [2,3,4,5,8]이 됩니다.

예시 코드

// 1. 버블 정렬
// - 인접한 두 원소를 비교하여 정렬하는 방식
// - 시간복잡도: O(n²)
const bubbleSort = (arr: number[]): number[] => {
    const array = [...arr];
    
    for (let i = 0; i < array.length; i++) {
        printArray(array, "Bubble Sort", `Pass ${i + 1} start`);
        
        let swapped = false;
        // 각 패스에서 뒤에서부터 정렬되므로 i를 뺀 만큼만 순회
        for (let j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                // 인접한 두 원소를 교환
                [array[j], array[j + 1]] = [array[j + 1], array[j]];
                swapped = true;
            }
        }
        
        // 교환이 없었다면 이미 정렬된 상태
        if (!swapped) break;
    }
    
    return array;
};

2. 선택 정렬 (Selection Sort)

예시 배열: [5, 3, 8, 4, 2]

실행 과정:

1. 첫 번째 패스:

   • 전체 배열에서 최솟값 2 찾음
   • 2와 첫 번째 위치의 5를 교환 [2,3,8,4,5]

2. 두 번째 패스:

   • 남은 배열 [3,8,4,5]에서 최솟값 3 찾음
   • 이미 올바른 위치에 있으므로 교환하지 않음

3. 세 번째 패스:

   • 남은 배열 [8,4,5]에서 최솟값 4 찾음
   • 4와 8을 교환 [2,3,4,8,5]

이런 식으로 계속 진행됩니다.

예시 코드

// 2. 선택 정렬
// - 현재 위치에 들어갈 값을 찾아 정렬하는 방식
// - 시간복잡도: O(n²)
const selectionSort = (arr: number[]): number[] => {
    const array = [...arr];
    
    for (let i = 0; i < array.length - 1; i++) {
        printArray(array, "Selection Sort", `Finding minimum for position ${i}`);
        
        let minIdx = i;
        // 현재 위치 이후의 원소들 중 최솟값 찾기
        for (let j = i + 1; j < array.length; j++) {
            if (array[j] < array[minIdx]) {
                minIdx = j;
            }
        }
        
        // 최솟값을 현재 위치로 이동
        if (minIdx !== i) {
            [array[i], array[minIdx]] = [array[minIdx], array[i]];
        }
    }
    
    return array;
};

3. 퀵 정렬 (Quick Sort)

예시 배열: [5, 3, 8, 4, 2]
피벗으로 마지막 요소 2를 선택한다고 가정

실행 과정:

1. 첫 번째 분할:

   • 피벗: 2
   • 2보다 작은 값들을 왼쪽으로 이동
   • 결과: [2] | [5,3,8,4]

2. 오른쪽 부분 배열 [5,3,8,4] 정렬:

   • 피벗: 4
   • 재정렬: [3] | [4] | [5,8]

3. [5,8] 정렬:

   • 피벗: 8
   • 재정렬: [5] | [8]

최종적으로 모든 부분이 합쳐져 [2,3,4,5,8]이 됩니다.

예시 코드

// 3. 퀵 정렬
// - 피벗을 기준으로 분할하여 정렬하는 방식
// - 평균 시간복잡도: O(n log n)
const quickSort = (arr: number[]): number[] => {
    const array = [...arr];
    
    const partition = (low: number, high: number): number => {
        const pivot = array[high];
        let i = low - 1;
        
        printArray(array, "Quick Sort", `Partitioning with pivot ${pivot}`);
        
        for (let j = low; j < high; j++) {
            if (array[j] <= pivot) {
                i++;
                [array[i], array[j]] = [array[j], array[i]];
            }
        }
        
        [array[i + 1], array[high]] = [array[high], array[i + 1]];
        return i + 1;
    };
    
    const sort = (low: number, high: number): void => {
        if (low < high) {
            const pi = partition(low, high);
            sort(low, pi - 1);
            sort(pi + 1, high);
        }
    };
    
    sort(0, array.length - 1);
    return array;
};

4. 병합 정렬 (Merge Sort)

예시 배열: [5, 3, 8, 4, 2]

실행 과정:

1. 분할 단계:
   [5,3,8,4,2]
   → [5,3] [8,4,2]
   → [5] [3] [8] [4,2]
   → [5] [3] [8] [4] [2]

2. 병합 단계:

   • [5] [3] → [3,5]
   • [8] [4] [2] → [4,8] [2]
   • [3,5] [2,4,8] → [2,3,4,5,8]

각 단계에서:

• 두 배열의 첫 번째 요소들을 비교
• 더 작은 값을 결과 배열에 넣음
• 선택된 배열의 다음 요소로 이동
• 한 배열이 비워질 때까지 반복
• 남은 요소들을 결과 배열 끝에 추가

이러한 과정을 통해 정렬이 이루어집니다.

예시 코드

// 4. 병합 정렬
// - 분할 정복 방식으로 정렬
// - 시간복잡도: O(n log n)
const mergeSort = (arr: number[]): number[] => {
    const array = [...arr];
    
    const merge = (left: number, mid: number, right: number): void => {
        const leftArr = array.slice(left, mid + 1);
        const rightArr = array.slice(mid + 1, right + 1);
        
        printArray([...leftArr, ...rightArr], "Merge Sort", "Merging subarrays");
        
        let i = 0, j = 0, k = left;
        
        while (i < leftArr.length && j < rightArr.length) {
            if (leftArr[i] <= rightArr[j]) {
                array[k] = leftArr[i];
                i++;
            } else {
                array[k] = rightArr[j];
                j++;
            }
            k++;
        }
        
        while (i < leftArr.length) {
            array[k] = leftArr[i];
            i++;
            k++;
        }
        
        while (j < rightArr.length) {
            array[k] = rightArr[j];
            j++;
            k++;
        }
    };
    
    const sort = (left: number, right: number): void => {
        if (left < right) {
            const mid = Math.floor((left + right) / 2);
            sort(left, mid);
            sort(mid + 1, right);
            merge(left, mid, right);
        }
    };
    
    sort(0, array.length - 1);
    return array;
};

5. 삽입정렬 (insertion sort)

예시 배열: [5, 3, 8, 4, 2]
실행 과정:

첫 번째 패스 (두 번째 요소부터 시작):

현재 값: 3
비교 배열: [5] | [3,8,4,2]
5와 3을 비교 → 3이 더 작음
3을 5 앞으로 삽입
결과: [3,5,8,4,2]

두 번째 패스:

현재 값: 8
비교 배열: [3,5] | [8,4,2]
5와 8을 비교 → 8이 더 큼
이미 올바른 위치이므로 그대로 둠
결과: [3,5,8,4,2]

세 번째 패스:

현재 값: 4
비교 배열: [3,5,8] | [4,2]
8과 4를 비교 → 4가 더 작음
5와 4를 비교 → 4가 더 작음
3과 4를 비교 → 4가 더 큼
3과 5 사이에 4를 삽입
결과: [3,4,5,8,2]

네 번째 패스:

현재 값: 2
비교 배열: [3,4,5,8] | [2]
8과 2를 비교 → 2가 더 작음
5와 2를 비교 → 2가 더 작음
4와 2를 비교 → 2가 더 작음
3과 2를 비교 → 2가 더 작음
맨 앞에 2를 삽입
최종 결과: [2,3,4,5,8]

예시 코드

// 5. 삽입 정렬
// - 정렬된 부분과 정렬되지 않은 부분으로 나누어 정렬
// - 시간복잡도: O(n²), 최선의 경우 O(n)
const insertionSort = (arr: number[]): number[] => {
    const array = [...arr];
    
    for (let i = 1; i < array.length; i++) {
        printArray(array, "Insertion Sort", `Inserting ${array[i]}`);
        
        const current = array[i];
        let j = i - 1;
        
        // 정렬된 부분에서 current가 들어갈 위치 찾기
        while (j >= 0 && array[j] > current) {
            array[j + 1] = array[j];
            j--;
        }
        
        array[j + 1] = current;
    }
    
    return array;
};

정렬 안정성

안정 정렬이란: 동일한 값을 가진 요소들의 원래 순서가 정렬 후에도 유지되는 것을 의미합니다.
예를 들어 [3A, 3B, 1] → [1, 3A, 3B] 이렇게 정렬되면 안정 정렬입니다.

1. 버블 정렬 (Bubble Sort)

안정 정렬 ✅
이유: 인접한 두 요소를 비교할 때 같은 값이면 교환하지 않기 때문에 원래 순서가 유지됩니다.

2. 선택 정렬 (Selection Sort)

불안정 정렬 ❌
이유: 가장 작은 값을 찾아 멀리 있는 위치와 교환할 때 동일한 값의 상대적 위치가 바뀔 수 있습니다.
예시: [4, 2A, 3, 2B, 1] → [1, 2B, 3, 2A, 4]
최소값을 찾아 맨 앞으로 보내는 과정에서 2A와 2B의 순서가 바뀔 수 있습니다.

3. 퀵 정렬 (Quick Sort)

불안정 정렬 ❌
이유: 피벗을 기준으로 요소들을 재배치하는 과정에서 동일한 값의 상대적 위치가 바뀔 수 있습니다.
예시: 피벗이 3일 때 [3A, 2, 3B, 1] → [2, 1, 3B, 3A]
분할 과정에서 3A와 3B의 순서가 바뀔 수 있습니다.

4. 병합 정렬 (Merge Sort)

안정 정렬 ✅
이유: 병합 과정에서 같은 값을 비교할 때 왼쪽 배열의 값을 먼저 선택하도록 구현하면 안정성이 보장됩니다.

5. 삽입 정렬 (Insertion Sort)

안정 정렬 ✅
이유: 같은 값을 만났을 때 그 뒤에 삽입하므로 원래 순서가 유지됩니다.

[lukasjhan]

직접 구현해보면서 익혀봅시다 :)

[yunseorim1116]

LGTM~!~!