'이것이 취업을 위한 코딩 테스트다 with 파이썬' 이라는 책을 공부 중입니다. 이 글은 해당 책의 내용 중 정렬 알고리즘 부분을 요약, 정리한 글입니다.
학습 목표
· 선택 정렬(Selection Sort)
· 삽입 정렬(Insertion Sort)
· 퀵 정렬(Quick Sort)
· 계수 정렬(Count Sort)
✍ ,정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다.
정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)이 가능해진다. 즉, 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하다.
선택 정렬(Selection Sort)
선택 정렬 알고리즘은 가장 원시적인 방법이다.
✍ 데이터가 무작위로 여러 개 있다고 가정하자. 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다.
다음은 선택 정렬을 사용하여 데이터를 오름차순으로 정렬한 코드다.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int []arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
int minIndex = 0; //가장 적은 원소의 인덱스
for(int i=0; i < arr.length; i++){
for(int j=i+1 ; j < arr.length; j++){
if(arr[minIndex] > arr[j])
minIndex = j;
}
//스와프
int tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
System.out.println(Arrays.toString(arr));
}
}
선택 정렬의 시간 복잡도
선택 정렬은 N-1 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해 비교 연산이 필요하다. 즉, 연산 횟수는 N + (N-1) + (N-2) + … + 2 이고, 근사치로 N x (N + 1) /2번의 연산을 수행한다.
빅오 표기법으로 간단히 O(N²)로 표현할 수 있다.
삽입 정렬(Insertion Sort)
✍ 삽입 정렬은 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입한다.
선택 정렬에 비해 실행 시간 측면에서 더 효율적이며, 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 더욱 효과적이다.
삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다.
다음은 주어진 데이터를 삽입 정렬하는 과정을 그림으로 표현한 것이다.
Step 0: 첫 번째 데이터 ‘7’은 그 자체로 정렬되어 있다고 판단하고, 두 번째 데이터인 ‘5’가 어떤 위치로 들어갈지 판단한다. ‘7’의 왼쪽으로 들어가거나 오른쪽으로 들어가는 두 경우만 존재한다. 오름차순으로 정렬 하므로 ‘7’의 왼쪽에 삽입한다.
Step 1: ‘9’가 어떤 위치에 들어갈 지 판단한다. 삽입될 수 있는 위치는 3가지이며 ‘9’는 ‘5’와 ‘7’ 보다 크기 때문에 원래 자리에 그대로 둔다.
Step 2: ‘0’이 어떤 위치에 들어갈지 판단한다. ‘0’은 ‘5’, ‘7’, ‘9’와 비교했을 때 가장 작기 때문에 첫 번째 위치에 삽입한다.
///////// 중략 /////////
Step 7
Step 8
Step 9: 이와 같이 적절한 위치에 삽입하는 과정을 N-1 번 반복하면, 다음과 같이 모든 데이터가 정렬된다.
삽입 정렬의 특징 & 소스코드
삽입 정렬이 이루어진 원소는 항상 오름차순을 유지하는 특징이있다. 즉, 위에서 하늘색으로 칠해진 카드들은 어떤 단계든 항상 정렬된 상태다.
이러한 특징으로 삽입 정렬에서 특정한 데이터가 삽입될 위치를 선정할 때, 삽입될 데이터보다 작은 데이터를 만나면 더 이상 데이터를 살펴볼 필요 없이 그 위치에서 멈추면 된다.
다음은 삽입 정렬을 사용하여 데이터를 오름차순으로 정렬한 코드다.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int []arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
for(int i=1; i < arr.length; i++){
for(int j=i ; j >= 1; j--){
if(arr[j] < arr[j-1]){ //한 칸씩 왼쪽으로 이동
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}else break; //자기보다 작은 데이터를 만나면 그 위치에서 멈춤
}
}
System.out.println(Arrays.toString(arr));
}
}
삽입 정렬의 시간 복잡도
삽입 정렬은 반복문이 2번 중첩 사용되며, 시간 복잡도는 O(N²)이다. 실제로 수행 시간을 테스트해보면 선택 정렬과 비슷한 시간이 소요된다.
✍ 하지만 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하고, 최상의 경우 O(N)의 시간 복잡도를 지닌다. 이렇게 거의 정렬되어 있는 상황에서는 퀵 정렬 알고리즘보다도 강력할 수 있다.
퀵 정렬
가장 많이 사용되는 정렬 알고리즘이다. 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이기도 하다.
✍퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 이러한 교환을 위한 기준을 ‘피벗’이라고 한다. 퀵 정렬을 수행하기 전 피벗을 어떻게 설정할 것인지 미리 명시해야 한다.
피벗을 설정하고 리스트를 분할하는 방법에 따라 여러 가지 방식으로 퀵 정렬을 구분한다. 책에서는 가장 대표적인 분할 방식인 호어(Hoare) 분할 방식을 기준으로 퀵 정렬을 설명한다.
호어 분할 방식은 ‘리스트에서 첫 번째 데이터를 피벗으로 정한다’는 규칙으로 피벗을 설정한다.
이렇게 피벗을 설정한 뒤에는 왼쪽부터 피벗보다 큰 데이터를 찾고, 오른쪽부터 피벗보다 작은 데이터를 찾는다. 그다음 큰 데이터와 작은 데이터의 위치를 서로 교환한다. 이 반복하면 ‘피벗’에 대한 정렬이 수행된다.
다음은 주어진 데이터를 퀵 정렬하는 과정을 그림으로 표현한 것이다. 편의상 퀵 정렬 전체를 3개의 파트로 나누어 설명한다.
파트 1
step 0: 리스트의 첫 번째 데이터 ‘5’를 피벗으로 설정한다. 이후 왼쪽에서부터 ‘5’보다 큰 데이터 ‘7’을 선택하고 오른쪽에서부터 ‘5’보다 작은 데이터를 ‘4’를 선택하여, 두 데이터의 위치를 서로 변경한다.
step 1: 피벗보다 큰 데이터와 작은 데이터를 각각 찾는다. ‘9’와 ‘2’가 선택되고, 두 값의 위치를 서로 변경한다.
step 2: 피벗보다 큰 데이터와 작은 데이터를 각각 찾는다. 이때 현재 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린다. 이렇게 두 값이 엇갈린 경우 ‘작은 데이터’와 ‘피벗’의 위치를 서로 변경한다. 즉, ‘1’과 피벗인 ‘5’의 위치를 서로 변경하여 분할을 수행한다.
step 3(분할 완료): ‘5’의 왼쪽에 있는 데이터는 모두 ‘5’보다 작고, 오른쪽에 있는 데이터는 모두 ‘5’보다 크다. 이렇게 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하도록 하는 작업을 ‘분할’ 혹시 ‘파티션’이라고 한다.
이런식으로 왼쪽 리스트와 오른쪽 리스트의 각각 피벗을 설정하여 동일한 방식으로 정렬을 수행하면, 전체 리스트에 대하여 모두 정렬이 이루어진다.
파트 2
왼쪽 리스트에서는 다음 그림과 같이 정렬이 진행되며 구체적인 정렬 과정은 동일하다.
파트 3
오른쪽 리스트에서는 다음과 같이 정렬이 진행되며 구체적인 정렬 과정은 동일하다.
전체 과정은 다음과 같다.
퀵 정렬의 특징 & 소스코드
퀵 정렬에서는 이처럼 특정한 리스트에서 피벗을 설정하여 정렬을 수행한 이후에, 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행한다.
✍이는 ‘재귀 함수’와 동작 원리가 같다.
실제로 퀵 정렬은 재귀 함수 형태로 작성하면 구현이 매우 간결하다. 이때 재귀 함수의 종료 조건은 현재 리스트의 데이터 개수가 1개인 경우다.
다음은 퀵 정렬을 사용하여 데이터를 오름차순으로 정렬한 코드다.
public class QuickExam {
public static void main(String[] args){
int array[] = {5, 7, 9, 0, 3, 1, 6, 2, 4, 8};
quickSort(array, 0, array.length -1);
for (int i : array) {
System.out.printf("%d ",i);
}
}
public static void quickSort(int array[], int start, int end){
if(start>=end) //원소가 1개인 경우 종료
return;
int pivot = start; //피벗은 첫 번째 원소
int left = start+1;
int right = end;
while ( left <= right){
//피벗보다 큰 데이터를 찾을 때까지 반복
while (left <= end && array[left] <= array[pivot])
left+=1;
//피벗보다 작은 데이터를 찾을 때까지 반복
while(right > start && array[right] >= array[pivot])
right-=1;
if(left > right){ // 엇갈렸다면 작은 데이터와 피벗을 교체
int tmp = array[right];
array[right] = array[pivot];
array[pivot] = tmp;
}else{ //엇갈리지 않았다면 적은 데이터와 큰 데이터를 교체
int tmp = array[right];
array[right] = array[left];
array[left] = tmp;
}
//분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quickSort(array, start, right -1);
quickSort(array, right +1, end);
}
}
}✍퀵 정렬의 평균 시간 복잡도는 O(NlogN)이고, 최악의 경우 O(N²)이다.
계수 정렬 (Count Sort)
✍계수 정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있는 매우 빠른 정렬 알고리즘이다.
모든 데이터가 양의 정수인 상황에서 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(N+K)를 보장한다.
하지만 계수 정렬은 ‘데이터의 크기 범위가 제한 되어 정수 형태로 표현할 수 있을 때’만 사용할 수 있다. 즉, 무한한 범위와 실수형 데이터에는 사용할 수 없다. 일반적으로 데이터의 최소, 최대의 차가 1,000,000을 넘지 않을 때 효과적이다.
✍이유는 계수 정렬은 모든 범위를 담을 수 있는 크기의 리스트(배열)을 선언해야 하기 때문이다.
계수 정렬롸 다음과 같은 데이터를 정렬한다고 가정하자.
7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
👆먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다.
여기서는 ‘0’가 가장 작은 데이터, ‘9’가 가장 큰 데이터이므로 크기가 10인 리스트를 선언한다. 그리고 리스트의 모든 데이터가 0이 되도록 초기화한다.
✌다음으로 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다.
step 1
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
step 2
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
step 3
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
-- 과정 반복 --
step 14
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
2 |
2 |
1 |
1 |
1 |
2 |
1 |
1 |
1 |
2 |
step 15
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
2 |
2 |
2 |
1 |
1 |
2 |
1 |
1 |
1 |
2 |
✍결과적으로 리스트에 각 데이터가 몇 번 등장했는지 횟수가 기록된다.
정렬된 결과를 눈으로 확인하고 싶다면, 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하면 된다.
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
2 |
2 |
2 |
1 |
1 |
2 |
1 |
1 |
1 |
2 |
출력 결과 0 0 1 1 2 2 3 4 5 5 6 7 8 9
계수 정렬의 특징 & 소스코드
public class CountSortExam {
public static void main(String args[]){
//모든 원소의 값이 0보다 크거나 같다고 가정
int arr[] = {7, 5 , 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
//모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화, int는 기본적으로 0으로 초기호)
int []count = new int [arr.length];
for (int i = 0; i < count.length; i++) {
count[arr[i]] += 1; //각 데이터에 해당하는 인덱스의 값 증가
}
for (int i = 0; i < count.length; i++) { //배열에 기록된 정렬 정보 확인
for (int j = 0; j < count[i]; j++) {
System.out.printf("%d ", i); // 등작한 횟수만큼 인덱스 출력
}
}
}
}
✍모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때 계수 정렬의 시간 복잡도는 O(N+K)다.
계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에 적절한 인덱스의 값을 1씩 증가시키며, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복 수행하기 때문이다.
✍현존하는 정렬 알고리즘 중 기수 정렬(radix sort)과 더불어 가장 빠른 알고리즘이다.
보통 기수 정렬이 계수 정렬 보다 동작이 느리고, 알고리즘 원리나 소스코드는 더 복잡하다. 하지만 처리할 수 있는 정수의 크기는 더 크다. (단, 반드시 기수 정렬을 이용해야만 해결할 수 있는 문제는 코딩 테스트에 거의 출제 안됨)
✍계수 정렬의 공간 복잡도는 (N+K)이다.
단, 데이터의 크기가 커지만 심각하게 비효율적이다. 예를 들어 데이터가 0과 999,999 두 개만 존재할 때도 리스트의 크기가 100만 개가 되도록 선언해야한다.
따라서 계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다.
'알고리즘&코딩테스트' 카테고리의 다른 글
| [Algorithm] 이것이 코딩테스트다 - 이진탐색 문제풀이(with 자바) (0) | 2021.09.13 |
|---|---|
| [Algorithm] 순차 탐색과 이진 탐색 (0) | 2021.09.06 |
| [Algorithm] 복잡도 (with 자바) (0) | 2021.02.03 |
| [Algorithm] BFS 문제 풀이 - 미로 탈출 (자바코드) (0) | 2021.02.02 |
| [Algorithm] DFS 문제 풀이 - 음료수얼려먹기 (자바코드) (0) | 2021.02.01 |
댓글