1. 버블 정렬
: 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식
- 시간 복잡도 O(n^2)으로 다른 정렬 알고리즘보다 속도가 느린 편이다.
버블 정렬 과정
- 비교 연산이 필요한 루프 범위를 설정한다.
- 인접한 데이터 값을 비교한다.
- swap 조건에 부합하면 swap 연산을 수행한다.
- 루프 범위가 끝날 때까지 2~3을 반복한다.
- 정렬 영역을 설정하며 다음 루프를 실행할 때는 이 영역을 제외한다.
- 비교 대상이 없을 때까지 1~5를 반복한다.
2. 선택 정렬
: 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법이다. 선택정렬은 구현 방법이 복잡하고 시간복잡도도 O(n^2)으로 효율적이지 않아 코딩 테스트에서는 사용하지 않는다.
선택 정렬의 핵심 이론
최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것이 선택정렬의 핵심이다.
3. 삽입 정렬
: 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식이다. 평균 시간 복잡도는 O(n^2)으로 느린 편이지만 구현하기 쉽다.
삽입 정렬의 핵심 이론
선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것이 핵심이다.
삽입 정렬 수행 방식
- 현재 인덱스에 있는 데이터 값을 선택
- 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색
- 삽입 위치부터 인덱스에 있는 위치까지 shift 연산을 수행
- 삽입 위치에 현재 선택한 데이터를 삽입하고 인덱스++ 연산을 수행
- 선택할 데이터가 없을 때까지 반복
4. 퀵 정렬
: 기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다. 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미치고, 평균적인 시간복잡도는 O(nlogn)이다.
퀵 정렬의 핵심 이론
pivot을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것이 핵심이다.
퀵 정렬 과정
- 데이터를 분할하는 pivot을 설정
- pivot을 기준으로 다음 a~e과정을 거쳐 데이터를 2개의 집합으로 분리
- start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동
- end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동
- start가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고, end가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start, end가 가리키는 데이터를 swap하고 start는 오른쪽 end는 왼쪽으로 한칸씩 이동
- start와 end가 만날 때까지 반복
- start와 end가 만나면 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여 pivot이 가리키는 데이터가 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽으로 pivot이 가리키는 데이터를 삽입
- 분리 집합에서 각각 다시 pivot을 선정
- 분리 집합이 1개 이하가 될 때까지 1~3 반복