Bubble Sort (버블 정렬) / Selection Sort (선택 정렬)

Bubble Sort (버블 정렬)

visualization의 차이: (오름차순으로 정렬)

배열의 요소들을 가로로 놓은 뒤 가장 큰 값부터 오른쪽으로 몰아가는 방식

혹은 가장 작은 값을 찾아 왼쪽으로 몰아가는 방식

세로로 놓고 가장 작은 값을 밑으로, 큰 값을 위쪽으로 놓는 방식 등

결과는 똑같다.

public class Main {
    public static void main(String[] args) {
        int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };
        // 버블 정렬
        for (int lastUnsortedIndex = intArray.length - 1; lastUnsortedIndex > 0;
             lastUnsortedIndex--) {
            for (int i = 0; i < lastUnsortedIndex; i++) {
                if (intArray[i] > intArray[i + 1]) {
                    swap(intArray, i, i + 1);
                }
            }
        }
        // 배열 출력
        for (int i = 0; i < intArray.length; i++) {
            System.out.print(intArray[i] + " ");
        }
    }

    public static void swap(int[] array, int i, int j) {
        if (i == j) {   // 같은 인덱스가 들어오면 함수를 끝냄
            return;
        }
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

• In-place (제자리 정렬)
  추가적인 배열을 만들 필요가 없다. 이런 알고리즘을 메모리 측면에서 In-place algorithm(제자리 정렬 알고리즘)이라고 한다. 구현 과정에서 지역 변수가 필요하기는 하지만 그래도 제자리 정렬이다. 왜냐? 만약 배열 요소의 개수가 늘어나도 추가로 필요한 메모리 양이 그대로라면, 제자리 정렬이라고 보면 된다.
• 시간복잡도 O(N^2); Quadratic
  정렬할 요소의 개수가 늘어남에 따라, 수행 속도가 급격히 느려진다.
• Stable algorithm
  하단 설명 참조.

시간 복잡도를 계산하는 팁: 

loop이 얼마나 필요한지를 보자. 보통 하나의 loop이 있으면 N이다. 즉 O(N) (Linear time complexity)이다. loop 2개가 중첩되어 있다면 N*N, 즉 O(N^2) (Quadratic time complexity)일 것이다. 

＃ 버블 소트가 성능이 매우 안좋으니, 몇몇 학자들은 버블 소트는 이제 배울 필요도 가르칠 필요도 없는 알고리즘이라고도 한다. Leetcode, HackerRank 같은 코딩 연습 사이트에도 버블 소트는 예제가 없다. 하지만 다른 알고리즘들은 왜 버블소트보다 빠른지 이해하기 위해서라도, 가볍게 짚고 넘어가자.

---

Stable vs. Unstable Sort Algorithms
(안정적 / 불안정적 알고리즘)

다음과 같이 정렬하려는 배열에 중복된 값이 존재한다고 치자.

정렬 전:

5

9

3

9

8

4

정렬 후:

3

4

5

8

9

9

9가 중복되는 값인데, 두 개의 9의 순서가 정렬 후에도 그대로 유지되면 안정적 정렬, 순서가 바뀌면(보존되지 않으면) 불안정적 정렬 알고리즘이다. 위의 예시에서는 정렬 과정에서 두 개의 9의 순서가 보존되었다. 따라서 안정적 정렬이다.

다른 모든 요소가 동일하다면, 불안정적 정렬보다는 안정적 정렬이 더 낫다. 그냥 정수라면 별 상관 없어 보이지만, 만약 중첩된 정렬을 수행하는데 정렬하려는 것이 string과 같은 object라면 얘기가 달라진다. 첫번째 pass에서 이름을 기준으로 정렬한 뒤, 그것들을 다시 나이에 따라 정렬한다던지, 이런 경우에 불안정적 정렬이 적용된다면 뒤죽박죽 될 위험성이 있다.

어쨌거나, 버블 소트는 "안정적" 정렬이다. 항상 인접한 두 요소끼리 비교하고, 두 값이 같은 값일 경우 swap하지 않을 것이고 따라서 안정적이다. 

※ 주의! 남의 코드를 보거나 직접 코드를 쓸 때, 분명 안정적 정렬 알고리즘인데 막상 구현한 걸 보면 불안정적 정렬인 경우가 있다. 꼭 확인할 것.

---

Selection Sort (선택 정렬)

버블 정렬과 마찬가지로, 가장 큰 값을 오른쪽에 쌓아 나가는 방식이나 가장 작은 값을 왼쪽에 쌓아 나가는 방식이나 결과는 똑같다.

다음 그림을 보자.

한 step 안에서, 

가장 왼쪽에 있는 값이 가장 작은 값이라고 가정한 뒤, 

그 오른쪽에 있는 요소들 중에 더 작은 값이 있으면 그 곳의 index를 저장해 놓는다(계속 update한다).

이런 식으로 끝까지 도달했을 때의 index값을 기준으로, 가장 왼쪽에 있는 값과 swap하면 정말로 가장 작은 값이 놓이게 된다.

위 그림은 가장 큰 값을 오른쪽에 쌓아 나가는 방식이다.

• In-place (제자리 정렬)
• 시간복잡도 O(N^2); Quadratic
  하지만 버블 정렬만큼 swap을 자주 하지는 않는다. 물론 almost sorted array(거의 정렬된 배열)을 버블 정렬할 경우 선택 정렬과 비슷하겠지만, 평균적으로는 선택 정렬이 버블 정렬보다 빠르다.
• Unstable algorithm
  중복된 여러 개의 값들 중 뒤의 값을 swap할 가능성이 충분히 있다. 그럴 경우 불안정적이 된다.

public class Main {
    public static void main(String[] args) {
        int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };
        // 각 pass가 끝날 때마다 lastUnsortedIndex 위치에 가장 큰 값이 위치해야 한다.
        for (int lastUnsortedIndex = intArray.length - 1; lastUnsortedIndex > 0;
                lastUnsortedIndex--) {
            int largest = 0;    // 가장 큰 값이 위치한 index
            // largest를 0으로 놓고 i는 1부터 시작
            for (int i = 1; i <= lastUnsortedIndex; i++) {
                if (intArray[i] > intArray[largest]) {
                    largest = i;
                }
            }
            // intArray[largest]와 intArray[lastUnsortedIndex] 교환
            swap(intArray, largest, lastUnsortedIndex);
        }

        for (int i = 0; i < intArray.length; i++) {
            System.out.print(intArray[i] + " ");
        }
    }

    public static void swap(int[] array, int i, int j) {
        if (i == j) {
            return;
        }

        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}