자료구조(10) 정렬의 7가지 방법

알고리즘을 코드 레벨에서 분석만 한다면 지루할 수 있다.

이보다는 각각의 알고리즘이 갖는 특징에 관심을 두고 공부하는 것이 기억에도 오래 남고 더 의미가 있을것이다.

1-1 버블 정렬 : 이해와 구현

이해하기도 구현하기도 쉽다. 물론 이해와 구현이 쉬운 만큼 성능에는 아쉬움이 있다.

버블 정렬을 구성는 두 개의 for문의 반복조건이 핵심이다. 따라서 바깥쪽 for문의 반복조건과 안쪽 for문의 반복 조건에 대해서 대략적인 이해가 아니라 정확한 이해가 필요하다

 

1-2 버블 정렬 : 성능 평가

정렬 알고리즘의 성능은 다음 두 가지 근거로 판단하는 것이 일반적이다. "비교연산"과 데이터의 이동을 위한 "대입연산"이 정렬과정의 핵심연산이기 때문이다.

1. 비교의 횟수 : 두 데이터간의 비교연산의 횟수
2. 이동의 횟수 : 위치 변경을 위한 데이터의 이동 횟수

 

실제로 시간 복잡도에 대한 빅-오를 결정하는 기준은 "비교의 횟수"이다. 하지만 "이동의 횟수"까지 살펴보면 동일한 빅-오의 복잡도를 갖는 알고리즘간 세밀한 비교가 가능하다

 

버블 정렬의 비교연산에 대한 빅-오는 최악의 경우와 최선의 경우 구분없이 O(n2)이다.

데이터의 이동횟수연산에 대한 빅-오는 최선의 경우(정렬이 한번도 일어나지않음)와 최악의 경우(역순으로 저장되어있어서 비교의 횟수와 동일함)로 구분되는데 최악의 경우를 기준으로 하여 O(n2)이다. 사실 최악의 경우 데이터 이동횟수는 비교횟수보다 3배 더 많다(if문안에 대입연산자가 3개!) 하지만 빅-오를 판단하는 과정에서는 이를 무시한다.

 

2-1 선택 정렬 : 이해와 구현

버블 정렬보다도 쉽고 간단한 알고리즘이다.

선택 정렬은 정렬순서에 맞게 하나씩 선택해서 옮기는, 옮기면서 정렬이 되게 하는 알고리즘이다.

 

질문 : 그럼 선택 정렬은 정렬결과를 담을 별도의 메모리 공간이 필요하겠네요?

답변 : 일반적인 상식선에서 생각하면 그렇다. 하지만 데이터를 하나 옮길 때마다 공간이 하나씩 비게 된다는 사실을 기반으로, 알고리즘을 개선시키면 별도의 메모리 공간을 마련할 필요가 없다.

 

"정렬순서상 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 원래 그 자리에 있던 데이터는 빈 자리에 가져다 놓는다"

 

2-2 선택 정렬 : 성능 평가

선택 정렬의 코드만 봐도 버블 정렬과 성능상 차이가 없음을 알 수 있다. 즉, o(n2) 비교횟수를 기준으로 보면 차이가 없다. 그렇다면 데이터의 이동횟수도 버블 정렬과 차이가 없을까? 아니다! 여기에는 제법 차이가 있다.

버블 정렬이나 선택 정렬이나 데이터의 교환을 위한 세번의 대입연산이 다음과 같은 유형으로 진행된다.

• temp = A;
• A = B;
• B - temp;

하지만 존재하는 위치가 다르다. 버블 정렬의 경우에는 안쪽 for문에 속해있다. 반면 선택 정렬의 경우에는 바쪽 for문에 속해있다. 때문에 선택 정렬의 경우 n-1회의 교환이 이뤄지므로 데이터의 이동횟수는 이의 세 배인 3(n-1)이 된다. 따라서 선택 정렬의 데이터 이동연산에 대한(대입연산에 대한) 빅-오는 최악의 경우와 최선의 경우 구분없다 다음과 같다 O(n).

 

최악의 경우를 놓고 보면 버블 정렬보다 선택 정렬에 좋은 성능을 기대할 수 있겠지만, 버블 정렬은 최선의 경우 단 한 번의 데이터 이동도 발생하지 않다는 점과, 실제로 데이터들이 늘 최악의 상황으로 배치되지 않는다는 사실을 감안하면, 이 둘의 우열을 가리는 것은 무의미하다고 할 수 있다. 

 

