3. 알고리즘

[버블소트, 힙소트, 머지소트, 퀵소트, 삽입소트]

• 버블소트는 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘이다. 0번 인덱스부터 n-1번 인덱스까지 n번까지의 모든 인덱스를 비교하며 정렬한다. 시간복잡도는 O(n^2)이다.

• 힙소트는 주어진 데이터를 힙 자료구조로 만들어 최대값 또는 최소값부터 하나씩 꺼내어 정렬하는 알고리즘이다. 힙소트가 가장 유용한 경우는 전체를 정렬하는 것이 아니라 가장 큰 값 몇개만을 필요로 하는 경우이다. 시간복잡도는 O(nlog2n)이다.

• 머지소트는 주어진 배열을 크기가 1인 배열로 분할하고 합병하면서 정렬을 진행하는 분할/정복 알고리즘이다. 시간복잡도는 O(nlog2n)이다.

• 퀵소트는 매우 빠른 정렬 속도를 자랑하는 분할 정복 알고리즘 중 하나로 합병정렬과 달리 리스트를 비균등하게 분할한다. 피봇을 설정하고 피봇보다 큰 값과 작은 값으로 분할하여 정렬을 한다. 시간복잡도는 O(nlog2n)이며 리스트가 계속해서 불균등하게 나눠지는 경우 시간복잡도가 O(n^2)까지 나빠질 수 있다.

• 삽입정렬은 두 번째 값부터 시작하여 그 앞에 존재하는 원소들과 비교하여 삽입할 위치를 찾아 삽입하는 정렬 알고리즘이다. 삽입 정렬의 평균 시간복잡도는 O(n^2)이며, 가장 빠른 경우 O(n)까지 높아질 수 있다.

[정렬 알고리즘 시간복잡도 비교]