Do it 알고리즘 코딩테스트 하루코딩 4장 정렬 이론

# 10 버블정렬
인접한 데이터끼리 크기 비교하여 swap
시간 복잡도 O(n^2) // 1번 루프당 1개 픽스

0과 1 비교하여 스왑, 1과 2를 비교하여 스왑, ... 맨뒤가 정렬된 영역
정렬된 영역을 제외하고 0과 1 비교하여 스왑, 1과 2를 비교하여 스왑, ...

만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면, 모두 정렬되어 있다는 뜻이므로 더 이상 정렬 수행하지 않아도 된다.

# 11 선택 정렬
정렬 해야 되는 범위에서 최솟값 또는 최댓값을 찾고, 남은 정렬 해야 되는 부분의 가장 앞에 있는 데이터와 swap
시간 복잡도 O(n^2) // 1번 루프당 1개 픽스

# 12 삽입 정렬
이미 정렬된 데이터의 범위에 정렬되지 않은 하나의 데이터를 적절한 위치에 삽입시켜 정렬 // 오름차순인 경우 자신보다 작은 값을 찾아 바로 뒤에 삽입
시간복잡도 O(n^2)

정렬된 영역에서는 이진 탐색을 사용할 수 있으므로 O(n)에서 O(logN)으로 줄일 수 있다. 그러나, 데이터를 옮기는 과정이 필요하므로 시간이 오래걸려 삽입 정렬을 자주 사용하지는 않는다.

# 13 병합 정렬
병합 정렬(merge sort)는 분할 정복 방식을 사용해, 데이터를 분할하고 분할한 집합을 각각 정렬하여 합치는 알고리즘
시간복잡도 O(nlogn)

 

전체가 정렬 되어 있진 않지만, 각 집합은 정렬 되어 있다.

 

한 쪽의 집합에서 모든 요소가 저장되면 나머지는 그대로 저장

 

2개의 그룹을 병합하는 과정
투 포인터 개념을 사용
왼쪽 포인터가 가리키는 값과 오른쪽 포인터가 가리키는 값을 비교하여 작은 값을 배열에 저장 (오름차순 경우)
포인터로는 오른쪽으로 한 칸 이동

14:00 // 앞에 데이터가 몇개 남아 있는지
1. swap이 n번 일어났다.
2. 자동차 경주에서 n번 역전이 일어났다.