소팅 알고리즘 중 시간복잡도가 O(n²)인 알고리즘들을 정리하려고 한다!

모든 코드는 오름차순 sorting 케이스이고 leetcode - sortColors에 제출해 정답을 얻은 코드이다!

Selection Sort

선택정렬. 현재 위치에 들어갈 값(선택)을 찾아 정렬

처음(index = 0)부터 n - 1을 돌며 해당 index에 들어갈 수를 찾아 swap한다.

    void selectionSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int selectedIndex = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[selectedIndex] > nums[j]) selectedIndex = j;
            }
            swap(nums, i, selectedIndex);
        }
    }

• is Stable: No
  swap 시 원래 앞에 있던 중복수1이 중복수2 뒤로 가는 경우, stable하지 않음
• is in-place: Yes

[8,5,6,2,4] 정렬 시
1. [2,5,6,8,4]
2. [2,4,6,8,5]
3. [2,4,5,8,6]
4. [2,4,5,6,8]
5. [2,4,5,6,8]

Insertion Sort

삽입정렬. 현재 위치에서 그 이하 위치의 값과 비교해 자신이 들어갈 위치를 찾아 삽입하는 알고리즘

새로운 수가 들어갈 위치를 뒤에서 부터 비교해(앞으로 가면서 swap) 찾음
따라서, 현재 위치가 k라면 k - 1까지는 정렬된 상태

이미 정렬된 배열이라면, O(n)의 시간복잡도를 가짐

// for
void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int value = nums[i];
        int j;
        for (j = i - 1; (j >= 0) && (nums[j] > value); j--) {
            nums[j + 1] = nums[j];
        }
        nums[j + 1] = value;
    }
}

// while
void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int value = nums[i];
        int j = i - 1;
        while ((j - 1 >= 0) && (nums[j] > value)) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = value;
    }
}

• is Stable: Yes
• is in-place: Yes

[8,5,6,2,4] 정렬 시
1. [5,8,6,2,4]
2. [5,6,8,2,4]
3. [2,5,6,8,4]
4. [2,4,5,6,8]

Bubble Sort

버블정렬. 매번 연속된 두 index를 비교해 큰 수를 뒤로 넘겨 정렬

비교할 때 마다 큰 수가 뒤로 swap
n바퀴 돌면 뒤쪽 n개 만큼 정렬된 상태

void bubbleSort(int[] nums) {
    for (int i = nums.length - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) swap(nums, j, j + 1);
        }
    } 
}

• is Stable: Yes
• is in-place: Yes

[8,5,6,2,4] 정렬 시
1. [5,6,2,4,8]
2. [5,2,4,6,8]
3. [2,4,5,6,8]
4. [2,4,5,6,8]