3-1 삽입 정렬 : 이해와 구현

삽입 정렬은 관점에 따라서 별도의 메모리를 필요로 하지 않는 "개선된 선택 정렬"과 유사하다고 느낄 수 있다.

하지만 전혀 다른 방법으로 정렬을 이뤄나간다.

 

삽입 정렬은 정렬 대상을 두 부분으로, 정렬 안된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 "삽입"해 가면서 정렬을 진행하는 알고리즘이다.
 

첫 번째 데이터와 두 번째 데이터를 비교하여, 정렬된 상태가 되도록 두 번째 데이터를 옮기면서 정렬은 시작된다. 그리고 이로 인해서 첫 번째 데이터와 두 번째 데이터가 정렬이 완료된 영역을 형성하게 된다.  그리고 이어서 3번째 4번째 … 데이터가 정렬이 완료된 영역으로 삽입이 되면서 정렬을 이어 나간다. 물론 정렬된 상태로 삽입하기 위해서는 특정위치를 비워야하고, 비우기 위해서는 데이터들을 한 칸씩 뒤로 미는 연산을 수행해야 한다. 참고로 구현에 도움이 될만한 말 몇 마디를 하면 다음과 같다

• 정렬이 완료 영역의 다음에 위치한 데이터가 그 다음 정렬대상이다
• 삽입할 위치를 발견하고 데이터를 한 칸씩 로 밀수도 있지만, 데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾아를 찾을 수도 있다.(어차피 정렬된 영역에서 삽입의 위치를 찾는 것이니, 삽입위치를 찾으면서 삽입을 위한 공간의 마련을 병행 할 수 있는 것이다)

삽입위치를 찾는 과정과 삽입을 위한 공간마련의 과정을 구분할 필요가 없다.

 

3-2 삽입 정렬 : 성능 평가

삽입 정렬은 정렬대상의 대부분이 이미 정렬되어 있는 경우 매우 빠르게 동작한다.

정렬대상이 완전히 정렬된 상태라면, 안쪽 for문의 if~else문의 조건은 항상 "거짓"이 되어 break문을 실행하게 된다.

따라서 데이터의 이동도 발생하지 않고 if~else의 조건비교도 바깥쪽 for문의 반복횟수 이상 진행되지 않는다.

하지만 최악의 경우를 고려하면, 이 역시 앞서 보인 두 정렬들과 다를 바 없다.

최악의 경우 안쪽 for문의 if~else문의 조건은 항상 "참"이 되어 break문을 단 한번도 실행하지 않는다.

따라서 바깥쪽 for문의 반복횟수와 안쪽 for문의 반복횟수를 곱한 수만큼 비교연산도, 이동연산도 진행되므로, 이를 근거로 비교연산과 이동연산에 대한 빅-오가 다음과 같다 O(n2)

 

4-1 힙 정렬 : 이해와 구현

앞서 소개한 단순한 정렬 알고리즘도 정렬대상의 수가 적은 경우 효율적으로 사용할 수 있어서 나름의 의미를 지닌다. 하지만 정렬대상 수가 적지 않은 경우에는 보다 만족스러운 결과를 보장하는 알고리즘이 필요하다.

 

힙 정렬은 힙의 다음 특성을 활용하여 정렬하는 알고리즘이다

"힙은 루트 노드에 저장된 이 가장 커야 한다" 물론 이는 "최대 힙"의 특징이다.

하지만 우리는 다음 특징을 갖도록 힙을 구성할 수 있다 "힙의 루트 노드에 저장돤 값이 정렬순서상 가장 앞선다"

 

힙은 저장의 목적 이외에도 정렬의 도구로도 사용이 될 수 있다.

4-2 힙 정렬 : 성능 평가

언뜻 보면 저장된 데이터를 죄다 힙에 넣었다가 다시 꺼내기 때문에 성능상 이점이 별로 없어 보이지만,

힙 정렬은 지금까지 소개한 정렬들 중 가장 좋은 성능을 보이는 알고리즘이다.

• 힙의 데이터 저장 시간 복잡도 : o(log2n)
• 힙의 데이터 삭제 시간 복잡도 : o(log2n)

