-
- 선택 정렬 ( Selection Sort )
- 순차적으로 가장 작은 수를 선택하고 이를 반복 교환하는 정렬
- 시간복잡도 : O(n^2)
- 삽입 정렬 ( Insertion Sort )
- 자기 보다 작은 수가 나올 때 까지 오른쪽으로 밀어 삽입하는 정렬
- 시간복잡도 : O(n^2)
- 버블 정렬 ( Bubble Sort )
- 좌측 값이 자기 보다 크면 교환하는 정렬
- 시간복잡도 : O(n^2)
- 쉘 정렬 ( Shell Sort )
- 작은 수가 나올 때 까지 간격 만큼 우로 밀어 삽입하는 정렬
- 시간복잡도 : 최악의 경우 O(n^2)
- 간격 : Hn = 3*H(n-1) + 1 // n = 데이터 수
- 반복
- 간격 H를 구한다.
- 간격 H에 위치한 요소끼리 정렬을 실시한다.
- 간격 H를 절반으로 줄인다. [ 간격 H가 홀수일 경우 +1 ]
- 반복
- 퀵 정렬 ( Quick Sort )
- 좌측, 우측 값을 축 값과 비교하고 서로 교환 후 재귀적으로 분할하는 정렬
- 시간복잡도 : O(NlogN)
- 동작
- 리스트 안에 있는 한 요소를 선택하고 이를 피벗이라고 한다.
- 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 큰 요소는 오른쪽으로 옮겨진다.
- 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트 다시 정렬
- 병합 정렬 ( Merge Sort )
- 최소 단위 까지 배열을 재귀적으로 분할 후, 병합 시 앞에서 부터 비교 삽입하는 정렬
- 시간복잡도 : O(NlogN)
- 힙 정렬 ( Heap Sort )
- 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조
- 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법
- 동작
- 정렬해야 할 n개의 요소들로 최대 힙을 만든다. // 내림차순 기준으로 정렬하고자 할 경우
- 요소를 하나씩 꺼내서 배열의 뒤부터 저장한다.
- 삭제되는 요소들은 값이 감소되는 순서로 정렬되게 된다.
- 시간복잡도 : O(NlogN)