꿈 꾸는 누렁이

기수 정렬이다. 드디어 정리할 시간이 다가왔다.

Q. 기수 정렬에서 기수란 무엇인가?

A. 숫자 표현(진법체계)에 기준이 되는 수를 뜻한다. 예를 들자면 16진, 10진, 8진, 2진 등을 기수라고 한다.

Q. 그럼 기수 정렬은 무엇인가? 기수를 통해서 어떻게 정렬을 이뤄내는가?

A. 예제를 통해서 보겠다.

정렬이 되는 대상들을 하나의 진법 속 요소들로 가정하고,

해당 진법 배열에 값을 모두 넣은 후, 단순히 순서대로 꺼내기만 한다.

이런 식으로 동일한 기수의 요소들끼리 해당 기수의 버킷을 이용하여 정렬이 이루어지는 것이 기수 정렬이다.

중요한 것은 해당 기수의 버킷에 넣고 다시 버킷의 처음부터 순서대로 꺼낼 뿐이다. 그러니까 값의 비교가 이루어지지 않는다는 것이다! 그렇기 때문에 정렬할 대상들에 따라 반복문을 여러 번 사용해야할 수도 있고, 중간에 갑자기 진행을 끊을 수도 있으며, 정렬할 수 있는 대상이 제한이 되기도 한다.

예를 들어, 1, -5, 100 이런 요소들에 대해서는 정렬이 불가능하다. - 를 기수 버킷으로 어떻게 표현할 것이란 말인가?

다음으로 간단한 숫자 정렬하는 예제를 보겠다.

코드 및 실행 결과

이번에는 병합 정렬이다. 이게 생각보다 간단하긴 한데 복잡하다(?) 일단 시작한다.

병합 정렬이란?

병합 정렬의 기본은 다음과 같다.

1. 배열을 원소 단위로 쭉~~ 나눴다가
2. 다시 단계적으로 정렬과 동시에 결합을 반복한다.

그림으로 나타내자면 다음과 같다.

그럼 문제는 무엇이냐? 어떻게 쪼갤 것인가? 이다. arr[0] , arr[1] 이게 쪼갠 것 아닌가? 아니다. 그냥 원소에 접근한거지 쪼갠게 아니다. 

그럼 쪼갠다 라는 의미를 아주 곰곰히 생각해봐야한다. 

쪼갠다는 것은 큰 덩어리부터 시작해서 작은 단위로 나눈다는 것이고, 내가 원소 레벨까지 쪼갰다 라는 의미는 내가 지금 쪼개고 있는 진행 흐름이 원소 단위까지 접근했다! 라는 것이다.

좀 어렵지만 잘 생각해라. arr[0] 에 접근하는 것은 우리 집 강아지와 할머니도 할 수 있는 행위이다.(집에 강아지와 할머니는 없다) 이것은 쪼갠 것이 아니고 접근한 거다. 

쪼갠다는 것은 그림의 설명과 같다.

제어할 수 있는 인덱스 범위를 한정지으면 되겠다 이것이다. 그런데 내가 가만히 보니 이 쪼개는 단계가 범위만 줄어드는 것 외에는 모두 같은 짓을 하고 있는 것이다. 그렇다면 원본 배열을 던지고, 그와 함께 범위 값만 다르게 던져주면 알아서 쪼개주는 함수가 없으려나?

있다. 바로 재귀 함수이다. 바로 코드를 본다

위 함수처럼 원본과 범위를 지정하여 함수에 던져주면 알아서 반으로 쪼갤 것이다. 

위 그림처럼 될 것이다.

그렇다면 쪼갰으니 정렬과 결합을 해야한다. 다시 MergeSort 코드를 보겠다.

MergeSort는 범위를 나누어 두 토막 내고(2개의 MergeSort) 그리고 정렬과 결합을(Merge) 수행한다 라는 사실을 기억해야하며, 신뢰해야한다. 그니까 밑에 잔뜩 실행된 MergeSort 함수는 신경쓰지말고, 현재 주어진 범위들에 대해서 정렬하고 결합한다는 것이다.

위 그림처럼 밑 바닥까지 MergeSort 하면서 내려가면 더 이상 쪼개지 못하므로 각 MergeSort에게 지정된 범위에 대해서 Merge 를 통해 정렬과 결합을 수행해주고 리턴한다 그러면 한 단계 위층에서의 MergeSort들은 내부적으로 정렬된 두 덩어리를 받을 것이고 또한 그들도 Merge 를 통해 정렬과 결합을 수행해주고 리턴해준다. 언제까지? 다 합쳐질 때까지!

