정렬의 목적 : 빠른 탐색(Search)을 위해!
1 9 3 4 8 5 … 에서 n을 찾으려면 최악의 경우 데이터의 길이만큼 탐색을 해야 하지만
1 3 4 5 8 9 … 에서 n을 찾으려면 log(데이터의 길이)만큼만 탐색을 진행하면 된다!(이진 탐색)
결국 우리는 이진 탐색을 위해 정렬을 하는 것인데..
안정 정렬, 불안정 정렬
DATA가 시간에 따라 순차적으로 입력을 받았다고 하자.
지역별로 정렬하고 싶어서 정렬 알고리즘을 돌렸는데 굳이 기존의 순서를 뒤죽박죽으로 할 이유는 없다!
정렬의 종류:
O(n²) : 버블 정렬, 선택 정렬, 삽입 정렬
O(n log n) : 병합 정렬, 힙 정렬, 퀵 정렬, 트리 정렬
1번과 2번을 비교한다 → 2번과 3번을 비교한다 →… → n-1번과 n번을 비교한다.
2번과 3번을 비교한다 → … → n-1번과 n번을 비교한다.
…
n-1번과 n번을 비교한다.