티스토리 뷰

5. 정렬 - 분포수세기, 퀵 정렬, 기수 정렬, 힙 정렬, 병합 정렬



5. 분포 수 세기

 Distribution Counting


각각의 자료의 수를 세어 들어갈 위치를 계산하는 방법이다. 자료의 종류만큼의 배열을 준비해야 한다.

기수정렬에서 응용되어 엄청난 성능을 발휘한다고 한다. 메모리를 많이 먹는다 뿐이지 그렇게 나쁘진 않다.

다만 사용 조건이 좀 까다로워서 기수 정렬에서 응용하는 것 같다.

또 하나, 이건 Single byte string search에선 유용할 것 같다.. 다만 Everything처럼 부분 문자열검색을 하는데 쓰긴 어렵겠지. 그건 따로 String search 알고리즘을 배워야 하나,...


이름

'세어서' 정렬을 하니까 그런가.


방법

나름 설명: 각각의 원소 종류들 개수를 세어 누적도수분포표를 만든다. 그러면 각각의 종류의 원소들이 정렬되었을 때 맨 오른쪽자리를 알 수 있다. 오른쪽부터 다시 세면서 누적도수분포표를 깎아가며 채워넣는다.


특징

1. 메모리를 먹는다. 사본을 생성하기 때문에 입력자료만큼의 메모리가 추가로 필요하고, 또 자료의 종류만큼의 메모리가 필요하다.

2. 시간복잡도는.. 교재엔 안 나오지만 O(N)일 것 같다. 그리고 입력자료의 배열에 영향을 받지 않는다. (즉, 자료의 크기에만 영향을 받는다.)

3. 안정성이 있다.

4. 결론: 분포 수 세기는 데이터의 종류가 적은 (혹은 중복된 자료수가 많은) 자료에 적합하다.

5. if문이 없는 정렬법이라 그런지 굉장히 빠르다.


최적화

딱히 최적화라기보다, 저 안정성이라는게 앞에서부터 채워넣는방식으로 알고리즘을 짜면 사라진다. 안정성을 부여하기 위해 뒤에서부터 자료를 채워넣는다.



6. 퀵 정렬

 Quick sort

분할해서 정복한다는 개념에선 쉘 정렬과도 비슷하다. 또한 어떤 임의의 값이 성능에 영향을 끼치는 것도 유사하다면 유사하겠지.

만들려고 할 때 괜히 욕심부려서 배열 안 쓰고 포인터 썼다가 피봄. 아직 미숙한 건가...

일반적으로 빠른 정렬이고, 가장 많이 쓰인다.


이름

일반적으로 빠른 정렬이라서 그런가 봄.


방법

나름 설명: 어떤 기준값을 잡고, 그 값보다 크거나 같은 값을 왼쪽에서부터, 작거나 같은 값을 오른쪽에서부터 찾음. 양쪽에서 둘 다 찾았는데 서로 뒤바뀌지 않았으면 교환. 좌우가 뒤바뀌었으면 양 옆 구간을 분할해서 재귀호출. 사이즈가 1이면 종료.


특징

1. 안정성이 없다. 굉장히 빠르다. 재귀호출이 메모리를 먹는다.

2. 시간복잡도는 가장 이상적일 때 을 가진다고 하고 최악의 경우에는 까지도 간다고 한다. 하지만 최악의 경우가 랜덤한 경우에 있는 터라 역시 발생하긴 쉽지 않다. 하지만 값을 무성의하게 정했을 때는... 모르지.

3. 일반적으로 많이 쓰이는 이유는 뭘까? 복잡한데;;


최적화

책에서 비재귀화를 첫번째로 다뤘다. 하지만 내 실험결과 비재귀화하려고 push(), pop()쓰는 건 이미 뭔가 이상하기 때문에.. ㄱ-.

함수 호출을 없애려고 함수 호출을 2개로 늘리다니? 말도 안 된다. 실험해봐도 저 push, pop조합이 훨 느렸다.

그 밖에 원소가 일정개수 이하일 경우 그냥 삽입 정렬을 시도하는 방법이 있었는데, 이건 꽤 좋았다. 성능 향상이 확실하다. 그 자잘한 구간을 재귀호출하느니 삽입정렬이 차라리 낫겠지.

