1. 버블 정렬

(1) 정의

인접한 원소끼리 비교 후에, 정렬되어 있지 않다면, 두 원소의 위치를 swap한다.
이런 식으로 정렬하게 되면 배열 혹은 리스트의 오른쪽부터 값들이 정렬되어 쌓이게 된다.
(오름차순이면, 정렬되지 않은 값 중 최대값이 계속 오른쪽에 쌓임. 내림차순은 반대로 최소값들이 오른쪽에 쌓임)
예시

사진 출처: 블로그

(2) 시간 복잡도:

반복문 한 번당 값 하나가 정렬됨. 이러한 반복문이 N개 필요. 따라서 시간복잡도는

O(n^2)

2. 선택 정렬

(1) 정의

정렬되지 않은 범위에서 최소값(혹은 최대값) 찾기
해당 값을 배열 맨 왼쪽으로 옮기기
정렬될 때까지 위의 과정 반복

사진 출처: 블로그

(2) 시간 복잡도:

'N개 중 최소값 찾아 오른쪽으로 밀어넣기 O(N)'를 N번 반복. 시간복잡도는

O(\( N^{2} \))

3. 삽입 정렬

(1) 정의

정렬되지 않은 범위에서 차례대로 값을 조회
정렬된 범위 내에서 현재 조회 중인 값을 삽입할 적절한 위치를 찾는다.
(오름차순: 조회 중인 값보다 큰 값을 만나면, 그 앞에 삽입, 내림차순: 조회 중인 값보다 작은 값을 만나면 그 앞에 삽입)
삽입할 위치에 현재 값을 삽입한다. (정렬된 영역이 +1 증가한다.)
정렬되지 않은 영역의 값을 가지고 위의 과정을 반복한다.

사진 출처: 블로그

(2) 시간 복잡도:

N개 중 조회할 값 뽑기 O(N), 해당 값을 정렬된 영역에서 위치 잡기 - 평균 N/2번의 대소관계 비교 필요 O(\(\frac{N}{2}\)) 따라서 시간 복잡도는 O(n^2)

4. Quick 정렬

(1) 정의

오름차순을 Quick 정렬을 이용해 구현한다고. 버블 정렬

(1) 정의

인접한 원소끼리 비교 후에, 정렬되어 있지 않다면, 두 원소의 위치를 swap한다.

이런 식으로 정렬하게 되면 배열 혹은 리스트의 오른쪽부터 값들이 정렬되어 쌓이게 된다.

(오름차순이면, 정렬되지 않은 값 중 최대값이 계속 오른쪽에 쌓임. 내림차순은 반대로 최소값들이 오른쪽에 쌓임)

예시

사진 출처: 블로그

(2) 시간 복잡도:

반복문 한 번당 값 하나가 정렬됨. 이러한 반복문이 N개 필요. 따라서 시간복잡도는

O(n^2)

2. 선택 정렬

(1) 정의

정렬되지 않은 범위에서 최소값(혹은 최대값) 찾기

해당 값을 배열 맨 왼쪽으로 옮기기

정렬될 때까지 위의 과정 반복

사진 출처: 블로그

(2) 시간 복잡도:

'N개 중 최소값 찾아 오른쪽으로 밀어넣기 O(N)'를 N번 반복. 시간복잡도는

O(\( N^{2} \))

3. 삽입 정렬

(1) 정의

정렬되지 않은 범위에서 차례대로 값을 조회

정렬된 범위 내에서 현재 조회 중인 값을 삽입할 적절한 위치를 찾는다.

(오름차순: 조회 중인 값보다 큰 값을 만나면, 그 앞에 삽입, 내림차순: 조회 중인 값보다 작은 값을 만나면 그 앞에 삽입)

삽입할 위치에 현재 값을 삽입한다. (정렬된 영역이 +1 증가한다.)

정렬되지 않은 영역의 값을 가지고 위의 과정을 반복한다.

사진 출처: 블로그

(2) 시간 복잡도:

N개 중 조회할 값 뽑기 O(N), 해당 값을 정렬된 영역에서 위치 잡기 - 평균 N/2번의 대소관계 비교 필요 O(\(\frac{N}{2}\)) 따라서 시간 복잡도는 O(n^2)

