기본 정렬 (Sort)

1. 버블 정렬(Bubble sort)

버블 정렬이란?

두 인접한 데이터의 크기를 비교해 정렬하는 방법이다.

시간 복잡도는 O(n^2)로 다른 정렬에 비해 느린 편이다.

버블 정렬 과정

1. 비교 연산이 필요한 루프 범위 설정
2. 인접한 데이터 값을 비교
3. swap 조건에 부합하면 swap 연산 수행
4. 루프 범위가 끝날 때까지 2.~3. 반복

특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다는 것은 그 영역 뒤에 있는 데이터가 모두 정렬되었다는 뜻이다.

2. 선택 정렬(Selection sort)

선택 정렬이란?

최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 방법이다.

시간복잡도는 O(n^2)으로 효율적이지 않다.

선택 정렬 과정

1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾음
2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap
3. 가장 앞에 있는 데이터의 인덱스 값을 변경해 남은 정렬 부분의 범위 축소
4. 전체 데이터 크기만큼 index가 커질 때까지 반복

3. 삽입 정렬(Insertion sort)

삽입 정렬이란?

선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 방법이다.

시간복잡도는 O(n^2)으로 효율적이지 않지만 구현하기가 쉽다.

삽입 정렬 과정

1. 현재 index에 있는 데이터 값 선택
2. 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치 탐색
3. 삽입 위치부터 index에 있는 위치까지 shift
4. 삽입 위치에 현재 선택한 데이터를 삽입하고 index++
5. 전체 데이터의 크기만큼 index가 커질 때까지 반복

적절한 위치를 탐색하는 과정(2번 과정)에서 이진 탐색(Binary search)을 이용하면 시간복잡도를 O(NlogN)로 줄일 수 있다.