[ Algorithm ] 정렬 알고리즘

면접시, 최소한 코드수준까지 구현할 알고리즘 한개, 과정을 완벽하게 설명할 수 있는 알고리즘 한개는 숙지하고 있어야 한다.¹

정렬 알고리즘#

정렬 알고리즘이란, 목록 안에 저장된 요소들을 특정한 순서대로 재배치하는 알고리즘이다. 그렇다면 우리가 왜 정렬을 해야 하는 것일까? 정렬을 하게 되면, 이후에 다른 알고리즘을 효율적으로 사용할 수 있게 된다. 또한 읽기 편해지기도 하고 다른 다양한 이점이 있다.

정렬 알고리즘에서 입력 데이터는 일반적으로 배열과 같은 데이터 구조에 저장한다. 그리고 아무 위치로의 임의 접근을 허용한다. 만약 연결 리스트를 사용한다면, 처음 혹은 끝부터 차례대로 훑어야 하긴 하다.

보통 사용하는 순서는 숫자, 사전 순서가 있고, 오름차순 혹은 내림차순으로 정렬한다. 정렬하는 방법이 다양하기 때문에 다양한 정렬 알고리즘이 있는데 보통 다음과 같은 차이가 있다.

시간 복잡도 차이
메모리 사용량 차이
안정성(stabilty) 차이
직렬 vs 병렬 차이

정렬 알고리즘의 안정성#

정렬 알고리즘의 안정성은 안전성(safety)과 착각하면 안된다. 안정성은 똑같은 키(key)를 가진 데이터들의 순서가 바뀌냐 바뀌지 않느냐의 여부를 나타낸다.

안정성을 잘 모르는 이유#

보통 정렬 알고리즘의 안정성을 모르는 경우가 많은데, 같은 키를 가진 데이터의 순서가 바뀌어도 문제가 아닌 경우가 많아서 그렇다. 그래서 잘 모르고, 생각도 하지 않는다. 그래서 안정성때문에 버그가 나면 고치지 못하는 경우가 있다.

알고리즘마다 안정성이 있는 알고리즘이 있고 없는 알고리즘도 있다. 이제 어떤 상황에서 문제가 생길 수 있는지 알아보자.

안정성이 문제가 되는 경우#

정렬의 기준이 되는 정렬 키(sort key)와 실제 데이터가 다름

구조체 / 클래스의 일부 멤버만 정렬 키로 사용

대표적인 정렬 알고리즘#

대표적인 정렬 알고리즘을 보자. 사용 빈도와 숙지 정도에 따라 나누었다.

언제라도 구현할 수 있어야 함#

버블 정렬
선택 정렬

언제라도 설명할 수 있어야 함#

퀵 정렬

이해하는 정도면 충분#

병합 정렬
힙 정렬

정렬 알고리즘 비교#

정렬 알고리즘	평균 시간 복잡도	최악 시간 복잡도	메모리 사용량	안정성
버블 정렬	$O(N^2)$	$O(N^2)$	$O(1)$	안정
선택 정렬	$O(N^2)$	$O(N^2)$	$O(1)$	불안정
삽입 정렬	$O(N^2)$	$O(N^2)$	$O(1)$	안정
퀵 정렬	$O(N log N)$	$O(N^2)$	$O(log N)$	불안정
병합 정렬	$O(N log N)$	$O(N log N)$	$O(N)$	안정
힙 정렬	$O(N log N)$	$O(N log N)$	$O(1)$	불안정
참고

평균 시간 복잡도는 평균적으로 소요되는 시간을 나타냄
최악 시간 복잡도는 입력이 최악의 경우에 소요되는 시간을 나타냄
메모리 사용량은 정렬 알고리즘이 필요로 하는 메모리 양을 나타냄
안정성은 동일한 값에 대해 순서가 바뀌지 않음을 의미함

시간복잡도와 실제 성능은 다를 수 있다.#

메모리 할당 / 해제 하는데 많은 시간이 소요된다.
시간복잡도와 실행시간은 다르다.(원래 앞에 들어가는 상수가 제거됨, 따라서 앞에 상수를 무시하지 않게 되면 성능 차이가 발생한다)

상황에 따른 정렬 알고리즘 선택#

기본 - 퀵 정렬#

퀵 정렬 사용
C도 qsort()함수를 기본 제공

간단히 구현할 때 - 버블 정렬#

버블 정렬 사용
구현이 매우 쉬움

어떤 경우에도 느려지면 안될 때 - 병합 또는 힙 정렬#

병합 또는 힙 정렬
평균은 퀵 정렬보다 느림
최악의 경우 여전히 $O(N log N)$

특수한 상황에 적합한 정렬 알고리즘#

예: 기수(radix) 정렬

이 포스트는 udemy의 자료구조 알고리즘(포프)의 강의를 기반으로 작성되었습니다. ↩