따라서 삽과 삭제를 하나의 연산으로 묶는다면, 이 연산에 대한 시간 복잡도는 다음과 같이 결론을 낼수있다.

O(2xlog2n)

하지만 숫자2는 빅-오에서 무시할만한 수준이므로 삽입과 삭제를 하나의 연산으로 묶는다 해도, 이 연산에 대한 시간 복잡도는 여전히 다음과 같다 o(log2n)

 

그럼 정렬과에 대한 시간 복잡도는 어떻게 될까? 정렬대상의 수가 n개라면, 총 n개의 데이터를 삽입 및 삭제해야하므로 o(log2n)에 n를 곱해야한다 O(nlog2n) 여러분이 보기에 nlog2n과 n2에는 별 차이가 없다고 생각할 지 모르겠다. 하지만 n에 몇몇 숫자만 넣어도 그 차이를 바로 알 수 있다. 둘 사이에는 매우 큰 차이가있다.

 

참고로 말하자면 O(n2)의 성능을 보이는 알고리즘을 O(nlog2n)의 성능을 보이도록 개선한다면, 이는 낮은 성능으로 인하여 현실적으로 활용하기 어려운 알고리즘을 활용이 가능한 수준으로 개선한 결과로도 평가 받을 수 있다.

 

5-1 병합 정렬 : 이해와 구현(재귀함수때문에 이해가 어려워서 패스!)

병합 정렬은 "분할 정복"이라는 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법이다. 분할 정복이란 말그대로 복잡한 문제를 복잡하지 않은 문제로 "분할 하여 정복"하는 방법이다.

• 1단계 분할 : 해결이 용이한 단계까지 문제를 분할해 나간다
• 2단계 정복 : 해결이 용이한 수준까지 분할된 문제를 해결한다.
• 3단계 결합 : 분할해서 결합한 결과를 결합하여 마무리 한다.

기본원리

"8개의 데이터를 시에 정렬하는 것보다, 이를 둘로 나눠서 4개의 데이터를 정렬하는 것이 쉽고, 또 이들 각각을 다시 한번 둘로 나눠서 2개의 데이터를 정렬하는 것이 더 쉽다"

 

"병합 정렬은 데이터가 1개만 남을 때 까지 분할을 해 나간다. 데이터가 2개만 남아도 정렬을 할 필요가 있지만, 데이터가 1개만 남으면 그 조차 불필요해지기 때문이다"

 

언뜻보면 병합 정렬은 나누는 것이 핵심인것 처럼 보인다. 물론 나누는 것이 핵심은 맞다. 하지만 실제 정렬은 나눈 것을 병합하는 과정에서 이뤄진다.

 

우선 나뉘었던 둘을 정렬순서를 고려하여 하나로 묶는다. 그리고 나뉘기전 한덩이였던 데이터를 또 정렬순서를 고려하여 하나로 묶는다. 분할이 총 3회 진행되었다면, 묶는 과정도 총 3회에 걸쳐 진행된다. 그리고 그 결과 정렬이 완료된다.

 

질문 : 분할의 과정에서 하나씩 구분이 될 때 까지 둘로 나누는 과정을 반복하는 이유는 무엇인가? 처음부터 하나씩 구분을 해버리면 더 간단하지 않겠는가?

답변 : 재귀적인 구현을 위한 것!!

