버블 정렬(Bubble Sort)
- 인접한 두 데이터를 비교하여 정렬 (오름차순 기준 - 앞의 데이터가 뒤에 데이터보다 크다면 교환)
- 정렬 한 턴을 수행할때 마다 해당 턴의 맨 마지막 위치에 정렬이 완료된 데이터가 배치됨
- 각 턴의 마지막은 턴을 수행할 때마다 한 칸씩 앞으로 온다
- 한 턴에 Swap이 일어나지 않을 경우 더 이상 정렬할 것이 없는 것이므로 정렬을 중단
선택 정렬(Selection Sort)
- 한 턴에서 데이터들 중 가장 작은 값을 찾고 각 턴에서 선택된 최소값을 턴의 맨 앞에 데이터와 교체
- 각 턴의 맨 앞에 데이터는 이미 정렬이 완료된 상태이므로 다음 데이터부터 마지막 데이터까지의 동일한 작업을 수행
삽입 정렬(Insertion Sort)
- 두 번째 인덱스부터 시작하여 해당 인덱스 값을 앞에 있는 데이터와 비교 (왼쪽에 이웃한 요소가 선택한 요소보다 크면 그 값을 대입하고 앞으로 이동하면서 이작업을 반복)
- 선택한 값 이하의 요소를 만나면 앞쪽은 검사를 멈추고 해당 위치에 값을 대입
기본 정렬(버블, 선택, 삽입)의 시간 복잡도는 모두 O(n^2)이다. (효율이 좋지 않다)
Reference
- https://en.wikipedia.org/wiki/Bubble_sort
- https://en.wikipedia.org/wiki/Selection_sort
- https://en.wikipedia.org/wiki/Insertion_sort
