티스토리 뷰
1. 정렬이란?
정렬은 이름, 학번, 키 등 핵심 항목의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말한다. 이렇게 정렬하면 검색을 더 쉽게 할 수 있다. (파일을 알파벳 순으로 정렬하고 찾으면 더 찾기 쉬운것 처럼)
또한 정렬시에 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는것을 안정된 정렬이라고 하고, 안정되지 않은 알고리즘을 사용하면 같은 키를 가진 요소의 순서가 정렬 전후에 유지 되지 않는다.
2. 외부 정렬과 내부 정렬
(1) 내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장 할 수 있는 경우에 사용하는 알고리즘
(2) 외부 정렬 : 정렬할 데이터가 너무 많아 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘
3. 버블 정렬 (Bubble Sort)
버블 정렬은 가장 직관적인 정렬 방법으로서 옆에 있는 값과 비교해 더 작은값을 앞으로 보내는 방법이다.
구현하기에는 가장 쉽지만 가장 비효율적인 방법이다.
시간복잡도는 O(N^2).
구현하면 다음과 같다.
import java.util.Arrays;
class BubbleSort1 {
static void swap(int[] a, int index1, int index2) {
int temp = a[index1];
a[index1] = a[index2];
a[index2] = temp;
}
// bubble sort
// 끝에서 부터 정렬
static void bubbleSort(int[] a, int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = n - 1; j > i; j--) {
if (a[j - 1] > a[j]) {
swap(a, j - 1, j);
}
}
}
}
// 처음 부터 정렬. 큰 값을 뒤로 보낸다.
static void bubbleSort1(int[] a, int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) swap(a, j, j + 1);
}
}
}
}
4. 단순 선택 정렬 (straight selection sort)
단순 선택 정렬은 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 이다.
가장 작은 값을 선택해서 제일 앞으로 보내는 아주 단순한 알고리즘이다. 직관적이고 구현하기 쉽다.
index가 n-1까지 돌면서 가장 작은것 찾은 다음 맨 앞의 값과 swap 시켜 주면 된다.
시간 복잡도는 마찬가지로 O(N^2)
import java.util.Arrays;
class SelectionSort1 {
static void swap(int[] a, int index1, int index2) {
int temp = a[index1];
a[index1] = a[index2];
a[index2] = temp;
}
static void selectionSort(int[] arr, int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min]) min = j;
}
swap(arr, i, min);
}
}
}
5. 단순 삽입정렬 (straight insertion sort)
단순 삽입 정렬은 선택한 요소를 그보다 더 앞쪽에 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘입니다.
앞에 있는 요소들이 이미 정렬되어 있다고 가정하고, 어디에 들어갈지 결정하는 것이다.
버블정렬과 선택정렬에 비해서 더 효율적인데, 정렬할때 앞까지는 이미 정렬이 되어 있고, 필요할때만 연산을 통해서 이동하는 것이기 때문에 연산자체가 더 작다.
하지만 시간복잡도는 O(N^2)로 동일하다.
import java.util.Arrays;
class InsertionSort1 {
//내풀이
static void insertionSort(int[] arr, int n) {
for (int i = 1; i < n; i++) {
int num = arr[i];
int j;
for (j = i - 1; j >= 0; j--) {
if (num < arr[j]) arr[j + 1] = arr[j];
else break;
}
arr[j + 1] = num;
}
}
//책풀이
static void insertionSort1(int[] arr, int n) {
for (int i = 1; i < n; i++) {
int num = arr[i];
int j;
for (j = i; j > 0 && arr[j - 1] > num; j--) {
arr[j] = arr[j - 1];
}
arr[j] = num;
}
}
// 또 다른 풀이
static void insertionSort2(int[] arr, int n) {
for (int i = 0; i < n-1; i++) {
int j = i;
while (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
j--;
}
}
}
}
거의 정렬된 상태인 경우에는 삽입정렬이 빠르다. 왜냐하면 swap하는 수가 줄어든다.
Reference :
Do it! 자료구조와 함께 배우는 알고리즘 입문 (이지스 퍼블리싱)
https://www.youtube.com/watch?v=16I9Z7bS1iM&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=4 (실전 알고리즘 강좌)
'Programming > Data Structures & Algorithms' 카테고리의 다른 글
그래프(Graph) (0) | 2022.09.23 |
---|---|
검색 (선형검색, 이진검색) (0) | 2022.09.17 |
Stack과 Queue (0) | 2022.07.26 |
이번주 코테문제 풀면서 배운것 3 (0) | 2022.07.19 |
이번주 코테문제 풀면서 배운것 2 (0) | 2022.07.17 |
- Total
- Today
- Yesterday