5-2 병합 정렬 : 성능 평가(log에대한 지식이 없어서 패스!

 

6 퀵 정렬 : 이해와 구현

퀵 정렬도 병렬 정렬과 마찬가지로 "분할 정복(DAC)에 근거하거 만들어진 정렬 방법이다. 실제로 퀵 정렬 역시 정렬 대상을 반씩 줄여나가는 과정을 포함한다. 퀵 정렬은 그 이름이 의미하듯이 평균적으로 매우 빠른 정렬의 속도를 보이는 알고리즘이다!

 

참고로 퀵정렬은 글보다 그림으로 이해하는 편이 낫다. 글로 설명하기에 난해한 부분이 많다.(그림 없음 ㅅㄱ)

 

퀵  정렬의 기본원리

• left : 정렬대상의 가장 왼쪽 지점을 가리키는 이름
• right : 정렬대상의 가장 오른쪽 지점을 가리키는 이름
• pivot : 피벗이라 발음하고 중심점, 중심축의 의미를 담고있다(가장 왼쪽에 위치한 데이터를 피벗으로)

(피벗은 정렬하는데 필요한 일종의 '기준'이라 할 수 있다. 피벗이 데이터의 가장왼쪽으로 정한것은 그냥 우리의 결정일 뿐이다=아마 편해서 그렇겟지? tip= 피벗을 어디에 잡느냐에 따라 알고리즘의 성능 차이가 생긴다.)

• low : 피벗을 제외한 가장 왼쪽에 위치한 지점을 가리키는 이름 (중요한 역할)
• high : 피벗을 제외한 가장 오른쪽에 위치한 지점을 가리키는 이름 (중요한 역할)

(결적으로 right와 high는 같은 위치를 가리킨다. 하지만 피벗을 가장 왼쪽 데이터가 아닌 가장 오른쪽 데이터로 결정한다면 이야기는 달라진다)

 

low는 오른쪽, high는 왼쪽으로 이동시킨다. 이때 이동의 기준은 다음과 같다.(오름차순 정렬의 대상으로)

• low의 오른쪽 방향 이동 : 피벗보다 큰 값을 만날 때까지
• high의 왼쪽 방향 이동 : 피벗보다 작은 값을 만날 때까지

오름차순 정렬이 아니라 일반화시킨다면

• low의 오른쪽 방향 이동 : 피벗보다 정렬의 우선순위가 낮은 데이터를 만날 때까지
• high의 왼쪽 방향 이동 : 피벗보다 정렬의 우선순위가 높은 데이터를 만날 때까지

여기서 low와 high의 이동은 완전히 별개이다.

 

피벗이 정렬 대상의 한쪽 끝에 치우치는 경우 최악의 경우를 보인다.

정렬 과정에서 선택되는 피벗의 수가 적을수록 최상의 경우에 해당이 된다!

피벗은 가급적 중간에 해당되는 값이 선택되어야 좋은 성능을 보인다!

7-1 기수 정렬 이해

"기수 정렬은 정렬순서상 앞서고 뒤섬의 판단을 위한 비교 연산을 하지 않는다" 우선순위를 판단하기위한

비교연산은 핵심중에 핵심이다. 앞서 소개한 모든 정렬 알고리즘은 이 연산을 포함하고있다. 뿐만 아니라

알고리즘의 복잡도도 이 연산을 근거로 판단해왔다.  그런데 기수정렬은 이러한 유형의 비교연산을 하지않고서도 정렬을 할 수 있다! 또한 정렬 알고리즘은 이론상 성능의 한계는 O(nlogn)으로 알려져있는데, 기수 정렬은 이러한 한계를 넘어설 수 있는 유일한 알고리즘이다!

 

단점

적용할 수 있는 범위가 제한적!

길이가 같은 데이터들을 대상으로 정렬이 가능하지만, 길이가 같지 않은 데이터들은 정렬이 불가!

(물론 정렬 대상 및 기준에 따라서 특정 알고리즘을 적용하여 길이가 다른 데이터들도 정렬은 가능하다) 그렇지만 매우 제한적이라 별도의 알고리즘을 고민하고 효율의 문제를 감수하면서까지 기수 정렬을 사용할 이유가 있겠는가?

• 가능 : 배열에 저장된 1,7,9,5,2,6을 오름 차순으로 정렬하라!
• 가능 : 영단어 red, why, zoo, box 사전편찬 순서대로 정렬하여라!
• 가능 : 42, 715
• 불가능 : 배열에 저장된 21, -9, 125, 8, -136, 45를 오름차순으로 정렬하라!
• 불가능 : 영단어 professionalism, hydorxproline, simple을 사전편찬 순서대로 정렬하여라!

 

기수(radix)란 주어진 데이터를 구성하는 기본 요소를 의미한다. 예를들어 2진수는 0과 1의 조합으로 데이터를 표현하니 2진수의 기수는 0과 1이다. 유사하게 10진수는 0부터 9까지의 숫자 조합으로 데이터를 표현하니 0부터 9까지의 숫자가 10진수의 기수가 된다.

 

LSD 기수 정렬(Least Significant Digit) : "덜 중요한 자릿수"부터 정렬을 진행해 나간다는 의미를 담고있다.

 

데이터들의 마지막 자릿수를(덜 중요한) 가지고 우선순위를 비교하여 버킷에 차례대로 담고 들어간 순서대로 꺼내면 정렬이된다(데이터가 둘 이상일때 FIFO 즉 Qqueue) . 이렇게 정렬이된 데이터를 첫번째 자리수까지 반복진행하면 정렬이 완성된다.

 

LSD 단점(단점아닌 단점) : 반드시 끝까지 가야한다. 중간에 정렬이 완료될 수 없다

LSD 장점(장점아닌 장점) : 작은 자릿수에서 시해서 큰 자릿수까지 모두 비교를 해야 값의 대소를 판단할 수 있다. 비교 중간에 대소를 판단하는 것은 불가능하다 가장 영향력이 큰 자릿수를 마지막에 비교하니 마지막까지 결과를 알 수 없는 것이 이 방법의 단점(MSD는 중간에 정렬이 완성될 수 있다)인데 이러한 단점이 프로그래밍을 하는데 있어서는 장점이 된다.

 

MSD 기수 정렬(Most Significant Digit) : 가장 중요한 자릿수부터 정렬을 진행해 나간다는 의미를 담고있다

 

질문 : LSD와 방만 다르고 정렬의 과정은 같다고 보면되나요!?

답변 : ㄴㄴ 진행방향만 바꿔서 진행해보면 알겠지만 정렬이 엉뚱하게 이뤄진다

 

MSD의 장점(장점아닌 장점) : 반드시 끝까지 가지 않아도 된다. 중간에 정렬이 완료될 수 있다.

MSD의 단점(단점아닌 단점) : 모든 데이터에 일괄적인 과정을 거치게 할 수 없다! (,즉 굳이 안쓴다 LSD쓰지)

 

2번째 자릿수를 가지고 MSD 기수 정렬을 한다고 가정해보자

224와 232 정렬순서는 이미 두 번째 과정에서 판별이 났다. 두 번째 자릿수인 2가 3보다 앞서기 때문이다. 그리고 그 결과는 세 번째 영향을 받지않는다!! 따라서 여기서 멈췄어야 했다. 멈추지 않고 마지막 단계까지 진행을 했기 때문에 잘못된 결과를 초래한 것이다. 이러한 오류를 범하지 않으려면, MSD 방식에서는 중간에 데이터를 점검해야 한다. 정렬대상의 일부는 다음단계로 넘어가되 일부는 넘어가면 안 되는 상황이 빈번히 등장하기 때문이다. 따라서 구현의 난이도는 LSD에 비해서 상대적으로 높다. 게다가 중간에 성능에 데이터를 점검해야 하므로 성능의 이점도 반감될 수 있다.

7-2 기수 정렬 : 성능평가

질문 : 성능은 MSD 방식이 월등하지 않은가요?

답변 : 그렇지 않다! 우선 LSD와 MSD의 빅-오는 같다. 물론 MSD의 경우 정렬의 과정에서 단축될 수 있어서 성능의 향상을 조금이라도 기대할 수 있지만, 모든 데이터에 일괄적인 과정을 거치게 할 수 없기 때문에 추가적인 연산과 별도의 메모리가 요구된다. 따라서 일반적인 상황이라면 굳이 MSD 방식을 고집할 이유가 없다.

 

기수 정렬은 비교연산이 핵심이 아니라, 오히려 버킷으로의 데이터 삽입과 추출이 핵심이다. 따라서 이 정렬의 시간 복잡도는 삽입과 추출의 빈도수를 대상으로 결정해야 한다.

 

버킷을 대상으로 하는 데이터의 삽입과 추출을 한 쌍으로 묶으면, 이 한 쌍의 연산이 수행되는 횟수는 다음과 같다 : MaxLen(가장 긴 데이터의 길이) x num(데이터의 개수) 따라서 정렬대상의 수가 n이고, 모든 정렬대상의 길이가 i이라 할때, 시간 복잡도에 대한 기수 정렬의 빅-오는 다음과 같다. O(ln) 물론 이는 O(n)으로 보아도된다. 이로써 기수 정렬은 O9(nlog2n)인 퀵 정렬보다 뛰어난 O(n)의 성능을 보임을 확인하였다. 물론 적용 가능한 대상이 제한적이라는 단점이 있지만 말이다.