[이코테-6] 정렬 알고리즘

 

정렬

정렬이란, 데이터를 특정한 기준에 따라 순서대로 나열하는 것이다. 정렬 알고리즘의 종류는 많지만, 이번 포스팅에서는 <이코테> 강의에서 다루는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬만을 소개하겠다.

 

선택 정렬 (Selection Sort)

처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 알고리즘이다. 

예를들어 아래와 같은 숫자들의 배열이 있다고 하자.

1. 정렬되지 않은 전체 배열에서 최솟값 (0)을 찾고, 맨 앞의 데이터 (7)과 바꾼다.

2. 정렬된 0을 제외하고 나머지 정렬되지 않은 배열에서 최솟값 (1)을 찾고, 맨 앞의 데이터 (5)와 바꾼다.

위와 같은 방법을 반복하게되면, 전체 정렬된 배열은 다음과 같이 나온다.

선택정렬 - 시간 복잡도

선택 정렬은 N번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야된다. 그리고 각 횟수마다 N개 중에 찾기, N-1개 중 찾기, ..., 2개 중 찾기이므로, 총 시간 복잡도는 N+ (N-1) + (N-2) + ... + 2 => O(N^2)이다.

 

선택정렬 - 소스코드 <Python>

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)):
	min_index = i
    for j in range(i+1,len(array)):
    	if array[min_index] > array[j]:
        	min_index = j
        array[i],array[min_index] = array[min_index],array[i]
print(array)

선택정렬 - 소스코드 <JavaScript>

let array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8];

for (let i = 0; i<array.length; i++){
	let minIndex = i;
    for (let j = i + 1; j < array.length; j++){
    	if (array[minIndex] > array[j]){
        	minIndex = j;
        }
    }
    [array[i], array[minIndex]] = [array[minIndex],array[i]];}
    
console.log(array);

 

 

삽입 정렬 (Insertion Sort)

삽입 정렬은 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 알고리즘이다. 선택 정렬에 비해 구현 난이도는 높지만, 일반적으로 더 효율적이다. 삽입정렬은 다음과 같은 순서대로 정렬된다.

 

1. 첫 번째 데이터인 '7'은 이미 정렬되어있다고 판단하고 두 번째 데이터인 '5'가 어느 위치로 들어갈지 판단한다. 7의 왼쪽이나 오른쪽으로 들어가는 두 가지 경우만 존재한다. 5는 7보다 작으므로, 7의 왼쪽으로 들어가게 된다.

2. 그 다음 데이터인 9는 7보다 크니까 오른쪽인 현재 위치를 유지한다.

3. 그 다음 데이터인 '0'은 왼쪽 데이터인 9보다 작으므로 왼쪽에 위치한다. 7, 5보다도 왼쪽에 위치하므로, 5의 왼쪽으로 들어가게 된다.

4. 위와 같은 과정을 반복하면 다음과 같이 정렬된다.

 

 

삽입정렬 - 소스코드 <Python>

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(1,len(array)):
	for j in range (i,0,-1):
    	if array[j] < array [j-1]:
        	array[j], array[j-1] = array[j-1], array[j]
        else:
        	break
print(array)

삽입정렬 - 소스코드 <JavaScript>

let array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8];
for (let i = 0; i < array.length; i++){
	for (let j = i; j>0; j--){
    	if (array[j] < array[j-1]){
        	[array[j], array[j-1]] = [array[j-1],array[j]];}
        else{
        	break;}}}
            
console.log(array);

 

삽입정렬 - 시간복잡도

반복문이 두 번 중첩되었으므로 시간복잡도는 O(N^2)이다.

그러나 현재 리스트 데이터가 거의 정렬되어있다면 매우 빠르게 동작한다.

최선의 경우(이미 다 정렬되어있는 경우) : O(N)

퀵 정렬 (Quick Sort)

기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.

대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이다. 기본적으로는 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.

1. 첫 번째 데이터인 '5'를 기준으로 하고, 왼쪽에서 '5'보다 큰 데이터(7)를 선택한고 오른쪽에서는 '5'보다 작은 '4'를 선택한다. 두 데이터의 위치를 서로 변경한다.

2. 피벗은 여전히 5이고 1번 과정을 계속 반복한다. 그러면 5보다 큰 데이터인 '9'와, 5보다 작은 데이터인 '2'의 위치가 바뀐다.

3. 이 과정을 반복하다가 왼쪽에서부터 5보다 큰 6과, 오른쪽에서부터 5보다 작은 1의 위치가 엇갈리게 되었다. 이 경우에는 피벗과 작은 데이터(1)의 위치를 변경한다.

4. 위의 과정을 반복하여 최종적으로 정렬된 데이터는 아래와 같다.

위와 같이 하나의 피벗값에 대해 왼쪽/오른쪽으로 데이터 묶음이 나뉘었다. 이를 분할이라고 한다.