또 축값Pivot을 잘 지정하는 방법이 무작위로 결정하는 것과, 세 값을 추출해 그 평균을 구하는 것이 있었는데, 나는 그냥 맨 앞·뒤 두 값의 평균만 이용했다. (이정도면 정렬알고리즘 공격도 가능하겠지 ㅡㅡ;)



7. 기수 정렬

 Radix sort


컴퓨터의 자료구조가 기본적으로 Digital이라는 발상에 기초. 비트연산으로 정렬을 한다.

기수교환정렬Radix exchange sort와 직접기수정렬Straight radix sort가 있다.


이름

기수 수학용어를 네이버 사전에서 찾아보니.. 2를 기수로 하는게 디지털자료. 그 특성을 이용해서 기수정렬이라 하나보다.

숫자 자리 표시법에서 어떤 자리의 가중값(weight)으로, 이 수를 곱하면 바로 윗자리에 대한 가중값이 얻어지는 정수.10 진법(decimal notation)에서, 예를 들면 256은 2×102+5×101+6×100으로 표현할 수 있는데, 이 경우 10을 기수라고 한다.


방법

나름 설명

기수교환정렬: 기준점을 각각의 비트 하나씩으로 잡고 퀵 정렬.

직접기수졍렬: 각각의 비트를 좀 나누고 뒤에서부터 분포수세기. (앞에서부터 하려면 퀵 정렬식으로 해야돼서.. 복잡해짐)


특징

0. 공통점: 자료의 비트 수가 적어야 쓰기 편하다. 비트를 직접 비교하므로. 대신 무지 빠르다.


기수교환정렬

1. 퀵 정렬의 속성을 가진다. 상속같은 개념인가 ㅋㅋ. 일단 비트를 사용한다는게 특징일 뿐이지 방법 자체는 퀵 정렬이니까.

2. 그러므로 안정성이 없다. 다만 기준값가지고 골때리는 일은 없다. 비트가 1 or 0인지만 판단하니까.


직접기수정렬

1. 분포 수 세기의 속성을 가진다. 즉, 입력자료의 사본을 추가로 할당한다.

2. 안정성이 있다. 뭐 분포 수 세기의 속성은 전부 가지고 있다.


최적화

이 책은 최적화만 나오면 비재귀화가 감초로 나오는데... 물론 패스한다. 나머지 최적화 얘기는 없었다.

근데 직접기수정렬에서 안정성이 있기 때문에 그냥 뒤에서부터 2비트씩 정렬하는 방법을 쓰더라. (물론 시대가 다르기 때문에 나는 1바이트씩 비교하는 방법을 썼다.) 그렇게하면 확실히 구현이 간단해지고 최종적으로도 안정성이 있다.

근데 앞에서부터 비교하면서 퀵 정렬의 분할방법을 쓰는 건 어떨까? 분할 + 분포 수 세기. 안정성은 잃어버리겠지만 혹시 더 빨라질지도...? 지금은 구현하지 않았고. 나중에..



8. 힙 정렬

 Heap sort


힙이 뭔지 먼저 알아야 한다... 자료구조개념을 다시 알아봐야겠다.

힙정렬 부터 점점 이해도가 떨어지는 느낌이다 ㅡㅡ.... 나중에 실전에서 복습이라도 해야하나.


우선순위 큐Priority queue: 특정한 자료구조를 의미하는 게 아니라, 자료의 각각이 순위를 가지고 관리되는 자료구조의 추상적 개념.

예를들어 스택, 큐... 이 힙도 거기 들어가나 보다.

일반적으로 다음의 7가지 동작이 정의되다고 한다.

1. 삽입Insert: 우선순위 큐에 새로운 자료를 삽입한다.

2. 제거Remove: 순위가 가장 높은 자료를 제거한다.

3. 생성Construct: N개의 자료로 우선순위 큐를 만든다. N번 삽입과 같다.

4. 대치Replace: 순위가 가장 높은 자료와 새로운 자료를 바꾼다. 제거 + 삽입과 같다.

