C로 배우는 알고리즘 - 복습 겸 요약 6

5. 정렬 알고리즘 - 선택·삽입·거품·쉘 정렬

음... 확실히 정했다. 혼연C하고 이 책을 동시에 봐야겠다. 계속 그랬지만 본격적으로 그래야 겠다.

근데 이렇게 마음먹자마자 혼연C 알고리즘 부분이 빈약해보이는 건 무슨 일이지;;

이 부분도 역시 예전엔 조금 알았는데 고등어 생활 중 많이 잊어버렸다. 다시 복습해야.. ㅠㅠ

정렬알고리즘은 C로...책으로 보니까 굉장히 신기하다. 종류도 많을 뿐더러 특히 그래프로 정렬되는 과정을 보여주는 그림이 가장 신기했다. o_o

그래서 가능한 한 WinAPI를 사용해 그림으로 표현하는 프로그램을 짤 생각이다.

그럼 ㄱㄱ

1. 개요

정렬을 왜 할까? 검색하려고. 즉 검색하려고 정렬을 배운다.

오름차순Ascending order은 뒤로 갈수록 값이 커지는 방향으로 배열하는 것을 의미하고

내림차순Descending order은 뒤로 갈수로 값이 작아지는 식으로 배열하는 것을 뜻한다.

한글로 익히면 헷갈리는 경우가 많으므로 영어 단어를 떠올려야 겠다.

정렬은 퀵 소트라는 것이 일반적으로 가장 빠르다고 알려져있지만, 100%그런 것은 아니다. (ex. 이미 정렬된 자료의 경우 플래그 버블보다도 느릴 수 있다.) 결국 상황에 가장 적절한 알고리즘을 고르는 안목이 필요하다.

정렬의 방법론

컴퓨터는 사람처럼 한 번 딱 보고 정렬할 수 없다. 컴퓨터는 판단(=비교) · 교환 두가지 동작을 할 수 이으며, 정렬 알고리즘은 이 두가지를 어떻게 섞는지에 대한 방법론이다.

정렬 알고리즘의 다양성

간단한 알고리즘: 선택 정렬, 삽입 정렬, 거품 정렬, 쉘 정렬

복잡한 알고리즘: 퀵 정렬, 기수 정렬, 힙 정렬, 병합 정렬

외부 정렬: 정렬의 대상이 되는 레코드들이 디스크나 테이프같은 컴퓨터 외부에 있으면.

내부 정렬: 정렬의 대상이 되는 레코드들이 메모리같은 컴퓨터 내부에 있으면.

직접 정렬: 레코드 자체를 옮김 (C로 표현하자면 구조체)

간접 정렬: 레코드의 지시자를 옳김 (C로 표현하자면 배열첨자나 포인터) - 대부분 이걸 쓰겠지. int가 아닌 이상.

정렬 기본 방법에 따른 분류

삽입: 삽입 정렬, 쉘 정렬

교환: 거품 정렬, 퀵 정렬, 기수 교환 정렬

병합: 병합 정렬

선택: 선택 정렬, 힙 정렬

세기count: 분포 수 세기, 직접 기수 정렬

안정성이란?

당나귀P2P에서 안정성있는 정렬알고리즘을 사용한 것 같다.

내가 사용한 예로는, 최고화질의 영화를 찾고 싶다면 일단 파일크기로 내림차순 정렬을 하고 파일 종류로 정렬을 하는 것이다.

그러면 영화파일끼리 묶이게 되는데, 그 영화파일의 맨 위에는 가장 파일크기가 큰 것 (즉 고화질)이 오게 된다.

이렇게 우선 순위가 같은 자료에 한해서 이전의 정렬결과가 보존되는 것을 '안정성이 있다'라고 한다.

일반화된 정렬함수

이 책에선 void*만 말하고 있는데... 지금은 C++시대다. 함수 포인터를 넘겨주는 건 객체로 바뀌겠지. anachronistic.

정렬을 시뮬레이션하기 위해선 일단 난수 배열이 필요하다.

