정렬 알고리즘 시간 복잡도

 

 

버블정렬

 

위 그림처럼 하나씩 인덱스를 옮기면서 정렬 라운드를 진행하고 정렬이 완료될 때 까지 라운드를 계속 반복한다.

 

시간 복잡도 N^2

 

 

 

 

---

선택 정렬

위 그림처럼 가장 우선순위가 높은 요소를 하나씩 선택하여 가져와서 정렬이 완료된 영역을 하나씩 넓힌다.

 

시간 복잡도 N^2

 

 

 

---

삽입 정렬

 

 

일단 값을 순서대로 가져와서 위치를 찾아서 삽입한다. 선택 정렬과 비슷하다.

 

시간 복잡도: N^2

 

 

 

---

힙 정렬

 

 

힙 정렬은 이진 트리 형태로 최대힙 또는 최소힙을 만들어서 값을 정렬하는 방법이다.

 

정렬을 하는데 log n 의 시간이 걸리고 총 n개를 삽입하므로

-> 시간 복잡도: N log N

 

 

 

 

---

병합 정렬

 

 

위 그림처럼 모두 분해해서 병합을 하면서 정렬을 하는 방법이다.

 

병합은 log N 번 진행하고 정렬은 각 병합 단계마다 N번 진행하므로

-> 시간 복잡도: N log N

 

 

 

 

 

---

퀵 정렬

 

 

위 그림처럼 피벗 값 하나를 선택하여 피벗 값을 기준으로 작은 값과 큰 값으로 나누는 과정을 반복한다. 만약 피벗 값이 각 배열의 중간 값이라고 가정하면 

 

시간 복잡도: N log N

 

사실 모든 피벗 값이 최소 값이나 최대 값이 되는 경우 N^2의 시간 복잡도가 나오겠지만 임의의 3개의 값을 선택해서 중간 값을 피벗으로 사용하는 방식을 사용하면 최악의 경우를 피할 수 있고 평균 시간 복잡도가 N log N 이다. 그리고 시간 복잡도가 N log N 인 알고리즘 중에서 가장 빠른 알고리즘이라고 한다.