정렬 - 선택, 버블, 삽입

그동안 알고리즘 문제 풀이 사이트에서 단순히 감으로 문제를 풀곤 했다. 그러나 시간이 지나고 나서야 이러한 방식으로는 실력을 향상할 수 없다는 것을 깨달았다. 이제는 체계적으로 문제를 해결하고자 한다.

우선, 코딩 테스트에서 중요한 시간 복잡도와 공간 복잡도를 고려하기 전에, 다양한 알고리즘의 종류를 먼저 이해하고 그런 다음, 문제를 풀고 나서 내가 작성한 풀이의 시간 복잡도를 분석하며 개선점을 찾아가는 방식으로 학습을 진행할 계획이다. 이렇게 체계적인 접근을 통해 깊이 있는 문제 해결 능력을 키우고자 한다.

출처 : 리트코드

 

정렬

정렬은 점수, 학번과 같은 항목의 대소 관계에 따라 나열하는 작업이다.

즉, 핵심 항목들을 체계적으로 정리하는 과정이다.

 

---

안정 정렬

정렬 전 동일한 키값에 한해서 정렬 후에도 키값이 유지되는 것을 말한다.

 

안정 정렬 알고리즘의 예로 버블 정렬 삽입 정렬 병합 정렬 이 있다.

---

선택 정렬 (Selection Sort)

가장 작은 또는 가장 큰 요소를 선택하여 이동시키는 알고리즘이다.

오름차순 기준

1. 배열에서 최소 요소를 찾는다.
2. 찾은 값을 정렬되지 않은 첫 번째 위치와 교환한다.
3. 그다음 정렬되지 않은 부분에서 1번과 2번 과정을 반복한다.

 

시간 복잡도

→ 배열의 각 최솟값을 구하기 위해 반복적으로 비교하기 때문에 O(N²)이다.

 

공간 복잡도

→ 교환에 필요한 일시적인 변수만 필요하기 때문에 O(1)이다.

 

불안정 정렬 알고리즘이다.

 

public class Solution {
    public void selectionSort(int[] arr) {
    
        int min_index;
        
        for (int i = 0; i < arr.length; i++) {
            min_index = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min_index]) {
                    min_index = j;
                }
            }
            int temp = arr[min_index];
            arr[min_index] = arr[i];
            arr[i] = temp;
        }
    }
}

 

---

버블 정렬 (Bubble Sort)

매번 첫 번째 요소부터 시작하여 인접한 두 요소를 비교하여 정렬하는 알고리즘이다.

오름차순 기준

1. 배열의 첫 번째 요소부터 시작하여 인접한 두 요소를 비교한다.
2. 두 요소의 순서가 잘못되어 있다면 교환한다.
3. 배열의 끝까지 도달하면, 가장 큰 값이 배열의 끝에 위치합니다.
4. 정렬이 완료될 때까지 1, 2, 3번을 반복한다.

 

시간 복잡도

→ 최악의 경우 O(N²) → 역순일 경우

→ 최선의 경우 O(N) → 이미 정렬되어 있을 경우

 

공간 복잡도

→ 교환에 필요한 일시적인 변수만 필요하기 때문에 O(1)이다.

 

안정 정렬 알고리즘이다.

 

public class Solution {
    public void bubbleSort(int[] arr) {
        
        boolean hasSwapped = true;
        while (hasSwapped) {
            hasSwapped = false;
            for (int i = 0; i < arr.length - 1; i++) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    hasSwapped = true;
                }
            }
        }
    }
}

public class Solution {
    public void bubbleSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

 

---

삽입 정렬 (Insertion Sort)

현재 위치에서 앞에 있는 요소들과 비교하여 교환하는 방식의 알고리즘이다.

이미 정렬된 부분과 하나씩 비교하며 삽입한다.

 

오름차순 기준

1. 첫 번째 요소는 정렬되었다 생각하고 두 번째 요소부터 시작하여 앞의 원소와 비교한다.
2. 자신과 가장 인접한 앞의 요소들을 하나씩 비교하고 적절한 위치에서 교환한다.
3. 정렬이 완료될 때까지 1, 2번을 반복한다.

 

시간 복잡도

• 최악의 경우 O(N²) → 역순으로 정렬되어 있을 경우 맨 앞의 배열까지 이동해야 하기 때문에
• 최선의 경우 O(N) → 정렬되어 있을 경우 비교만 하면 되기 때문에

공간 복잡도

• 교환에 필요한 일시적인 변수만 필요하기 때문에 O(1)이다.

안정 정렬 알고리즘이다.

 

public class Solution {
    public void insertionSort(int[] arr) {
    
        for (int i = 1; i < arr.length; i++) {
            int currentIndex = i;
            while (currentIndex > 0 && arr[currentIndex - 1] > arr[currentIndex]) {
                int temp = arr[currentIndex];
                arr[currentIndex] = arr[currentIndex - 1];
                arr[currentIndex - 1] = temp;
                currentIndex -= 1;
            }
        }
    }
}