정렬 알고리즘
- 버블 정렬(Bubble Sort)
- 선택 정렬(Selection Sort)
- 삽입 정렬(Insertion Sort)
- 퀵 정렬(Quick Sort)
- 합병 정렬(Merge Sort)
버블 정렬
- 쉽지만 좋은 알고리즘은 아니다.
O(n^2)의 시간 복잡도를 가진다.
과정
배열 [5, 2, 6, 3, 1, 4]가 있다고 가정하자.
- 0번, 1번 index의 값을 비교한다. → [5, 2]
- 왼쪽 > 오른쪽 → 5 > 2 이므로 [2, 5, 6, 3, 1, 4]가 된다.
- 1번, 2번 index의 값을 비교한다. → [5, 6]
- 왼쪽 < 오른쪽 → 5 < 6 이므로 교환하지 않는다. → [2, 5, 6, 3, 1, 4]
- 위 과정들을 반복하다보면 결과적으로 [1, 2, 3, 6, 5, 6]의 배열이 완성된다.
선택 정렬
O(n^2)의 시간 복잡도를 가진다.
과정
배열 [5, 2, 6, 3, 1, 4]가 있다고 가정하자.
- 전체 아이템 중 가장 작은 아이템의 위치를 변수에 저장한다. → 1이 가장 작으므로 index 4
- 가장 작은 아이템의 위치와 index 0의 위치를 변경한다. → [1, 2, 6, 3, 5, 4]
- 정렬되지 않은 부분들을 대상으로 위 과정을 반복한다. → 2가 가장 작고, 정렬되지 않은 값 ([2, 6, 3, 5, 4]) 중 index 0도 2로 같다. 교환하지 않는다.
- 위 과정들을 반복한다.
삽입 정렬
- 최고의 시나리오에서
O(n)의 시간 복잡도, 최악의 시나리오에서O(n^2)의 시간 복잡도를 가진다.
과정
배열 [5, 2, 6, 3, 1, 4]가 있다고 가정하자.
- index 1에서 시작한다.
- index 1보다 왼쪽인 값들 중 index 1의 값보다 큰 값이 있다면 교환한다. → 5 > 2 이므로 [2, 5, 6, 3, 1, 4]
- index 2로 이동한다.
- index 2보다 왼쪽인 값들 중 index 2의 값보다 큰 값이 없다면 교환하지 않는다. → 5 < 6이고 2 < 6
- 위 과정을 반복한다.
