정렬 알고리즘(sorting algorithm)이란?

정렬 알고리즘이란 원소들을 일정한 순서대로 열거하는 알고리즘이다.

 

자세한 설명에 들어가기 앞서, 해당 내용은 Big-O Complexity에 대한 기본적인 이해가 필요하므로 해당 복잡도에 대한 이미지를 첨부한다. 

 

 

 

---

알고리즘의 비교

 

정렬 알고리즘 별 시간복잡도

 

아래에서는 대중적으로 다루는, 시간복잡도가 O(n^2), O(nlogn)인 정렬만 다루려고 한다.

 

---

1. 선택 정렬

현재 위치에 들어갈 값을 찾아 정렬하는 방법이다. 현재 위치에 저장될 값의 크기가 작은지/큰지에 따라 최소 선택 정렬(Min-selection sort)와 최대 선택 정렬(Max-selection sort)로 구분할 수 있다.

 

기본 로직은 아래의 그림과 같다.

 

1. 정렬되지 않은 인덱스의 맨 앞에서부터 배열 전체 중 가장 작은 값을 찾는다.

2. 가장 작은 값을 찾으면 그 값을 현재 인덱스의 값과 바꿔준다.

3. 다음 인덱스에서 1,2의 과정을 반복해준다.

 

배열 안의 원소 개수가 N개라고 할때 배열이 어떻게 되어있든지 간에 전체 비교를 진행하므로 시간 복잡도는 O(n^2)이다,

 

공간 복잡도는 하나의 배열에서만 진행하므로 O(n)

 

선택 정렬

 

2. 삽입 정렬 (Insertion Sort)

 

삽입 정렬은 현재 위치에서 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 정렬 방법이다. 

 

기본 로직은 아래의 그림과 같다.

1. 삽입 정렬은 두번째 인덱스부터 시작하며, 현재 인덱스는 별도의 변수에 저장한다. 비교 인덱스는 현재 인덱스 -1로 잡는다.

2. 별도로 저장해둔 삽입을 위한 변수와 비교 인덱스의 배열 값을 비교한다.

3. 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해주고, 비교 인덱스를 -1하여 비교를 반복한다.

4. 만약 삽입 변수가 더 크면, 비교 인덱스+1에 삽입 변수를 저장한다.

 

삽입 정렬

 

최악의 경우(역으로 정렬된 경우) 시간복잡도는 O(n^2)

배열이 이미 정렬되어 있는 경우 시간복잡도는 O(n)

 

공간 복잡도는 하나의 배열에서만 진행하므로 O(n)

 

3. 버블 정렬 (Bubble Sort)

 

매번 연속된 두개의 인덱스를 비교하여 정한 기준의 값을 뒤로 넘겨 정렬하는 방식이다.

 

기본 로직은 아래의 그림과 같다.

1. 두번째 인덱스부터 삽입정렬을 시작하여 현재 인덱스 값과 바로 이전의 인덱스값을 비교한다.

2. 만약 이전 인덱스가 더 크면 현재 인덱스와 바꿔준다.

3. 현재 인덱스가 더 크면 교환하지 않고 다음 두 연속된 배열값을 비교한다,

4. 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복한다.

 

버블 정렬

 

배열의 구조가 어떻든 전체 비교를 진행하므로 시간복잡도는 O(n^2)

 

공간 복잡도는 하나의 배열에서만 진행하므로 O(n)

 

4. 합병 정렬 (Merge sort)

 

합병 정렬은 분할 정복(divide and conquer) 방식으로 설계된 방법이다.

* 분할 정복은 큰 문제를 반으로 쪼개 문제를 해결해나가는 방식이다.

 

** 분할은 배열의 크기가 1보다 작거나 같을 때까지 반복한다.

입력으로 하나의 배열을 받고, 이를 두 개의 배열로 계속 쪼개나간 뒤, 합치면서 정렬하여 최종적으로 하나의 정렬된 배열을 출력한다.

 

기본 로직은 다음과 같다. 

1. 현재 배열을 반으로 쪼갠다. (배열의 시작 위치와 종료 위치를 입력받아 둘을 더한 후 2로 나눈 뒤 그 위치를 기준으로 쪼갠다)

