Quick Sort

인턴을 끝낸 이후로 이력서다 뭐다하며 지내면서 기본적인 감각도 잊은 거 같습니다. 앞으로 면접대비도 할겸(이게 제일 크지만)

이번 포스팅은 Quick Sort 입니다. 평균적인 정렬을 요구하는 상황에서 가장 무난한 성능을 보여준다는 퀵 정렬이죠.

퀵 정렬은 불안정 정렬에 속합니다. 불안정 정렬이...? 뭐죠?

위키백과에서 찾아보겠습니다.

음...자세한 설명은 따로 없지만

불안정 정렬에는 선택/셀/힙/퀵 정렬  -> 중복되는 값이 있을 때 상대적인 위치 변경 없음

안정 정렬은 버블/삽입/합병 정렬이 있습니다. -> 중복되는 값이 있을 때 상대적인 위치 변경이 있을 수 있음

이렇게 설명할 수 있겠습니다.

예를 들어서 77, 77, 22 라는 값이 있을 때 앞의 값을 77-1 뒤의 값을 77-2 라고 하면

안정 정렬은 정렬이 완료 되면 22, 77-1, 77-2 겠지만 불안정 정렬은 22, 77-2, 77-1 이럴수도 있다는 이야기입니다.

음! 그렇구나! 자 그러면 Quick Sort의 본격적인 내용으로 넘어가보겠습니다.

퀵 소트는 pivot을 기준으로 두 구역으로 나누어서 왼쪽은 pivot보다 작은 값 오른쪽은 큰 값을 이동시킵니다.

그리고 재귀적으로 스스로를 부르는데 이때 아까 나누었던 두 구역을 다시 pivot을 정하게 해서 왼쪽 작은값 오른쪽 큰값을 넣습니다. 이것을 반복하면 정렬이 이루어지는 것이죠.

최악의 경우는 이미 정렬된 경우에는 시간이 가장 오래걸리지만 보통의 경우 자료가 입력이 되었는데 이미 정렬된 경우를 기대하긴 힘들 것이라 예상되므로 가장 평균적으로 빠른 성능을 보여줍니다.

저의 코드에서는 pivot하고 비교하고 자리를 바꾸기 위해서 i와 j를 사용했습니다.

그림처럼 i와 j를 이용해서 pivot값보다 작으면 서로의 자리를 바꾸고 크다면 j를 옆으로 한칸 이동합니다.

즉 j는 pivot과 비교하기 위한 index이고 i는 pivot보다 작은 값들을 왼쪽에 위치하도록 pivot이 있을 위치를 잡아주는 index의 역할입니다.

파란색칸이 pivot보다 작은 값인데 i의 위치가 pivot보다 작은 값이 확보됨에 따라서 이동하는 것을 알 수 있습니다.

설명이 매끄럽진 않지만 이해가 안 가시는 분들은 그림을 보고 한 단계씩 학습해보시길 바랍니다.

ubuntu 15.04 에서 c로 코딩하여 컴파일했습니다.

2015.11.06 17:47 추가

최근제가 git을 개설하여 사용하기 시작하면서 코드들은 거기에 올려보고자합니다. git에 익숙해지는 연습을 해보고 싶네요.

이때는 웹페이지로 업로드해서 몰랐는데 쉘로 요즘 연습하고 있습니다. 파일이 필요하신분은 따로 드릴게요