Sorting

CS 지식을 공부하다보면 Sorting(정렬)과 관련된 주제는 정말 수도 없이 많이 다룬다.

그도 그럴 것이 정렬은 참 쓸 데가 많다. 당장 출석부 같은 것만 보아도 이름 순으로 정렬을 한 게 스테레오 타입이지 않는가.

아무튼 Sorting이 뭐냐고 묻는다면 다들 정렬 이라고 하겠지만, 조금 더 엄밀한 정의를 내려보자.

랜덤한 순서의 배열을 재배치하여 오름차순(내림차순)으로 만드는 것

이라고 할 수 있겠다.

일반적으로는 오름차순으로 나타내는 것이 맞다.

Insertion Sort

대충 알겠으니 바로 하나의 알고리즘으로 넘어가자.

Insertion Sort는 참 쉬운 알고리즘 중 하나이다.

원카드를 한다고 생각하고 앞에서부터 카드 정리를 한다고 생각하자.

그럼 아마 그 카드를 뽑고 적절한 위치에 넣는 방법을 선택하지 않을까 싶다.

물론 아닐 수도 있는데 그건 내 알빠는 아니다.

Logic

간단하게 로직 설명 한 번 해보자.

1. 두번째 카드부터 시작
2. 그 카드를 기준으로 앞에 있는 카드들과 하나씩 비교
3. 더 큰 카드가 있으면 뒤로 밀기
4. 더 작은 카드를 만나면 바로 뒤에 넣기
5. 마지막 카드까지 무한 반복

대충 느낌오죠?

Pseudo Code

슈도 코드는 쓰기 귀찮으니까 사진으로 대체 한다.

그냥 위에서 설명한거랑 똑같다.

Prove

알고리즘은 사실 그냥 짰다고 다가 아니긴하다.

이렇게 끝날 거 같으면 나도 윤강훈-Sort 하나 만들어서 내지 그냥

썩을 놈의 증명 한 번 해줘야한다.

대충 보면 잘 동작하는 거 아니냐고?

맞긴 한데 아닐 수도 있잖아.

백준 풀다가 98%에서 틀렸습니다! 나오면 진짜 화가 머리 끝까지 나는 상황을 한 번 경험해봤으면 증명이 얼마나 중요한 지 알 수 있을거다.

자 암튼 재귀를 활용한 증명과 반복을 활용한 증명이 있는데 이 친구는 반복을 한 번 활용해보자.

이유가 뭐냐고? 묻지도 마 그냥!! 진짜 프로 출신들은 슈도 코드만 봐도 뭘 써야하는 지 다 안다고

뻘소리는 그만하고 증명 한 번 하자.

일단 반복문으로 구성된 알고리즘의 경우 반복문이 진행되면서 변하지 않는 것을 찾는 것이 중요하다.

우리는 이걸 Loop Invariants (루프 불변성) 라고 부를 것이다.

위에서 말했던 Logic에서 힌트를 찾을 수 있다.

카드를 하나 뽑고 "앞에 있는 카드들과 비교"

이 말에서 프로 출신들은 바로 깨달았을 것이다.

내가 뽑은 것 앞에 있는 놈들은 다 정렬되어 있다.

절대 등수대로 서렌치면 안된다는 것이다.

지금 8등에서 반등 타이밍 잘 잡았는데 차례대로 죽여야지 1등부터 칠려고 하면 안된다.

점수판 제대로 등반해야겠지?

암튼 이걸 좀 더 정적으로 설명하자면

$j$번째 iteration에서 $A[1:j-1]$이 정렬되어 있다는 사실은 불변이다.

이걸 증명하기 위해서도 3가지 단계가 필요하다.

1. 초기 조건
   $j=2$ 일 때, $A[1:j-1]$은 $A[1]$ 이므로 반드시 정렬되어 있다.

2. 유지 조건
   선택된 원소가 1칸씩 앞으로 가서 자리를 찾고 나면 $A[1:j]$ 또한 정렬되어 있다.

3. 종료 조건
   $n$번째 iteration이 마지막 iteration이며, 이게 끝나고 나서 $A[1:n]$도 정렬되어 있다.

이렇게 3가지 단계를 모두 만족하는 것을 증명했다면 이 알고리즘은 정상 작동하는 것으로 잘 증명되었다.

Time Complexity

쓰기에는 너무 많으니 사진 한 장으로 대체한다.

최선의 경우 $O(n)$ 일 것이며,

최악의 경우 $O(n^2)$ 시간이 걸릴 것이다.

그럼 평균적인 경우는 어떨까?

러프하게 j/2 번 반복한다고 했을 때, 이 또한 $O(n^2)$ 시간이 걸릴 것이다.

앞의 글에서 말했듯이 최선일 때를 고려할 필요는 없다.