알고리즘

소트의 종류

버블소트

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

힙소트

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

머지소트

머지소트는 주어진 배열을 크기가 1인 배열로 분할하고 합병하면서 정렬을 진행하는 분할-정복 알고리즘이다. 시간 복잡도는 O(n long n)
처음에 주어진 배열을 하나씩 쪼개서 말 그대로 merge 하면서 크기 순서대로 정렬하는 방식.

퀵소트

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

삽입정렬

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

알고리즘별 시간 복잡도 비교표

참고 : 망나니 개발자