정렬 알고리즘
정렬: 데이터들을 특정한 값에 따라 정해진 순서대로 나열하는 것
수많은 데이터들을 효율적으로 탐색하기 위해서는 데이터들이 순서대로 정렬되어있어야 한다.
기본적인 정렬 알고리즘으로 버블정렬, 삽입정렬, 선택정렬 등이 있다.
Bubble Sort (버블 정렬)
- 배열을 순회하면서 인접한 두개의 데이터를 비교하고 교환하는 정렬 방법이다.
void bubble_sort(int[] arr) {
for(int i = arr.length-1; i > 0; i--) {
for(int j = 0; j < i; j++) {
if(arr[j] > arr[j+1]) {
//swap
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}- 배열의 j번째(시작은 0) 값과 그 다음 값을 비교하고 순서에 맞게 교환한다.
- j를 1 증가시키며 i까지 과정 1을 반복한다.
- 1~2를 반복하되 한 사이클이 끝나면 i를 1 감소시켜 비교 범위를 점점 좁힌다. (가장 큰 값이 제일 뒤로 가기 때문에)
장점
- 개념이 단순하다.
제자리 정렬이다.안정 정렬이다.
제자리 정렬: 배열 이외에 추가 메모리를 요구하지 않는 정렬 방법
안정 정렬: 동일한 값을 가진 데이터의 순서가 유지되는 정렬 방법
단점
- 시간복잡도가 최선의 경우도 O(n^2)로 매우 비효율적이다.
- 배열의 길이가 길어질 수록 비효율적이다.
- 교환이 많이 일어난다.
Insertion Sort (삽입 정렬)
- 정렬 범위를 1칸씩 확장하면서 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리에 삽입하는 방법이다.
void insertion_sort(int[] arr) {
for(int i = 0; i < arr.length; i++) {
for(int j = i; j > 0; j--) {
if(arr[j] < arr[j-1]) {
//swap
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}- 배열의 i번째 (시작은 0) 값을 선택한다.
- 선택한 원소의 왼쪽(이미 정렬된 부분)으로 끝까지 차례대로 돌면서 더 큰 값이 나오면 교환한다.
- 배열의 마지막까지 i를 1씩 증가시키며 1~2를 반복한다.
장점
- 이미 정렬되어 있는 경우 시간복잡도가 O(n)으로 효율적이다.
제자리 정렬이다.안정 정렬이다.
단점
- 배열의 길이가 길어질 수록 비효율적이다.
- 평균 시간복잡도가 O(n^2)로 비효율적이다.
Selection Sort (선택 정렬)
- 배열에서 위치를 선택하고 그 위치에 들어갈 값을 찾아 교환하는 방법이다.
void selection_sort(int[] arr) {
for(int i = 0; i < arr.length-1; i++) {
int min_index = i;
for(int j = i+1; j < arr.length; j++) {
if(arr[j] < arr[min_index])
min_index = j;
}
//swap
int temp = arr[min_index];
arr[min_index] = arr[i];
arr[i] = temp;
}
}- 배열의 i번째 (시작은 0) 값을 선택한다.
- 선택한 위치의 값을 최소값으로 둔다.
- 바로 다음(i+1)부터 배열의 마지막까지 차례대로 돌면서 최소값을 갱신한다.
- i번째 값과 최소값을 교환한다 (위치를 바꾼다).
- i가 배열의 크기 - 1이 될 때 까지 i를 1 증가시키고 1~4를 반복한다.
장점
제자리 정렬이다.- 비교 횟수는 많지만 교환 횟수가 적기 때문에 교환이 많이 필요한 상태에서 비교적 효율적이다.
단점
불안정 정렬(Unstable Sort) 이다.- 배열의 길이가 길어질 수록 비효율적이다.
- 시간복잡도가 O(n^2)로 비효율적이다.
불안정 정렬: 동일한 값을 가진 데이터의 순서가 유지되지 않는 정렬 방법
시간복잡도, Runtime 비교
