코딩테스트 문법 정리 - 정렬

1. 버블 정렬

• 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식

1) 버블 정렬의 핵심 이론

• 인접한 데이터 크기를 비교해 정렬 하는 방법
• 시간 복잡도는 O(n^2) 다른 정렬 알고리즘보다 속도가 느린 편
• 인접한 데이터 간의 swap 연산으로 정렬한다

2) 정렬 법 그림

• 만약 특정한 루프의 전체영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는데이터가 모두 정렬되었다는 뜻이므로 프로세스를 종료해도 된다.

2. 선택 정렬

1) 선택 정렬 핵심 이론

• 최대나 최소 데이트를 선택하는 방법

• 구현 방법이 복잡하고 시간 복잡도가 O(n^2)라 효율적이지 않아 많이 사용하지않음.

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

• 왜 N^2이냐? :
  처음 n n-1 n-2 n-3 .... n-n까지 반복이 되기 때문에 n^2이 된다.

3. 삽입 정렬

1) 삽입 정렬 핵심 이론

• 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식
• 시간 복잡도는 O(n^2)로 느린편이지만 구현이 쉽다.

2) 정렬법 그림

• 조금 더 빠르게 하는 방법 : 이진 탐색
  인덱스의 크기가 커졌을때 정렬된 데이터의 가운데 와 비교한 다음 탐색을 하면 O(logN)으로 줄어든다.

4. 병합 정렬 (중요함)

1) 병합 정렬 핵심 이론

• 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘.
• 시간 복잡도는 O(nlogn)
• 왜 시간 복잡도가 nlogn이냐 : 아래 그림 처음 8개의 원소에서 총 3번만에 데이터 정렬이 된다. 3은 log8이다 => 8log2^3이기 때문에 그렇다.
  

2) 병합 정렬 수행 방식

• 최초에는 8개의 그룹으로 나눈다.

• 2개씩 그룹을 합치며 오름차순 정렬한다.

• 위에 방식을 반복한다.

• 3번만에 정렬된다.

• 병합 정렬은 코딩테스트의 정렬 관련 문제에서 자주 등장한다. 특히 2개의 그룹을 병합하는 원리를 꼭 숙지해야 한다. (투포인트)

3) 2개의 그룹을 병합하는 과정

• 뽑힌 인덱스의 오른쪽으로 한칸씩 이동하며 값을 집어넣는다. 이것이 원리.

• 만약 한쪽의 인덱스가 다 뽑혔다면 남은 인덱스 전부 그대로 붙여넣으면 된다. (이미 정렬된 상태이기 때문)

• 투포인트