5. 변경Change: 자료의 순위를 변경한다. 삭제 + 삽입과 같다.

6. 삭제Delete: 임의의 자료를 삭제한다.

7. 결합Join: 두 우선순위 큐를 결합하여 큰 우선순위 큐를 만든다.


힙이란?

우선순위가 키 값의 크기에 의해 정해지는 자료구조라고 한다. 키 값은 데이터를 말하는 것 같다.

어떤 키가 다른 특정한 두 키보다 큰 값을 가져야 한다는 조건이 있는데, 그 조건만 만족하면 힙이 되는 것이다.

여기서 '두 키'라는 말이 있기 때문에 자료구조로 구현하면 이진트리로 자연스레 구현된다.

교재에서 힙의 뿌리는 전체 레코드중에서 가장 큰 레코드가 된다. 라고 했는데, 사실 오름차순이든 내림차순이든 상관 없는 것 같다. 위키에 따르면.

(잠깐, 이게 꼭 순위대로 정렬이 된 상태는 아니네? 양쪽의 순서는 따지지 않아..)

새로 삽입된 자료가 힙의 규칙에 맞게 지위가 상승하는 것을 UPHEAP, 반대로 끌어내리는 것을 DOWNHEAP이라고 한다.


층별순으로 순위를 매기면 다음의 관계를 얻을 수 있다.

1. 번호 j를 갖는 노드의 부모의 번호는 j/2

2. 번호 j를 갖는 노드의 왼족자식의 번호는 j*2, 오른쪽 자식은 j*2+1

3. 힙 자료의 개수 n의 절반(n/2)까지가 내부 노드.


일반 나무구조는 균형이 잡혀있지 않은 경우도 있기 때문에 배열로 구현할 때 공간의 낭비가 심하다. 하지만 힙은 규칙으로 거의 완전이진트리를 형성하므로 배열로 구현하기 편하다. 그 배열의 첨자로 사용하기 위해 저렇게 층별순위를 매겨두는 것이다.


근데... 구현은 편한지 몰라도 내겐 좀 어려운 걸까 ㅡ,.ㅡ


이름

Heap.. 영어사전에서 찾아보니까 '수북히 쌓아놓은 더미'라고 한다.


방법

나름 설명: 힙을 만들면 그 힙의 최상위 값은 항상 최소·최대값 중 하나를 가지게 된다. 힙을 유지하면서 그 최상위 값만 뽑아 순서대로 저장하면 끝. 그 힙을 만들 때 기존의 배열이 있는 공간을 사용할 수 있으므로 추가적인 메모리가 필요치 않다.


특징

1. 매우 빠르다. 시간 복잡도가 임이 밝혀져 있다. 즉, 최악의 경우가 뜨더라도 그렇게 많이는 느려지지 않는다. 하지만 검색해보니 실제로는 퀵 정렬보다 평균적인 소요시간에서 좀 떨어지는 듯 하다.

2. 복잡하다. 아니, 구현이야 굉장히 깔끔하지만 내가 이해하기에... ㅠㅠ 익숙해지면 나으려나.

3. 성능이 좋은데도 추가적인 메모리가 필요없다.

4. 안정성은 없다.


최적화

하향식으로 힙을 만들 수도 있고, 상향식으로도 만들 수 있나 보다. 상향식으로 만드는 게 소스 양을 반으로, 연산을 2/3으로 줄여준다.


퀵 정렬과 힙 정렬의 비교분석: http://kldp.org/node/110384

내용 중 일부를 추려본다.


winner님

힙 구조를 만드는 데 필요한 시간은 O(N)이고, 깨진 구조를 바로잡는데 걸리는 시간은 O(NlogN), 최대원소를 찾는 시간은 O(1)이다.   거기다 필요 공간도 O(1)이므로 매우 효율적인 정렬이 가능하지만, 정렬 특성상 자료에 따라 시간을 단축하는 것이 없고, 힙 재조정 연산이 들어가면 캐시 이용이 힘들어져 퀵소트에게 밀리게 되었다.

