https://www.boostcourse.org/cs204
자료구조 강의를 듣고 정리한 내용입니다
*강의 후반부에서 다루는 알고리즘에 대한 내용을 정리한 글입니다
알고리즘과 관련된 선수지식
> 리스트에 있는 데이터를 정렬할 때, 어떻게 정렬을 할 것인지 고려해야 한다
Out-of-place 정렬
데이터 구조의 복사본을 만든 후 정렬하는 방법이다 //용량이 늘어난다
in-place 정렬
내부에서 데이터 구조들의 위치를 바꾸어 정렬하는 방법이다
> 리스트에 중복된 요소가 있는지 체크해야한다
안정 정렬 : 중복된 숫자가 원래 순서를 유지한 상태로 정렬하는 방법이다
-> 순차적이고, 규칙적이다
불안정 정렬 : 중복된 숫자의 순서를 보장할 수 없다
-> 비 순차적, 불규칙적이다
> 해당 정렬 알고리즘을 썼을때 걸리는 시간을 체크해야 한다
시간 복잡도
최악의 경우, 평균적인 경우, 최선의 경우의 복잡도가 존재한다
최악 : 정렬 전 요소들이 큰 수에서 작은 수로 있는 경우를 의미한다
최선 : 이미 정렬되어 있는 경우를 의미한다
평균 : 완전히 임의의 순서로 되어있는 리스트를 정렬하는 경우를 의미한다
시간복잡도는 Big O(빅 오) 표기법으로 표기하며,
O(1) -> O(log n) -> O(n) -> O(n logn) -> O(n^2) 의 순서대로 오래걸린다
//n^2는 n의 2제곱이라는 의미이다
정렬 알고리즘
1. 선택정렬
리스트의 가장 작은 수를 순서가 확정되지 않은 부분의 가장 앞 칸의 수와 바꾸는 것이다
10 7 8 6 3 의 숫자가 있는 경우
3 > 10과 변경, 6 > 7과 변경하는 식의 정렬이다
-> 리스트의 안에서 순서를 교환하는 in place 정렬이며 최선, 최악, 평균의 시간 복잡도 모두 O(n^2)이다
2. 삽입 정렬
여러 요소로 이루어진 리스트에서 요소를 꺼낸 후 다른 모든 요소들과 비교한다
비교한 수보다 작으면 두 수의 위치를 교환한다
하나의 요소를 꺼내서 앞에 있는 요소들과 비교하기 때문에 최악, 평균 시간복잡도는 O(n^2)이다
최선의 복잡도는 O(n)이다 //수를 꺼내서 하나씩 비교하기 때문
-> 안정 정렬이며, in-place 정렬이다
**삽입 정렬은 잘 정렬된 데이터베이스에 요소를 추가할 때 자주 사용한다
이 경우 이미 정렬된 부분은 다시 정렬할 필요가 없기 때문에 시간복잡도는 O(n)이 된다
삽입 정렬의 코드
for(int i = 1; i < array.length; i++) {
int j, v = array[i];
for(j = i-1; i>= 0; j--) {
if(array[i] <= v)
break;
array[j+1] = array[i]; //처음 j가 i-1이었기 때문에 j+1를 넣은 식을 사용가능하다
}
array[j+1] = v; //요소를 v에 복사해서 넣는다
}
3. 셀 정렬
양 끝에서 요소를 가져와서 그 둘을 바꾸는 정렬방식이다
항상 같은 간격을 가지고 비교할 두 수를 고른다
큰 간격으로 수를 바꾸다가 점점 작은 간격으로 바꾸며, 간격의 넓이가 1이되면 삽입정렬을 한다
-> 작은 값을 가진 요소는 오른쪽에서 왼쪽으로 옮기고 큰 값을 가진 요소는 왼쪽에서 오른쪽으로 옮기는 알고리즘이다
최악의 시간 복잡도 : O(n^2) 평균적인 복잡도는 간격의 크기에 따라 달라진다
-> 중복된 숫자의 순서가 보장되지 않는 불안정 정렬이고, in-place 정렬이다
4. 합병정렬
숫자로 이루어진 리스트를 정렬할 때 숫자의 반을 나눠 정렬한다
하나만 남을 때까지 계속해서 반을 나누고,
나눈 리스트를 대소 관계에 맞춰 하나의 리스트로 합친다
-> 중복된 숫자의 순서가 유지되는 안정 정렬이며, out-of-place 정렬이다
평균적인 시간 복잡도는 O(n logn)이다
합병정렬의 코드
int[] array, temp; //두 개의 정수 배열
public mergeSort(int[] array) {
this.array = array;
temp = new int[array.length]; //빈 배열을 만들어 데이터가 정렬되면 이를 저장
split(0, array.length -1);
}
//리스트가 1개 남을 때까지 나눈다
private void split(int low, int high) {
if(low == high) return;
int mid = (high + low)/2;
split(low, mid);
split(mid + 1, high); //같은 인덱스를 2번 사용하면 안되기 때문
merge(low, mid, high) ;
}
//대소 비교 후 순서에 맞게 나열
public void merge(int low, int mid, int high) {
int i = low, j = mid + 1, tempposn = low;
//나눈 리스트의 대소 비교와 정렬
while(i<= mid && j <= high) {
if(array[i] <= array[j])
temp[tempposn++] = array[i++]; //임시배열
else
temp[tempposn++] = array[j++];
}
//i가 mid, j가 high로 갈 때까지 반복한다
while(i <= mid) temp[tempposn++] = array[i++]; //배열끝까지 이동
while(j <= high) temp[tempposn++] = array[j++];
//원래 배열에 복사
for(tempposn = low; tempposn <= high; tempposn ++)
array[tempposn] = temp[tempposn];
}
**5. 퀵 정렬**
리스트의 중간값인 중심점(Pivot Point)을 하나 잡는다
중심점보다 작은 수와 큰 수로 나눈다
반으로 나눠진 왼쪽과 오른쪽 리스트에서 각각 중심점을 지정해 비교하여 정렬한다
**중심점의 왼쪽에 있는 숫자들은 오른쪽 숫자와 비교할 필요가 없다
시간 복잡도는 O(log n)이다
퀵 정렬 알고리즘은 Java의 sort메서드에서 사용하며 모든 종류의 변수에 대해 사용 가능하다
- 퀵 정렬 최악의 케이스
평균적인 상황에서의 시간 복잡도는 O(log n)이지만, 최소인 지점을 중심점으로 잡아
모든 숫자가 중심점보다 커서 대소비교만 하고 분류가 되지 않는 상황에는
O(n^2)까지 늘어날 수 있다
퀵 정렬의 코드
public class QuickSort<E> {
E[] array;
public E[] sort(E[] array) {
this.array = array;
quicksort(0, array.length-1)
return array
}
public void swap(int from, int to) { //위치를 바꾸는 함수
E tmp = array[from];
array[from] = array[to];
array[to] = tmp;
}
public void quicksort(int from, int to) { //퀵 정렬 메서드
if(from >= to) return; //참인경우 리스트에 요소가 1개
E value = array[to]; //중심점으로 배열의 마지막 숫자 선택
int counter = from; //배열의 가장 앞까지 탐색
//배열 탐색
for(int i = from; i<to; i++) { //pivot의 값은 탐색하지 않는다
if(((Comparable<E>) array[i].compareTo(value) <= 0) {
swap(i, counter);
counter++;
}
}
-> Pivot 앞 까지의 리스트를 탐색하는 코드
Pivot보다 작으면 리스트의 앞으로 이동하고 동일하면 그대로 둔다
swap(counter, to); //중심점이 중간에 오게 한다
//배열의 왼쪽과 오른쪽을 정렬, 카운터의 위치는 옮길 필요없다
quicksort(from, counter-1);
quicksort(counter+1, to);
}
6. 기수정렬 (Radix)
우편번호, 자릿수 등의 기준을 만들어 기준에 따라 숫자를 분류하여 정렬하는 방법이다
이론적으로 빠른 정렬 방법이지만, 숫자를 복사하는 과정이 많아 수행속도가 느리다
-> 컴퓨터에서 사용하는것은 어렵다 일상생활에서 기계적으로 정렬할 때 많이 사용된다.(우편물을 정리하는 기계)