5.1 정렬 알고리즘

1. 버블 정렬

: 양옆에 위치한 두 값을 비교하면서 크기 순으로 정렬 -> 배열의 뒤에서부터 정렬됨

배열의 n번째 요소를 정렬하기 위해 n(n-1)/2만큼 연산을 수행하며, O(n^2)의 시간 복잡도 소요됨. 정렬 수행이 비교적 느리지만 별도의 메모리 공간이 필요하지 않음

 

2. 선택 정렬

: 배열을 순회하면서 배열의 앞에서부터 차례대로 각 인덱스에 들어갈 값을 선택해 위치시킴

배열의 n번째 요소를 정렬하기 위해 n(n-1)/2만큼 연산을 수행하며, O(n^2)의 시간 복잡도 소요됨. 정렬 수행이 비교적 느리지만 별도의 메모리 공간이 필요하지 않음. 하지만 구현이 비교적 간단함.

 

3. 삽입 정렬

: 배열을 앞에서부터 순회하면서 정렬된 부분의 적절한 위치에 값을 삽입하는 방식

배열의 n번째 요소를 정렬하기 위해 n(n-1)/2만큼 연산을 수행하며, O(n^2)의 시간 복잡도 소요됨. 

 

4. 합병 정렬

: 정렬하는 배열을 크기가 0 또는 1이 될 때까지 절반씩 분할하고, 분할된 각각의 배열은 다시 하나의 배열로 합치면서 정렬을 수행

합병 정렬의 시간 복잡도는 O(n log n)으로 수행 시간 면에서 효율적임

 

5. 퀵 정렬

: pivot 이라는 특정 값을 선택해 피봇보다 작은 값으로 구성된 배열과 피봇보다 큰 값으로 구성된 배열로 분열해 정렬하는 방식 -> 분할 배열의 크기가 1 이하가 될 때까지 반복해서 수행함

 

평균적인 시간 복잡도는 O(n log n)임 -> 이를 위해서 배열을 균등하게 분할할 수 있어야 함. 피봇 선택이 중요!

 

6. 힙 정렬

: 배열을 힙으로 만드는 과정을 통해 최대 힙이나 최소 힙 자료구조를 이용해 정렬을 수행 -> 시간 복잡도는 O(n log n)

 

7. 기수 정렬

: bucket이라는 큐를 생성해 낮은 자릿수부터 정렬을 수행

데이터 개수를 n, 최대 자릿수를 d라고 할 때 시간 복잡도는 O(dn)임

 

8. 계수 정렬

: 데이터의 개수를 세서 정렬하는 방식

데이터의 개수를 n, 데이터의 최댓값을 k라고 할 때 시간 복잡도는 O(n+k)임