데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.
내림차순 정렬은 오름차순 정렬을 수행한 뒤에 그 결과를 뒤집기하여 내림차순 리스트를 만들 수 있다. 리스트를 뒤집는 연산은 O(N)의 복잡도로 간단히 수행할 수 있음
선택 정렬
가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다.
1) 전체 중 가장 작은 데이터인 0과 맨 앞에 있는 데이터 7을 바꾼다.
| 7 | 5 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
2) 정렬된 첫 번째 데이터는 제외하고 이후 데이터 중 가장 작은 데이터인 1을 선택해서 처리되지 않은 데이터 중 가장 앞에 있는 데이터 5와 바꾼다
| 0 | 5 | 9 | 7 | 3 | 1 | 6 | 2 | 4 | 8 |
3) 위 과정 반복
| 0 | 1 | 9 | 7 | 3 | 5 | 6 | 2 | 4 | 8 |
선택 정렬 코드
static void SelectSort(int[] arr) {
for(int i=0; i<arr.length; i++){
int minIdx = i;
for(int j=i+1; j<arr.length; j++){
if(arr[j] < arr[minIdx]){
minIdx = j;
}
}
// swap
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
시간 복잡도 : O(n^2)
삽입 정렬
데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입한다.
삽입 정렬은 선택 정렬에 비해 구현 난이도가 높은 편이지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적이다.
삽입 정렬은 두 번째 데이터부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.
1) 첫 번째 데이터 '7'은 그 자체로 정렬되어 있다고 판단하고, 두 번째 데이터인 '5'가 어떤 위치로 들어갈지 판단한다. 이 경우에서는 5를 7의 왼쪽에 삽입한다.
| 7 | 5 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
2) 이어서 9가 어떤 위치에 들어갈지 판단한다. 삽입될 수 있는 위치는 총 3가지 이며 현재 9는 5와 7보다 크기 때문에 원래 자리 그대로 둔다.
| 5 | 7 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
3) 이어서 '0'이 어떤 위치에 들어갈지 판단한다. '0'은 '5', '7', '9'와 비교했을 때 가장 작기 때문에 첫번째 위치에 삽입한다.
| 5 | 7 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
4) 위 과정 반복
| 0 | 5 | 7 | 9 | 3 | 1 | 6 | 2 | 4 | 8 |
삽입 정렬 코드
static void InsertSort(int[] arr){
for(int i=1; i<arr.length; i++){
for(int j=i; j>0; j--){
if(arr[j] < arr[j-1]) {
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
else
break;
}
}
}
시간 복잡도 : O(N^2)
퀵 정렬
가장 많이 사용되는 알고리즘이다.
퀵 정렬에서는 피벗이 사용된다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 피벗이라고 표현한다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다. 대표적인 분할 방식으로는 호어 분할 방식이 있다.
호어 분할 : 리스트에서 첫 번째 데이터를 피벗으로 정한다.
피벗을 설정한 뒤 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다. 이러한 과정을 반복하면 '피벗'에 대하여 정렬이 수행된다.
1) 리스트의 첫 번째 데이터를 피벗으로 설정하므로 피벗은 '5'이다. 이후 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다. 이후 이 두 데이터의 위치를 서로 변경한다.
| 5 | 7 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
(피벗)
2) 1의 과정을 반복한다.
| 5 | 4 | 9 | 0 | 3 | 1 | 6 | 2 | 7 | 8 |
3) 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린 경우, '작은 데이터'와 '피벗'의 위치를 서로 변경한다. 즉, 작은 데이터인 '1'과 피벗인 '5'의 위치를 서로 변경하여 분할을 수행한다.
| 5 | 4 | 2 | 0 | 3 | 1 | 6 | 9 | 7 | 8 |
1과 피벗5 교환
4) 분할이 완료된 상태에서 왼쪽 리스트와 오른쪽 리스트를 개별적으로 정렬시킨다. 왼쪽 리스트와 오른쪽 리스트에도 각각 피벗을 설정하여 동일한 방식으로 정렬을 수행하면 전체 리스트에 대하여 모두 정렬이 완료된다.
| 1 | 4 | 2 | 0 | 3 | 5 | 6 | 9 | 7 | 8 |
| 1 | 4 | 2 | 0 | 3 |
| 6 | 9 | 7 | 8 |
종료 조건 : 데이터 개수가 1인 경우 까지 위 과정을 반복한다.
퀵 정렬 코드
static void QuickSort(int[] arr, int start, int end){
if(start >= end) return;
// 피벗은 첫 번째 원소
int pivot = start;
int left = start+1;
int right = end;
while(left <= right) {
// 피벗보다 큰 데이터 찾을 때까지 반복
while(left <= end && arr[left] <= arr[pivot]) {
left++;
}
// 피벗보다 작은 데이터를 찾을 때까지 반복
while(right > start && arr[right] >= arr[pivot]) {
right--;
}
// 엇갈렸으면 작은 데이터와 피벗을 교체
if(left > right) {
int temp = arr[pivot];
arr[pivot] = arr[right];
arr[right] = temp;
}
// 안 엇갈렸으면 작은 데이터와 큰 데이터 교체
else {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
QuickSort(arr, start, right-1);
QuickSort(arr, right+1, end);
}
시간 복잡도 : O(N log N)
계수 정렬
특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.
먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다. 아래와 같은 예시에서는 가장 큰 데이터가 '9'이고 가장 작은 데이터가 '0'이다. 따라서 우리가 정렬할 데이터의 범위는 0부터 9까지이므로 리스트의 인덱스가 모든 범위를 포함할 수 있도록 한다. 즉, 크기가 10인 리스트를 생성하면 된다.
- 초기 단계 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
처음에는 리스트를 0으로 초기화하고 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 된다.
- 초기 단계 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
- 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
위 과정 반복
- 7 5 9 0 3 1 6 2 9 1 4 8 0 5 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 9
계수 정렬 코드
// 모든 원소의 값이 0보다 크거나 같다고 가정
static void CountSort(int[] arr){
int max = Arrays.stream(arr).max().getAsInt();
// 모든 범위 포함하는 배열 선언
int[] temp = new int[max+1];
for(int i=0; i<arr.length; i++){
temp[arr[i]]++;
}
for(int i=0; i<temp.length; i++){
if(temp[i] > 0){
for(int j=0; j<temp[i]; j++)
System.out.print(i+" ");
}
}
}
시간 복잡도 : O(N + K)