4. Quick 정렬

(1) 정의

오름차순을 Quick 정렬을 이용해 구현한다고 해보자.

기준 값인 pivot 값을 설정해서, 그 값도 큰 데이터들은 오른쪽으로, 그 값보다 작은 데이터들은 왼쪽으로 몬다.
(pivot 제외 맨 왼쪽의 index를 가르키는 포인터를 i, 맨 오른쪽을 가르키는 포인터를 j라고 해보자.)
- i가 가르키는 값이 pivot 값보다 작으면 i++
- j가 가르키는 값이 pivot 값보다 크면 j--
- i가 가르키는 값이 pivot보다 크다면 i는 해당 자리에 멈춰있을 것이다. j도 마찬가지로 j가 가르키는 값이 pivot보다 작으면 멈춰있을 것이다. 둘 다 위의 이유로 멈춰있다면 서로 값을 바꾸고, i++, j-- 한다.
pivot을 2개의 집단 사이의 index에 저장한다.
각 집단별로 재귀를 이용해 또 quick 정렬을 반복한다. (더 이상 쪼개지지 않을 때까지)

(2) 시간 복잡도:

오름차순으로 정렬하려는데 pivot을 매번 최소값으로 잡는다고 해보자. 위의 에시에서는 4,7,11,12 순으로 잡는 것이다. 이러면 퀵정렬 과정 한 번당 한 개밖에 정렬이 되지 않는다.
ex) Loop1 - pivot=4: {} {7,11,12,13,15,16,18,19}, Loop2 - pivot=7: {4} {11,12,13,15,16,18,19}
이러면 평균N/2번의 순회를 N번 반복하는 결과가 된다.

따라서 최악의 시간 복잡도는

O(n^2)

5. 병합 정렬

(1) 정의

병합 정렬은 분할 정복 + 투 포인터의 개념을 이용하여 배열 혹은 리스트를 정렬하는 방법이다. 이론은 다음과 같다.

배열 혹은 리스트를 더 이상 쪼갤 수 없는 단위까지 쪼갠다. (분할)
해당 단위에서 대소관계 비교로 값을 정렬한다.
같은 단계의 단위들끼리 서로의 값 간의 대소관계를 확인 후 병합 및 재정렬한다.
(정복 by 투 포인터 상세 방법: 밑에 기술)
배열 혹은 리스트 전체가 정렬될 때까지 위의 과정을 반복한다.

(2) 구현 방법

배열의 두 부분을 병합할 때를 생각해보자. 이때 포인터가 총 3개 필요하다.

오름차순 정렬을 가정했을 때, s와 m을 비교해서 더 작은 값을 k로 보낸다. 그 후 k++, k에 값을 집어넣은 포인터 ++ 을 한다.
해당 반복은 s나 m이 자신의 범위 맨 끝까지 갈 때까지 반복한다.
이렇게 되면 한쪽 배열의 값은 전부 다 소진했는데, 나머지는 아닐 것이다.
전체 배열의 빈 부분은 해당 나머지들을 바로바로 채워주면 된다. (부분 배열들은 모두 정렬된 상태이기 때문이다.)

(3) 시간 복잡도:

O(nlogn)

6. 기수 정렬

(1) 정의

주어진 입력값의 자릿수를 비교하여 값을 정렬하는 방법.

a. 장점

정렬들 중에서 가장 성능이 빠르다. O(n)

b. 단점

성능이 빠른 만큼, 많은 량의 메모리를 차지한다. Queue가 10개 (음수 값이 있을 때는 10개 더 필요) 혹은 Bucket 배열을 따로 써야한다. 또한 10개의 Queue에 정렬된 수를 넣었다 빼내는 과정에서 추가적인 메모리 소요가 크다.
양의 정수와 음의 정수로 데이터의 종류가 양분화 되었다면, 양의 정수는 양의 정수끼리 따로 모아서 처리, 음의 정수는 음의 정수끼리 따로 모아서 처리해야 한다. (안 그러면 정렬이 안된다.)