이 과정을 재귀적으로 수행하다보면 피벗값을 기준으로 정렬되어야 하는 범위는 점점 작아진다.

 

퀵정렬-시간복잡도

퀵 정렬은 분할이 절반씩 일어나는 경우가 이상적이다. 이 경우는 전체 연산 횟수로 O(NlogN)을 기대할 수 있다.

그러나 최악의 경우, O(N^2)의 시간복잡도를 가진다. 첫 번째 원소를 피벗으로 삼고, 이미 정렬된 배열에 대해 퀵 정렬을 수행하면 피벗보다 작은(왼쪽에 오는) 데이터가 없으므로 매번 분할이 일어날 때마다 왼쪽은 없고 오른쪽만 남는 형태로 남는다. 이렇게 분할을 하기 위해서 매번 선형탐색을 해야되기 때문에 이 경우는 O(N^2)의 시간복잡도를 갖는 것이다.

 

퀵정렬 - 소스코드 <Python>

array = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(array):
	if len(array) <= 1:
    	return array #리스트가 하나 이하의 원소만 있다면 종료
    pivot = array[0]
    tail = array[1:] #피벗을 제외한 리스트
    
    left_side = [x for x in tail if x<= pivot]
    right_side = [x for x in tail x > pivot]
    
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

퀵정렬 - 소스코드 <JavaScript>

let array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8];

function quickSort(array) {
    if (array.length <= 1) {
        return array;
    }

    let pivot = array[0];           // 첫 번째 원소를 피벗으로 설정
    let tail = array.slice(1);      // 피벗 제외한 나머지 리스트

    let leftSide = tail.filter(x => x <= pivot); // 분할된 왼쪽 부분
    let rightSide = tail.filter(x => x > pivot); // 분할된 오른쪽 부분

    // 분할 이후 왼쪽, 피벗, 오른쪽을 합쳐 반환
    return [...quickSort(leftSide), pivot, ...quickSort(rightSide)];
}

console.log(quickSort(array));

 

 

계수 정렬 (Counting Sort)

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다. 아래와 같은 방법으로 정렬된다.

1.  가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성한다.
    예를들어, 정렬한 데이터가 75 9 0 3 1 6 2 9 1 4 8 0 5 2 라면, 인덱스가 0~9까지인 리스트를 생성한다.

2.  데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.

3. 계속 반복하다가 결과적으로는 최종 리스트에는 각 데이터가 몇 번씩 등장했는지 횟수가 기록된다.

 

 결과를 확인할 때는 리스트의 첫 번째 데이터부터하나씩 그 값을 반복하여 인덱스를 출력한다. 

최종 결과는 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9 

 

이 정렬 알고리즘은 공간 복잡도는 높지만 퀵정렬에 비해 조건만 맞다면 매우 빠른 알고리즘이다.

퀵정렬 - 소스코드 <Python>

array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
count = [0] * (max(array) + 1)

for i in range (len(array)):
	count[array[i]] += 1
for j in range (len(count)):
	for j in range((count[i]):
    	print(i, end='')

퀵정렬 - 소스코드 <JavaScript>

let array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
let count = new Array(Math.max(...array)+1).fill(0);

for (let i = 0; i < array.length < i++){
	count[array[i]] += 1;}
    
let result = [];
for (let i = 0; i < count.length < i++){
	for (let j = 0; j < count[i].length < j ++){
		result.push(i);
    }
}	
console.log(result.join(" "));

 

퀵정렬 - 시간복잡도

시간,공간복잡도는 모두 O(N+K)이다. 데이터의 개수만큼 데이터를 확인하며 count를 체크하므로 O(N)이고, 원소 중 가장 큰 값인 K 만큼 인덱스를 확인하기에 그 값만큼 출력한다. 따라서 이중반복문의 시간복잡도는 O(N+K)이다.

경우에 따라서는 제일빠르지만, 범위가 너무 크면 심각하게 비효율적이다. 예를들어, 0과 999,999로 두 개의 데이터만 존재하는 경1,000,000의 크기를 갖는 리스트를 만들어야되므로 공간복잡도가 굉장히 높다.

따라서 이 정렬 알고리즘은 동일한 값을 가지는 데이터가 여러개 등장할 때 효과적이다.

 

정렬 알고리즘 비교

앞서 다룬 네 가지 정렬 알고리즘을 비교하면 다음과 같다. 대부분의 프로그래밍 언어에서 지원하는 표준정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어있다.

정렬 알고리즘	평균 시간복잡도	공간 복잡도	특징
선택 정렬	O(N^2)	O(N)	아이디어가 간단
삽입 정렬	O(N^2)	O(N)	데이터가 거의 정렬되어있으면 제일 빠름
퀵 정렬	O(NlogN)	O(N)	대부분의 경우에 가장 적합, 빠름
계수 정렬	O(N+K)	O(N+K)	데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만 매우 빠름