[Algorithm] 정렬

버블 정렬

배열의 값을 다음 인덱의 값과 하나씩 비교하며 배열 끝까지 순회한다.

이 과정을 모든 인덱스에 대해 진행하므로 n*n 즉, 시간 복잡도가 O(n^2)으로 최악의 정렬 알고리즘이다.

 

선택 정렬

배열의 가장 작은 요소부터 찾아서 앞에서부터 순서대로 정렬한다.  O(n^2)

 

삽입 정렬

배열을 순차적으로 돌면서 현재 인덱스를 앞에 위치하는 인덱스들 중에서 비교하여 현재 인덱스가 들어가야할 위치에 삽입힌다. O(n^2)

버블 정렬 보다 빠르며, 배열의 크기가 작을 경우에는 효율적이다.

 

셸 정렬

길이가 n인 배열이 있을 때 간격을 n/2로 주어 i번 인덱스부터 n-1번 인덱스까지 간격에 해당하는 인덱스들 중에서 값을 비교해서 더 작은 값이 앞으로 이동한다. 이후 간격을 n/4로 더 좁혀 더 넓은 범위에 대해 정렬하고 이 과정을 간격이 1이 될 때까지 반복한다.

O(n log n)

 

퀵 정렬

피벗을 임의로 정해 피벗보다 작은 값을 앞으로 피벗보다 큰값이 뒤로오게 한 다음 피벗을 기준으로 왼쪽과 오른쪽에서 새로 피벗을 만들어 앞선 과정을 나누어질 수  없을 때까지 반복한다.

다른 O(n log n) 시간을 가지는 정렬 보다 빨라 많이 사용되지만, 이미 정렬된 리스트에 대해서는 오히려 더 많은 시간이 걸린다.

 

병합 정렬

배열을 1개가 될 때까지 균등하게 나눈 다음 각각에 대해 비교 후 합치는 과정을 통해 정렬한다.

전체를 하나로 쪼개고, 하나를 전체로 합친다. O(n log n)

 

정렬 속도 비교