2. 분할한 배열의 크기가 0이나 1일때까지 반복한다.

 

** 합병은 두 개의 배열을 비교하여, 기준에 맞는 값을 다른 배열에 저장해 나간다.

 

기본 로직은 다음과 같다.

1. 두 배열 A,B의 크기를 비교한다. 각각의 배열의 현재 인덱스를 i,j로 가정한다.

2. i에는 배열 A의 시작 인덱스를 저장하고, j에는 B배열의 시작 주소를 저장한다.

3. A[i], B[j]를 비교한다. 오름차순의 경우 이 중 더 작은 값을 새 배열 C에 저장한다,

  A[i]가 더 큰 경우 A[i]의 값을 배열 C에 저장해주고 i++한다.

4. 이를 i/j가 둘 중 하나라도 각자 배열의 끝에 도달할 떄까지 반복한다.

5. 끝까지 저장을 못한 배열의 값을 순서대로 전부 C에 저장한다.

6. C배열을 원래 배열에 저장해준다.

 

합병 정렬

 

이 정렬 알고리즘은 분할 과정과 합병 과정이 나뉘어진다.

 

합병 과정의 시간복잡도는 전체 배열의 길이에 비례하므로 O(n)

분할 과정의 시간복잡도는 O(logN)이다. 

( * 크기가 N인 배열 분할 시, 한번 분할하면 N/2, N/2 2개. 그 다음 분할시 N/4,N/4,N/4,N/4, 4개 이므로 로그함수) 

 

따라서 합병 정렬의 시간 복잡도는 O(NlogN)

 

공간복잡도는 두개의 배열을 사용하므로 O(2N)

 

 

5. 퀵 정렬 (Quick Sort)

 

퀵 정렬 역시 분할 정복을 이용하여 정렬을 수행한다.

 

기준이 되는 값 pivot을 하나 설정하는데, 이를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식으로 정렬한다. 이를 반복하여 분할된 배열의 크기가 1이 되면 배열이 모두 정렬된다.

 

기본 로직은 다음과 같다,

1. pivot으로 잡은 배열의 값 하나를 정한다. (보통 맨 앞/ 맨 뒤/ 중간 값/ 랜덤 값 중 하나)

2. 분할을 진행하기에 앞서, 비교를 진행하기 위해 가장 왼쪽 배열의 인덱스를 저장하는 left 변수, 가장 오른쪽 배열의 인덱스를 저장하는 right 변수를 생성한다,

3. right부터 비교를 진행한다. 비교한 배열 값이 pivot보다 크면 right를 하나 감소시키고 비교를 반복한다.

 * pivot보다 작은 값을 찾으면 반복을 중지한다.

4. 그 다음 left부터 비교를 진행한다. 비교한 배열 값이 pivot보다 작으면 leff를 하나 증가시키고 비교를 반복한다. 

* pivot보다 큰 값을 찾으면 반복을 중지한다.

5. left 인덱스 값과 right 인덱스 값을 바꿔준다,

6. 3~5 과정을 left<right일 때까지 반복

7. 위 과정이 끝나면 left값과 pivot 값을 바꿔준다,

8. 맨 왼쪽부터 left-1까지, left+1부터 맨 오른쪽까지 나눠 퀵 정렬을 반복한다.

 

퀵 정렬

 

퀵 정렬은 분할과 동시에 정렬을 진행한다,

 

퀵 정렬은 배열의 크기만큼 비교를 진행하며, 총 분할 깊이인 logN만큼 진행하므로, 시간복잡도는 O(NlogN)

다만 최악의 경우(배열이 이미 정렬되어 있는경우) 분할이 N만큼 일어나므로, 시간복잡도는 O(n^2)

-> 이를 방지하기 위에 중간값/랜덤값으로 pivot을 정하기도 함

 

최악의 경우 때문에 합병 정렬보다 느리다고 생각할 수 있지만, 이는 발생하기 쉽지 않은 경우이고 일반적으로 퀵 정렬이 합병 정렬보다 더 빠르다.