안전 정렬 : 동일한 값에 기존 순서가 유지 (버블, 삽입)
불안정 정렬 : 동일한 값에 기존 순서가 유지X (선택,퀵)
📌선택정렬
선택정렬(Selection Sort)은 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 그 위치에 어떤 원소를 넣을지 선택하는 알고리즘입니다. 선택정렬(Selection Sort)와 삽입정렬(Insertion Sort)이 종종 헷갈릴 수 있는데,
선택정렬은 배열에서 해당 자리를 이미 선택하고 그 자리에 오는 값을 찾는 것이며,
삽입정렬은 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 것입니다.
- 선택정렬은 제자리 정렬(in-place sorting) 알고리즘의 하나
제자리 정렬이란, 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법이며
해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
- 선택정렬의 과정
- 주어진 배열 중에 최소값을 찾습니다.
- 그 값을 맨 앞에 위치한 값과 교체합니다. (pass)
- 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체합니다.
- 하나의 원소만 남을 때까지 위의 1~3 과정을 반복합니다.
https://github.com/GimunLee]">gif로 보는 선택정렬 [출처 : https://github.com/GimunLee]
배열에 있는 정수값 오름차순 정렬하기 (선택정렬)
import java.util.Arrays;
// 선택 정렬
public class SelectionSort {
public static void main(String[] args) {
int[] number = {15,3,23,64,77,46,42,174,68,78,91,5,76,310,84,342,176,120,33,41};
// swap 할 공간
int temp;
for (int i = 0; i < number.length-1; i++) { // 1
int indexMin = i;
for (int j = i+1; j < number.length; j++) { // 2
// > 내림차순, < 오름차순
if(number[j] < number[indexMin]) { // 3
indexMin = j;
}
}
// 4
temp = number[indexMin];
number[indexMin] = number[i];
number[i] = temp;
}
System.out.println(Arrays.toString(number));
}
}
📌Java Code (오름차순 조건)
- 우선, 위치(index)를 선택해 줍니다.
- i+1번째 원소부터 선택한 위치(index)의 값과 비교를 시작합니다.
- 오름차순이므로 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, 위치(index)를 갱신
- 2번 반복문이 끝난 뒤에는 indexMin에 '1'번에서 선택ㄹ한 위치(index)에 들어가야 하는 값의 위치를 갖고 있으므로 SWAP 처리
💡 선택정렬의 장점
- 거품정렬(Bubble sort)과 마찬가지로 알고리즘이 단순합니다.
- 정렬을 위한 비교 횟수는 많지만, 거품정렬(Bubble Sort)에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적입니다.
- 거품정렬(Bubble Sort)와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식(제자리 정렬, In-place Sort)이므로, 다른 메모리 공간을 필요로 하지 않습니다.
💡 선택정렬의 단점
- 시간복잡도가 O(n^2)으로, 비효율적입니다.
- 불안정 정렬(Unstable Sort) 입니다.
📌 버블정렬
버블정렬은 배열내의 두개의 인접한 Index를 비교하여 더 큰 숫자를 뒤로 보내 차곡차곡 쌓아 정렬하는 방법입니다. 결론적으로 말하자면 배열의 뒷쪽부터 정렬하는 방법이라고 생각하시면 될 듯 합니다.
첫번째 FOR문
① for문에서 [0]번째 Index와 [1]번째의 Index값을 비교하여 더 큰 숫자를 뒤로 보내줍니다.
② for문에서도 마찬가지로 [1]번째 [2]번째의 Index값을 비교하여 더 큰 숫자를 뒤로 보내주죠.
이런식으로 ④번처럼 배열의 끝까지 정렬을 다 했으면 다시 배열의 처음으로 돌아와
정렬이 완료될때까지 반복하는것이 버블정렬입니다.
배열에 있는 정수값 오름차순 정렬하기 (버블정렬)
// 버블 정렬
public class BubleSort {
public static void main(String[] args) {
int[] number = {11,234,23,4,1,5,6,2,65,764,825,46,72,47,26,69,793,25,498,245};
for (int i = 0; i < number.length; i++) { //1
for (int j = 0; j < number.length -i -1; j++) { //2
// < 내림차순, > 오름차순
if(number[j] > number[j+1]) { //3
int temp = number[j+1];
number[j+1] = number[j];
number[j] = temp;
}
}
}
System.out.println(Arrays.toString(number));
}
}📌Java Code (오름차순 조건)
- 우선, 위치(index)를 선택해 줍니다.
- i+1번째 원소부터 선택한 위치(index)의 값과 비교를 시작합니다.
- 오름차순이므로 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, 위치(index)를 갱신
- 2번 반복문이 끝난 뒤에는 indexMin에 '1'번에서 선택ㄹ한 위치(index)에 들어가야 하는 값의 위치를 갖고 있으므로 SWAP 처리
시간복잡도
시간복잡도를 계산하면, (n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2이므로, O(n^2) 입니다. 또한, Bubble Sort는 정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(n^2) 으로 동일합니다. (개선된 Bubble Sort가 존재하긴 하나, 이번 장은 기초를 다지기 위한 학습이므로 넘어가겠습니다.)
공간복잡도
주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 입니다.
💡 버블정렬의 장점
- 구현이 매우 간단하고, 소스코드가 직관적입니다.
- 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다. => 제자리 정렬(in-place sorting)
- 안정 정렬(Stable Sort) 입니다.
💡 버블정렬의 단점
- 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적입니다.
- 정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 됩니다.
📌삽입정렬
삽입정렬은 기준이 되는 숫자와 그 앞에있는 숫자를 비교하여 조건에 맞게 정렬을 하는 방법입니다.
0번째 인덱스는 앞쪽에있는 숫자가 없기 때문에 정렬의 시작은 1번째 인덱스로 시작을 합니다.
GIF로 이해하는 Insertion Sort
배열에 있는 알파벳 오름차순 정렬하기 (삽입정렬)
import java.util.Arrays;
import java.util.LinkedList;
// 삽입 정렬
public class InsertSort {
public static void main(String[] args) {
char[] str = {'C','A','D','G','F','E','B'};
// 배열로 구현
// for (int i = 0; i < str.length; i++) {
// for (int j = i; j > 0; j--) {
// // < 내림차순, > 오름차순
// if(str[j-1] > str[j]) {
// char temp = str[j-1];
// str[j-1] = str[j];
// str[j] = temp;
// }
// }
// }
// System.out.println(Arrays.toString(str));
// 리스트로 구현 (가변적이고 좋음)
LinkedList<Character> list = new LinkedList<>();
for (char c : str) {
list.add(c);
}
for (int i = 0; i < list.size(); i++) {
for (int j = i; j < list.size(); j++) {
if(list.get(i) > list.get(j)) {
Character temp = list.remove(j);
list.add(i, temp);
}
}
}
System.out.println(list);
}
}시간복잡도
최악의 경우(역으로 정렬되어 있을 경우) Selection Sort와 마찬가지로, (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 즉, O(n^2) 입니다.
하지만, 모두 정렬이 되어있는 경우(Optimal)한 경우, 한번씩 밖에 비교를 안하므로 O(n) 의 시간복잡도를 가지게 됩니다. 또한, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는, 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문입니다.
최선의 경우는 O(n) 의 시간복잡도를 갖고, 평균과 최악의 경우 O(n^2) 의 시간복잡도를 갖게 됩니다.
공간복잡도
주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 입니다.
💡 삽입정렬의 장점
- 알고리즘이 단순합니다.
- 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있습니다.
- 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다. => 제자리 정렬(in-place sorting)
- 안정 정렬(Stable Sort) 입니다.
- Selection Sort나 Bubble Sort과 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠릅니다.
💡 삽입정렬의 단점
- 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적입니다.
- Bubble Sort와 Selection Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적입니다.
정리하기
💡정렬알고리즘의 시간복잡도 비교
- 단순(구현 간단)하지만 비효율적인 방법 : 삽입 정렬, 선택 정렬, 버블 정렬
- 복잡하지만 효율적인 방법 : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬
출처: https://devuna.tistory.com/28 [튜나 개발일기]
출처: coding-factory.tistory.com/133 [코딩팩토리]
'알고리즘 문제 풀이' 카테고리의 다른 글
| [LeetCode] Java 448. Find All Numbers Disappeared in an Array (0) | 2021.05.09 |
|---|---|
| [Algorithm] 힙 정렬 (0) | 2021.04.15 |
| [Algorithm] 퀵 정렬 / 병합(합병) 정렬 (0) | 2021.04.15 |
| [Algorithm] 알고리즘 시간복잡도에 대하여 (0) | 2021.04.15 |