이런 이유로 힙 정렬은 우선순위큐에 많이 쓰이는데, 최대원소를 빼내면서 원소를 중간마다 추가할 수 있어야 한다는 요구사항을 반영한 자료구조이므로 Heap이 아주 적당하다는 게 이유이다.

(힙이 적당히 정렬된 상태란 말도 있었다. 힙을 구축했다고 하더라도 실제론 정렬된 상태가 아니라 최대원소를 즉각 뽑아낼 수 있는 상태인 것 뿐이다. 그러므로 Heap이 우선순위 큐에 어울리며, 실제 삽입과 삭제가 빈번한 자료에서의 정렬에 쓴다고 하면 힙을 분리 시켜야 할 테기 때문에 사본을 떠야 할 것이다.)


jick님

힙소는 그런 거 다 필요없이 시작과 끝이 있는 1차원 배열 하나 덜렁 던져주고 "이거 소트해줘" 하는 상황에서도 아주 간편하게 써먹을 수 있습니다. 

(힙 정렬하고 쉘 정렬하고 비슷하지만 쉘 정렬은 간격을 설정하는 문제가 있기 때문에 즉흥적으로 써먹긴 힘들지도.)

vuccell님

퀵 정렬이 되는 경우는 실제로 거의 없고, 평균적인 수준에서 힙 정렬은 퀵 정렬보다 20%느리고, 최악의 경우에도 거기서 20%더 느리다. 이른바 보험같은 검색방식. 역시 평균적인 상황이 중요하므로 퀵 소트를 쓰는 것이다.

9. 병합 정렬

 Merge sort


교재에서 순차접근을 하기 때문에 외부정렬에 쓰이기 편하다고 한다.



이름

배열을 나눠서 정렬한 다음 합친다. 쉘 소트하고 다른 점은 간격을 두고 분할하는 게 아니란 것.


방법

나름 설명: 처음엔 1사이즈로 배열을 분할한다. 그 중에서 순서대로 2개의 배열을 선택하고 두 배열 맨 앞을 비교해서 (1개면 이미 정렬된 것이나 마찬가지니까.) 작은 것부터 사본에 복사한다. 그런 식으로 2개의 배열을 사본 배열 1개로 정렬한다. 그걸 원본 배열 끝까지 반복. 반복 했으면 사이즈를 키워서 반복. (가다가 짝이 안 되는 건 알아서. ㄱ-)


특징

1. 빠르다. 시간 복잡도가 임이 밝혀져 있다.

2. 안정성이 있다.

3. 사본을 떠야 하기 때문에 입력자료만큼의 추가적인 메모리가 필요하다. 즉, 공간복잡도 O(N).


최적화

교재에선 배열 바꿔치기할 때 원소 하나하나 복사하지 말고 포인터만 교체하라고 하는데 그건 기본 아닐까.



교재엔 외부 정렬External sort 챕터가 하나 더 끼어있었다. 외부장치는 느리고 순차접근만 가능하니까 임시파일로 쪼개서 입력 받는데 그걸 잘 내부정렬하여라... 라는 내용이었나. 쓸 필요를 느끼지 못했다.



마지막으로, 이 모든 것이 구글링하면 더 잘 일목요연하게 나온다는 거... 그냥 자기만족적 복습이지 뭐.


기념으로 만든 실행프로그램을 올리겠다. 지금까지 실습한 정렬을 그래프로 표현하는 프로그램이다.

SortSimulation.exe는 그냥 정렬 실행

SortSimulation_delayed.exe는 정렬되는 모습을 보여줌. 하지만 일부러 슬립함수를 넣었기 때문에 벤치마크 불가.

근데 알고리즘 비교하려해도 대충만든 게 한둘이 아니기 때문에 비교거리도 안 됨;;



SortSimulation.exe


SortSimulation_delayed.exe


나중에 정렬의 특성을 표로 만들어 볼 예정.


이름 시간 복잡도 공간 복잡도 난이도 방식 범용성 안정성 활용성
거품 정렬
선택 정렬
삽입 정렬
쉘 정렬
퀵 정렬
분포 수 세기
기수 교환 정렬
직접 기수 정렬
힙 정렬
병합 정렬

댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함