n: 자료의 개수, d: 수의 자릿수

상태: 정렬된 수 가 다른 수가 정렬되는 과정에서 위치의 변동이 생기는지 여부

알고리즘

최선

평균

최악

상태

삽입 정렬

O(n)

O(n^2)

O(n^2)

안정

선택 정렬

O(n^2)

O(n^2)

O(n^2)

불안정

버블 정렬

O(n^2)

O(n^2)

O(n^2)

정렬

셸 정렬

O(n)

O(n^1.5)

O(n^2)

불안정

퀵 정렬

O(nlogn)

O(nlogn)

O(n^2)

불안정

히프 정렬

O(nlogn)

O(nlogn)

O(nlogn)

불안정

합병 정렬

O(nlogn)

O(nlogn)

O(nlogn)

불안정

기수 정렬

O(dn)

O(dn)

O(dn)

안정

카운팅 정렬

O(n)

O(n)

O(n)

안정

평균 O(n^2)의 정렬기법 중 삽입정렬이 제일 빠릅니다. 수가 정렬되어있을 시 최대 O(n)을 자랑합니다.

(셸 정렬은 삽입정렬의 변형된 기법으로, 필요한 경우 사용할 수 있도록 연습합니다.)

카운팅 정렬은 한자리 숫자(0~9)들을 정렬하는 등의 특수한 경우에만 사용 할 수 있는 정렬입니다.

 

기수 정렬에서 d는 기수의 자릿수로 자릿수가 작을 때는 O(n)으로 봐도 무방합니다.

자릿수가 고정되어 있는 수들을 정렬 할 때만 사용할 수 있습니다

퀵정렬은 정렬기법 중 제일 빠르지만, 최악의 경우(모든 수가 정렬or역정렬되어있을 때)에는 O(n^2)입니다.

프로그래밍 문제를 풀다가 정렬기법을 써야 할 때 해결해야 할 자료의 범위가 큰 경우(1초당 약 1억번의 연산) 퀵정렬은 최선의 방법이 아닐 수 있습니다.

 

+ Recent posts