물론!!!! 여기서 정렬은 조상님이 와서 대신 해주는게 아니다! Merge라는 함수 내에서 이를 구현해야한다. 이는 어렵지 않으므로 코드로 확인해보면 될 것이다.

이 코드가 핵심인데, 앞 범위 토막과 뒷 범위 토막의 요소들을 모두 둘둘씩 비교하여 작은 값을 새로운 공간에 차곡차곡 넣는 방식이다. 이게 가능한 이유는 각 토막들은 아래 계층에서 이미 정렬되어 올라왔기 때문이다! (쓰면서 명확히 깨달음 ㅋ)

내가 무슨 말을 하고 있는지 모르겠다면 직접해봐라 미래의 나야

코드 및 실행 결과

----

----

머리가 참 아득해진다..

머리가 아득해지는 김에 빅오를 보자

병합 정렬 성능

최악/ 평균 / 최선에 상관없이 비교와 데이터 이동 연산을 모두 세어보면 O(n log 2 n)이다. 2는 아래 첨자 2이다.

삽입 정렬 어렵진 않은데 뭔가 설명을 적기에는 복잡하다 휴 영상이면 좋을텐데 말이지

일단 기록해둔다.

삽입 정렬이란?

삽입해서 정렬하는 것이다. 예를 들어서 

이와 같은 배열이 있을 때, 아래의 그림 순으로 설명하겠다.

그림으로 설명을 좀 대체했다. 나중에 알아먹을 수 있을란가 모르겠군.

그리고 각 그림 속 번호는 그림을 처음 봤을 때 읽어야 할 순서의 동글뱅이 번호를 뜻한다.

코드 및 결과

----

----

삽입 정렬 성능

이미 정렬되어있는 부분들이 많을수록 성능은 좋다.

최악의 경우 비교, 대입 횟수는 버블 정렬과 마찬가지로 O(n^2) 이다
왜냐하면 안쪽, 바깥쪽 반복의 횟수가 일치하기 때문이다.

최악의 경우 비교 횟수 : (n-1) + (n-2) + ... + 2 + 1 -> O(n^2)
최악의 경우 대입 횟수 : (n-1) + (n-2) + ... + 2 + 1 -> O(n^2)

버블 정렬을 학습 후에 바로 정리한다.

버블 정렬이란?

위와 같은 4칸 크기의 배열 구조가 존재하고 그 안에 값이 정렬되지 않은 채로 존재한다. 여기서 우리는 오름차순으로 값을 정렬하고자 한다.

각 화살표 시작에 적힌 원 숫자 순서대로 값을 결정하는 방법이다. 어떻게? 인덱스를 하나씩 증가시켜가면서 인덱스와 뒤 인덱스를 비교하여 값의 위치를 조정하는 것. 그것이 버블 정렬이다.

총 4개의 값이 들어왔다고 가정.

3번째 자리, 2번째 자리, 1번째 자리, 0번째 자리 순으로 값이 정해져야 한다.

(1) 3번째 자리에 들어올 값을 정하기 위해서는 [0]과 [1](0+1)을 비교, [1]과 [2](1+1)를 비교, [2]와 [3](2+1)을 비교 ( 3번 반복 ) -> 3번째 자리에 들어올 값 결정

(2) 2번째 자리에 들어올 값을 정하기 위해서는 [0]과 [1](0+1)을 비교, [1]과 [2](1+1)를 비교 ( 2번 반복 ) -> 2번째 자리에 들어올 값 결정
(3) 1번째 자리에 들어올 값을 정하기 위해서는 [0]과 [1](0+1)을 비교 ( 1번 반복 ) -> 1번째 자리에 들어올 값 결정
(4) 0번째 자리에 들어올 값은 자연스럽게 결정

결국 총 3번 반복하는데 그 반복 하나하나마다 3번, 2번, 1번 반복을 해야한다.
이를 코드로 나타낸다면

for ( ... )
{
    for( ... )
    {
        ...
    }
}

이러한 형태가 되는 것이다.

코드 구현 및 실행 결과

----

----

버블 정렬 성능

최악의 경우 비교 횟수 : (n-1) + (n-2) + ... + 2 + 1 -> O(n^2)
최악의 경우 대입 횟수 : 비교 후 바로 대입이 진행되므로 O(n^2), temp 연산으로 인한 *3 -> 3 * O(n^2) -> O(n^2)