밍경송의 E.B
선택 정렬(Selection sort)와 삽입 정렬(Insertion sort) 본문
오늘은 길었던 정통공과 이별하고,, 알고리즘의 아주 기초적이지만 나는 모르는 .. 개념들에 대해서 정리해보겠습니다. 아자
이전에 버블정렬(bubble sort) 알고리즘에 대해서 간략하게 정리했었는데요. 그때 버블 정렬의 시간 복잡도를 O(N^2)로 나타낼 수 있다고 배웠습니다. 오늘은 선택정렬과 삽입정렬에 대해서 다뤄볼텐데, 버블 정렬까지 세 알고리즘이 어떻게 다른지! 시간 복잡도는 어떤지! 이해해봅시다.
선택정렬(Selection sort)
선택 정렬의 키워드는 최솟값입니다. 간단하게 말하자면 배열의 왼쪽부터 시작해서 맨 마지막 셀까지 쭉 돌면서, 최솟값을 저장하고 순회가 끝나면 이를 맨 왼쪽 인덱스 값(인덱스 0이 아닐 수 있음)과 교환해주고,,그 과정을 정렬될 때까지 계속 반복하는 그런 알고리즘입니다.
이전에 배웠던 버블 정렬은 두 개의 포인터를 이용해 값을 비교하고 순서가 바뀌어 있으면 둘을 교환해줘서 패스스루가 끝날 때마다 그 당시의 맨 오른쪽 셀에 정렬된 값이 들어갔었는데요. 그러니까 최댓값이 먼저 정렬되는 것이죠.
그런데, 선택 정렬의 경우, 패스스루마다 최솟값을 저장하고 그것을 그 당시의 맨 왼쪽 셀에 저장하기 때문에 최솟값이 먼저 정렬된다는 중요한 차이가 있습니다.
여러 정렬 알고리즘을 배우다보면 뭐가 뭔지 헷갈릴 수 있으니 처음 배울 때 잘 익혀두면 좋을 것 같아요..
그럼 선택 정렬의 과정을 한 번 들여다봅시다.
1) 배열의 각 셀을 왼쪽부터 오른쪽 방향으로 확인하면서 어떤 값이 최솟값인지 결정한다. 한 셀씩 이동하면서 현재까지 가장 작은 값을 기록한다(변수에 인덱스를 저장함). 변수에 들어 있는 값보다 작은 값이 들어 있는 셀을 만나면 변수가 새 인덱스를 가리키도록 값을 대체한다.
2) 이제 최솟값이 어느 인덱스에 들어 있는지 알았으므로 그 인덱스의 값과 패스스루를 처음 시작했을 때의 값을 교환한다. 첫 패스스루를 시작했을 때 인덱스=0, 그 다음 패스스루에서 인덱스=1, ...
3) 매 패스스루는 1), 2) 단계로 이루어지고, 배열 끝에서 시작하는 패스스루에 도달할 때까지 패스스루를 반복한다. 마지막 패스스루에서는 배열이 완벽하게 정렬!
한 패스스루만 연습해봅시다!
[ 2 , 6 , 1 , 3 ]
↑ (현재 최솟값:2)
[ 2 , 6 , 1 , 3 ]
↑ (현재 최솟값:2)
[ 2 , 6 , 1 , 3 ]
↑ (현재 최솟값:1)
[ 2 , 6 , 1 , 3 ]
↑ (현재 최솟값:1)
[ 1 , 6 , 2 , 3 ]
최솟값인 1을 맨 왼쪽 셀과 교환
--> 첫번째 패스스루 끝
쉽쬬.. 이제 인덱스0(현재 1)에는 정렬된 값(최솟값)이 들어간 상태니까 다음 패스스루는 인덱스1(현재 6)부터 시작하면 됩니다. 그렇다면! 선택정렬을 한 번 코드로 구현해보겠습니다.
function selectionSort(array) {
for(let i =0; i < array.length - 1 ; i++) { //각 패스스루를 나타내는 루프(0부터 마지막인덱스-1)
//마지막 인덱스는 안 봐도 됨
let lowestNumberIndex = i; //최솟값 넣어줄 변수 선언
for (let j = i+1; j < array.length; j++) { //패스스루 안에서, 배열의 나머지값 확인
if (array[j] < array[lowestNumberIndex]) {//현재 최솟값보다 더 작은 값이 있다면 교환(인덱스넘버를)
lowestNumberIndex =j;
}
}
if(lowestNumberIndex != i) { //최솟값이 맨 왼쪽 값이 아니라면, 현재 최솟값과 맨 왼쪽값 교환
let temp = array[i];
array[i] = array[lowestNumberIndex];
array[lowestNumberIndex] = temp;
}
}
return array; //정렬된 배열 출력
}
선택정렬의 효율성
선택정렬은 비교와 교환을 거칩니다. 여기서 교환은 패스스루당 최대 한 번(맨 왼쪽값과 최솟값의 불일치시) 일어나게 됩니다. 교환의 과정 때문에, 선택정렬은 버블정렬과 비교했을 때, 최악의 경우에도 2배 빠르게 정렬을 할 수 있는데요.
이를 빅 오 표기법으로 나타내면 O(N^2 / 2)가 되겠죠?
라고 생각했다면 땡! 선택정렬을 빅 오 표기법으로 나타내면 버블정렬과 동일하게 O(N^2)이라고 합니다. 이유가 뭘까요?
"빅 오 표기법은 상수를 무시한다"
빅오의 본질에서 살펴봤듯, 빅 오 표기법은 데이터가 늘어날 때 알고리즘 단계 수가 장기적으로 어떤 궤적을 그리는지를 중요하게 생각합니다. 그러니까 다시 말하면, 빅 오 표기법은 단지 알고리즘의 카테고리를 분류해주는 것. 그 뿐이라는 뜻입니다. O(N)은 직선 성작을, O(N^2)은 지수 성장을 보여주는데 이 둘 완전 다른 카테고리에 속한다는 것을 알 수 있죠. 하지만, 10N이든 100N 빅오 표기법으로 나타내면 모두 O(N)이 되는 거죠. 둘은 O(N)이라는 같은 카테고리에 속하니까요.
뭐 어쨌든 최악의 경우, 선택 정렬이 버블 정렬보다 2배 빠른 알고리즘이라는 것은 알아둡시다 :)
자 그렇다면 삽입 정렬에 대해서 알아봅시다.
삽입 정렬(Insertion Sort)
삽입정렬은 간단히 말하자면 특정 인덱스의 값을 빼서 공백으로 두고, 본인의 왼쪽 인덱스들을 돌면서 알맞은 자리를 찾아 삽입해주는 방법인데요. 일부로 배열 중 한 인덱스의 값을 다른 곳으로 옮겨 공백을 만들고, 이 값과 공백의 왼쪽 값들을 비교하여 왼쪽 값들 중 더 큰 값이 있으면 오른쪽으로 shift해주어 공백을 옮겨주고, 나중에 다른 곳으로 옮긴 값을 다시 공백에 넣어.. 배열을 정렬해나가는 알고리즘입니다.
과정은 이러합니다.
1) 첫번째 패스스루에서 임시로 인덱스1(두번째 셀)의 값을 삭제하고 이 값을 임시 변수에 저장한다. 인덱스 1에 값이 없으므로 공백이 생긴다. 이후 각 패스스루마다 다음 인덱스의 값을 삭제한다(두번째 패스스루에서는 인덱스 2의 값 삭제).
2) 다음으로 공백 왼쪽에 있는 각 값을 가져와 임시 변수에 있는 값과 비교하는 시프트 단계를 시작한다. 공백 왼쪽에 있는 값이 임시 변수에 있는 값(삭제된 값)보다 크면 그 값을 오른쪽으로 시프트한다. 시프트-> 자연히 공백이 왼쪽으로 옮겨짐! 임시로 삭제한 값보다 작은 값을 만나거나 배열의 왼쪽 끝에 도달해야 시프트 단계가 끝난다.
3) 이제 임시로 제거한 값을 현재 공백에 삽입한다.
4) 1) - 3)단계까지가 하나의 패스스루다. 배열의 마지막 인덱스에서 패스스루를 시작할 때까지 패스스루를 반복한다. 이때가 되면 배열은 완전히 정렬된다.
한 패스스루만 연습해봅시다.
[ 4 , 2 , 7 , 1 ,3 ]
↑ 삭제(변수에 저장)
[ 4 , 2 , 7 , 1 ,3 ]
↑와 2(임시값) 비교
[ , 4 , 7 , 1 ,3 ]
↑ 4가 2보다 크기 때문에 오른쪽(공백자리)로 shift
[ , 4 , 7 , 1 ,3 ]
↑ 공백이 배열의 왼쪽 끝에 있으므로 비교/이동 불가
[ 2 , 4 , 7 , 1 ,3 ]
↑ 2(임시값)을 공백에 삽입
첫번째 패스스루 종료!
이제 두번째 패스스루에서는 다음 인덱스의 값(7) 삭제하여 공백을 만들고 시작하는데, 이때 공백의 왼쪽은 나? 정렬이 된 상태기 때문에! 비교해나가다가 임시값보다 더 작은 값을 만나면 더 왼쪽으로 갈 필요는 없습니다.
그렇다면 삽입 정렬(Insertion sort)를 코드로 구현해봅시다.
def insertion_sort(array):
for index in range(1 , len(array)): #배열 순회 시작
temp_value = array[index]; #삭제된 값을 변수에 저장
position = index -1 #position이라는 변수는 삭제값의 왼쪽부터 시작
while position > =0: #position값이 0보다 크거나 같은 경우동안 패스스루 진행
if array[position] > temp_value: #비교하는 값이 임시값보다 크다면
array[position+1] = array[position] #비교값을 오른쪽으로 시프트
position = position -1 #position은 왼쪽으로 쭉쭉 가
else: #position에 있는 값이 temp_value보다 같거나 작을때
break #패스스루 종료
array[position + 1] = temp_value #임시값을 현 공백에 삽입
return array
삽입정렬의 효율성
삽입정렬에 포함된 단계는 삭제, 비교, 시프트, 삽입 . 이렇게 총 4단계입니다. 중간 과정은 생략하고 결론부터 말하면, 삽입정렬은 최악의 경우 N^2의 비교와 시프트(합쳐서), N-1번의 삭제와 삽입(각각) 과정을 거칩니다. 그러니까 N^2 +2N -2 단계가 걸리는 알고리즘인 거죠. 그런데 우리는 위에서 빅 오 표기법이 상수를 무시한다는 것을 배웠습니다.
그렇다면 삽입정렬의 효율성은 O(N^2 + 2N)으로 나타낼 수 있을까요?
땡! ... 이유는요. 우리가 빅오 표기법에 대해 알아야 할 한가지 정보가 더 있기 때문입니다.
"다양한 차수가 한데 섞여 있을 때 빅 오 표기법은 가장 높은 차수의 N만 고려한다."
이유는.. 데이터의 개수인 N이 증가할 수록 높은 차수가 차지하는 비중이 더 커지기 때문에 낮은 차수는 무시하기로 했기 때문입니다. 그러니까 결국 삽입정렬의 효율성을 빅 오 표기법으로 나타내면 앞에서 배운 버블, 선택 정렬과 동일하게 O(N^2)이 되는거죠.
그런데, 우리는 여기서 한 가지 추가로 짚고 넘어가야 할 부분이 있습니다. 거두절미하고, 삽입 정렬은 시나리오에 따라 성능이 크게 좌우되는 알고리즘이라는 것인데요.
| 최선의 시나리오 | 평균 시나리오 | 최악의 시나리오 | |
| 선택정렬 | N^2/2 | N^2 /2 | N^2 /2 |
| 삽입정렬 | N | N^2 /2 | N^2 |
그러니까, 보통 빅 오 표기법은 최악의 시나리오일 때를 생각하기 때문에, 그 경우에는 선택정렬이 삽입정렬보다 2배나 빠른 알고리즘이라고 할 수 있습니다. 하지만, 대부분의 알고리즘은 평균적인 경우가 많다는 점을 생각하면.. 선택정렬과 삽입정렬의 효율성이 동일하다고도 할 수 있겠습니다. 헷
그럼 이상으로 선택정렬과 삽입정렬에 대한 포스팅을 마치겠습니다 땡큐~
이 글은 <누구나 자료구조와 알고리즘 개정 2판>, 제이 웬그로우 지음, 심지현 옮김 의 내용을 바탕으로 작성하였습니다.
'CSE > 자료구조&알고리즘' 카테고리의 다른 글
| <3> 배열, 구조체, 포인터 (0) | 2023.10.25 |
|---|---|
| <2> 순환(Recursion) 과 반복(Iterative) (0) | 2023.10.25 |
| <1> 자료구조와 알고리즘 (0) | 2023.10.24 |
| 빅 오 표기법 - O(1), O(N), O(log N) (0) | 2023.04.17 |
| 선형 탐색(linear search)과 이진 탐색(binary search) (0) | 2023.04.05 |
