전체 정렬 개요의 설명은 여기를 참조
Shell 정렬의 설명은 여기를 참조
Merge 정렬의 설명은 여기를 참조
Quick 정렬의 설명은 여기를 참조
Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조
Counting 정렬의 설명은 여기를 참조
Radix 정렬의 설명은 여기를 참조
Bucket 정렬의 설명은 여기를 참조
Topological 정렬의 설명은 여기를 참조
1. Bubble Sort(버블 정렬)
설명보단 보는 것이 제일 빠르다. 다음의 애니메이션을 보고 버블 정렬이 무엇인지 이해해보자.
한 눈에 보아도 이해가 쉽다. 오름차순 정렬을 기준으로 보여주는 애니메이션이다. 연속된 값들을 서로 비교하면서 더 작은 값이 왼쪽에 위치하도록 상호 위치 변경을 해주는 작업을 해주고 있다.
버블 정렬의 특징은 다음과 같다.
| 특성 | 설명 |
| In-place 알고리즘 | Memory 상에서 필요 시 상호 위치만 변경될 뿐 추가적인 배열 생성이 불 필요함 |
| Stable 알고리즘 | 구현하기 나름이나, 기본적으로 값이 같으면 정렬 순서를 바꾸지 않는다. |
버블 정렬의 시간 / 공간 복잡도는 아래와 같다.
| 알고리즘 | 시간복잡도(최상) | 시간복잡도(평균) | 시간복잡도(최악) | 공간복잡도 |
| 버블 정렬 | O(n) | O(n^2) | O(n^2) | O(1) |
버블 정렬 코드는 다음과 같다. (애니메이션과 달리 좌측에서 부터 정렬 시작, 반대 방식은 직접 코딩하기를 권장)
package com.test;
public class BubbleSort {
public static void main(String[] args){
int[] intArray = { 20, 35, -15, 7, 55, 1, -22};
// 정렬되지 않은 Index를 지정하여 해당 partition을 기반으로 재정렬을 시도한다.
for(int lastUnsortedIndex = intArray.length-1; lastUnsortedIndex > 0; lastUnsortedIndex--){
// 정렬되지 않은 부분의 Partition 내부 인접 요소 검사하는 부분
for(int i=0; i < lastUnsortedIndex; i++){
// 오름차순 정렬 기반으로 낮은 인덱스를 가진 요소가 인접 요소보다 큰 값인 경우 위치 상호 변경
// 아래가 등호이므로 Stable을 유지할 수 있음
if(intArray[i] > intArray[i+1]){
// swap하기 위한 method를 호출하는 부분
swap(intArray, i, i+1);
}
}
}
for(int i=0; i < intArray.length; i++){
System.out.println(intArray[i]);
}
}
// 인접한 요소끼리의 위치를 변경한다.
public static void swap(int[] array, int i, int j){
if(i==j){
return;
}
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
2. Selection Sort(선택 정렬)
이번에도 애니메이션을 한 번 보자.
이것도 쉽게 이해할 수 있을 것이다. 전체 값을 한 번 훑고 가장 작은 값을 찾아서 현재 정렬되지 않은 partition의 가장 작은 인덱스 값과 상호 위치를 바꾸고 있다.
선택 정렬의 특징은 다음과 같다.
| 특성 | 설명 |
| In-place 알고리즘 | Memory 상에서 필요 시 상호 위치만 변경될 뿐 추가적인 배열 생성이 불 필요함 |
| Unstable 알고리즘 | Stable을 보장할 수 없다. 그 이유는 아래에 설명 |
왜 선택 정렬이 Stable을 보장할 수 없을까? 아래의 예시를 보자.
| Index | 0 | 1 | 2 | 3 | 4 |
| Value | 4 | 2 | 3 | 4 | 1 |
여기서 가장 작은 값은 1이다. 그 1의 위치는 Index 0의 위치와 상호 변경될 것이다. 그러면 Stable을 유지하기 위해서는 Index 0의 4와 Index 3의 4가 순서가 유지되어야 하는데 Index3의 4가 더 앞 쪽에 자리잡게 되었기 때문에 Unstable하다.
만약 Stable을 유지하고 싶다면 방법은, 최소값인 1을 찾고 1과 Index 0의 4를 상호 변경하는게 아니라 Index 0 ~ 3까지를 Index 1 ~ 4로 한 칸씩 미루고 Index 0 에 1을 삽입한다면 가능하다.
선택정렬의 시간 / 공간복잡도는 아래와 같다.
| 알고리즘 | 시간복잡도(최상) | 시간복잡도(평균) | 시간복잡도(최악) | 공간복잡도 |
| 선택 정렬 | O(n^2) | O(n^2) | O(n^2) | O(1) |
선택 정렬은 최상의 경우에도 O(n^2) 수준이기는 한데, 일반적으로 버블 정렬보다 좋은 결과를 가져오기는 한다.
선택 정렬 코드는 아래와 같다. 이번에도 애니메이션과는 달리 최대값을 찾아서 끝으로 옮김(반대 방식은 직접 만들어보길 권장)
package com.test;
public class SelectionSort {
public static void main(String args[]){
int[] array = {20, 35, -15, 7, 55, 1, -22};
for(int unsortedIndex = array.length-1; unsortedIndex > 0; unsortedIndex--){
// 가장 큰 값을 갖는 Index를 0으로 초기화
int largest = 0;
// 0은 이미 largest에 저장되어 있으니 1부터 시작해서 미정렬 상태 Partition 중
// 가장 큰 값을 갖는 Index를 찾는다.
for(int j=1; j <= unsortedIndex; j++){
if(array[largest] < array[j]){
largest = j;
}
}
swap(array, largest, unsortedIndex);
}
for(int i=0; i < array.length; i++){
if(i == array.length-1){
System.out.print(array[i]);
} else {
System.out.print(array[i] + ", ");
}
}
}
private static void swap(int[] array, int largest, int unsortedIndex){
if(largest == unsortedIndex){
return;
}
int temp = array[largest];
array[largest] = array[unsortedIndex];
array[unsortedIndex] = temp;
}
}
3. Insertion sort(삽입 정렬)
이번에도 애니메이션부터 보도록 하자.
정렬되지 않은 부분의 인덱스 위치의 값을 그 이전에 정렬된 부분의 인덱스 내에 있는 값들과 비교하여 적절한 위치를 찾을 때까지 정렬된 부분의 값들을 한 칸씩 이동시키고 빈 자리를 찾아 삽입시키는 과정으로 진행된다.
삽입 정렬의 특징은 다음과 같다.
| 특성 | 설명 |
| In-place 알고리즘 | Memory 상에서 필요 시 상호 위치만 변경될 뿐 추가적인 배열 생성이 불 필요함 |
| Stable 알고리즘 | 구현하기 나름이나, 기본적으로 값이 같으면 정렬 순서를 바꾸지 않는다. |
삽입 정렬의 시간 / 공간 복잡도는 아래와 같다.
| 알고리즘 | 시간복잡도(최상) | 시간복잡도(평균) | 시간복잡도(최악) | 공간복잡도 |
| 버블 정렬 | O(n) | O(n^2) | O(n^2) | O(1) |
삽입 정렬의 코드는 다음과 같다. (애니메이션과 동일하게 구현)
package com.test;
public class InsertionSort {
public static void main(String[] args){
int intArray[] = {20, 35, -15, 7, 55, 1, -22};
for(int firstUnsortedIndex = 1; firstUnsortedIndex < intArray.length; firstUnsortedIndex++){
int toBeInserted = intArray[firstUnsortedIndex];
int i;
// 삽입할 값보다 그 이전의 값들이 더 크면 뒤로 미루어야 한다.
for(i=firstUnsortedIndex; i > 0 && intArray[i-1] > toBeInserted; i--){
intArray[i] = intArray[i-1];
}
// 현재 값이 삽입될 위치를 찾았으니 삽입
intArray[i] = toBeInserted;
}
for(int i=0; i < intArray.length; i++){
System.out.print(intArray[i] + ", ");
}
}
}
이번 포스팅에서 설명한 정렬 방식들은 가장 기본적인 수준의 정렬 방식들이다. 그러나 일반적으로 좋은 성능을 낼 수 없기 때문에 실제로 개발 시에는 사용하지 않는 것이 좋다.
실제 사용되는 정렬 방식은 이후에 포스팅할 Merge / Quick 정렬 등을 사용하는 것이 좋다.
오류가 있는 부분은 댓글로 남겨주시면 반영하겠습니다. 감사합니다.
'자바 프로그래밍 > 자료구조(Data Structure)' 카테고리의 다른 글
| 자료구조 - 정렬 3 (Merge) (0) | 2020.11.09 |
|---|---|
| 자료구조 - 정렬 2 (Shell) (0) | 2020.11.09 |
| 자료구조 - 정렬 (개요) (0) | 2020.11.06 |
| 자료구조 - 세그먼트 트리(Segment Tree)2 - 느린 전파 (0) | 2020.11.02 |
| 자료구조 - 트라이(Trie) (6) | 2020.10.25 |