여기선 큰 문제가 안 되지만, 난수에 대해선 불평할 게 하나 있다. 나중에 따로 포스팅 하기로 한다. (그냥 내 무지에서 나온 걸지도 모르지만)

이제부터 모두 오름차순 정렬기준으로 쓴다.

2. 선택 정렬

Selection sort

오타 발견.. 322p 2. i가 n-2가 되면 끝낸다. n-1아닌가 싶다.

WinAPI짜는 거 GetExitcodeThread MSDN 잘못 읽어서 좀 삽질했다. 아나. 난 왜 이런식이지.

이름

최소값을 '선택'해서 교환하는 방법을 써서 선택정렬인가 보다.

방법

내 나름 설명: 일단 첫 번째 원소를 고르고 거기에 들어갈 최소값 원소를 쭉 검색한다. 끝까지 검색했으면 나온 최소원소(중 맨 마지막 원소)와 첫 번째 원소를 교환한다. 이제 두 번째 원소를 첫번째 원소로 두고 반복한다. 이걸 비교 대상원소가 1개가 될 때까지 반복한다.

특징

1. 간단하고 느리다. 안정성은 없다. 메모리 사용은 O(1)이다. 소요시간은 아마도 Θ(N²).

즉 자료의 크기가 같다면 정렬 시간은 동일하다.

2. 교환의 횟수가 가장 작은 편에 속한다. 

비교횟수가 N(N-1)/2 정도이다. 읽기는 많이 하지만 교환 횟수는 많아봐야 N번이다. 읽기는 상관 없지만 쓰기가 극단적으로 느린 매체에 대해 외부정렬을 시도하는 경우 유용할 수 있을 것 같다. 큰 레코드의 직접 정렬도 마찬가지다.

3. 순차적으로 정렬이 된다.

예를 들어, 프로그램이 로딩되면 맨 먼저 보이는 화면은 가장 처음의 항목들을 보여주기 마련이다. 선택정렬을 이용하면 자료의 가장 처음부터 순서대로 정렬되기 때문에 빠른 로딩에 도움이 될 것 같다. 이건 내가 만든 그림으로 표시해주는 프로그램을 봐도 알 수 있다.

내가 이걸 구현할 때 문득 이중 루프 중 안쪽의 루프의 순회방향을 바꿔주면 선택정렬에도 안정성이 생기지 않을까 생각해봤다.

하지만 다시 잘 생각해보니 교환하는 요소는 안정성을 유지할 수 있어도, 교환 당하는 요소(최소값이 아닌 요소)는 안정성을 보장 못하더라.

3. 삽입 정렬

Insertion sort

근데 교재에 예제코드 있는거 a[j-1] > t && j > 0 이거 Access violation걸릴 수 있는 거 아닌가 ㅡㅡ?

쇼트 서키트를 쓴다 해도 앞뒤 순서 좀 바꿔야 할 것 같은데, 딱히 에러는 안 나는게... 뭐지.

교환이 많음에도 별로 선택정렬에 비해 성능이 뒤지지 않는 건... 최악의 경우가 아닌 한 끝까지 밀어넣을 필요가 없어서겠지.

게다가 연결 리스트를 쓰면 정말 교환이 N번이 되고.

이름

아무 값이나 적절한 위치에 '삽입'해서 삽입정렬인가 보다.

방법

내 나름 설명: 2번째 원소부터 고른다. 그러고 첫번째 원소까지 탐색해서 정렬상 맞는 위치로 옮겨준다. 그러고 이전에 골랐던 원소가  아닌 다음 원소로 가서 반복한다.

특징

1. 간단하고 느리다. 안정성이 있다. 메모리 사용은 O(1)이다. 

2. 소요시간은 아마도 O(N²), Ω(N). 선택 정렬보다 교환을 많이 한다.

대신, 이미 정렬된 자료에 대해서는 최소한의 검산만한다. 그러므로 어느정도 정렬된 배열의 경우 효과가 좋다.

반대로, 역순의 경우 최악의 경우가 된다. N(N-1)/2번 비교·교환을 하게 된다. 이러면 오히려 선택정렬이 낫다.

3. 그래서 난수 배열의 경우 선택 정렬보다는 더 좋다. (경우에 따라선 더 느릴 수도 있지만 대체로.)

삽입정렬은 입력자료에 굉장히 민감하다. 반대로 말하면 선택정렬은 둔감하다.

4. 교환을 많이 하기 때문에, 내부정렬과 간접정렬에 필요하다. 그게 아니면 그걸로 바꿀 필요가 있다.

최적화

1. 보초sentinel를 사용하기. 자료의 첫번째 항목에 -1같이 보장되는 최소값을 넣어주면 내부 루프 조건에서 j > 0을 뺄 수 있다.

2. 이진검색 도입. 어느 기준점 이전의 자료들은 이미 정렬된 상태이기 때문에 검색을 사용해 더 빨리 끼울 곳을 찾을 수 있다.

4. 거품 정렬

Bubble sort

일반적으로 worst의 정렬이다. 

이름

교환을 하는 모습이 뽀글거리는 거품이 이동하는 것 같다고 해서 거품정렬이라는 것 같다. 바로 다음 원소와 스왑하니까.

방법

현재 원소와 다음 원소를 정렬한다. 그러고 현재 원소를 다음 원소로  잡고 계속 반복한다. 끝까지 하면 맨 마지막 원소는 최대값이다. 그거 빼고 처음부터 반복한다.

특징

1. 간단하고 일반적으로 가장 안 좋다. 안정성이 있다. 메모리 사용은 O(1)이다.

2. 소요시간은 O(N²). 하지만 교환하는 연산이 스왑 그대로라서 한 2.5상수배는 해 주는 것 같다. 최적화를 넣으면 Ω(N)이 되기는 한다.

3. 진보형태로 쉐이커정렬이 있다. 양쪽으로 오가면서 정렬을 한 댄다.

4. 단순 연결 리스트에서 적용 가능하다...

최적화

flag넣기. 대충 정렬을 하기 때문에 막판에 와서 이미 정렬이 다 되어 있을 수 있다. 그때 flag를 쓰면 더 이상의 연산을 막을 수 있다.

4. 쉘 정렬

Shell sort

삽입정렬이 입력자료에 민감하다는 단점을 극복한 정렬이다. 기본적으로 삽입정렬을 쓴다. (꼭 안 쓰고 딴 거 써도 쉘 정렬로 치는 듯 하다.)

이름

알고리즘의 창시자 도널드 셸의 이름을 따서 정해졌다. (위키참조)

근데 쉘이라고 부르는게 습관이 됐는데 이거 어쩌나. 상관 없겠지 뭐.

방법

원소를 띄엄띄엄 간격을 두고 골라 부분집합 여러개로 나눈다. (이건 너무 요약적이므로 누군가 이걸 이해하려고 읽는 사람들은 다른 글을 참조 바람) 그걸 정렬하고, 간격을 줄여 반복한다. 결국 마지막은 간격0, 일반정렬로 끝난다.

특징

1. 메모리 사용이 O(1)면서 빠르다. 하지만 안정성이 없다.

2. 시간복잡도는 계산하기 까다롭다. 이유는 간격을 어떻게 두느냐에 따라 시간이 달라지기 때문.

일반적으로 의 값을 가진다고 한다. 최악의 경우 자체도 역순이 아니라 랜덤한 자료에 있다.

최적화

위에서 나오다시피 간격에 따라 쉘 정렬의 성능이 달라진다. 교재에서 낫다고 알려진게 수열이라는데, 왜인지 알고싶었지만.. 논문이라니.

그 논문엔 쉘 정렬이 3중루프로 일반화되어 있었다.

결국 그림그리는 표현 프로그램을 만들었다. 허접하지만 시간이 들어간... 그건 다음에 올릴 거다 ㅇㅅㅇ