[Algorithm - Java] 알고리즘에서 중요한 정렬의 종류 (버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬)
[Algorithm - Java] 알고리즘에서 중요한 정렬의 종류
(버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬)
코드를 구현하다보면, 어떠한 값을 산출하기 위해서 계산을 해야됩니다. 그런데, 계산을 하다보면, 무식하게 작성을 한 코드를 보면서, '지금까지 뭐한걸까?' 라는 생각과 함께, 제가 짠 코드도 뭐가 어떻게 구현한건지 몰라 해매는 경우가 많았습니다. 물론.. 지금도 그렇구요;;; 그리고 다른 고수분들께서 문제를 풀어 작성한 코드를 보면, '와.. 이렇게 코드줄을 짧게도 결과를 만들어낼수 있구나!'라는 생각을 많이 하게 되었습니다. 그래서 코드를 구현하는 방법을 개선하기 위해 공부를 하고 있는것중 하나! 바로 '정렬'에 대한 주제로 포스팅을 해보기로 했습니다.
▶ 정렬이란?
데이터를 순서대로 나열하는 방법을 의미하며, 알고리즘의 중요한 주제라 볼 수 있습니다. 어떠한 정렬방법을 선택하느냐에 따라 '시간 복잡도'가 얼마나 걸릴지 정해지는데요. 정렬하는 방법이 어떤것이 있는지 알아보겠습니다.
▶ 버블 정렬 ◀
버블 정렬은 가장 쉬운 정렬로, 첫 번째와 두 번째, 두 번째와 세 번째... 식으로 마지막자료(n-1)까지 비교하며, 교환하는 방식입니다. 그림으로 표현하면 아래와 같습니다.
코드로 예를 들어보죠.
int[] arr = {7,4,2,5,1};
int count = 0;
int len = arr.length;
while(count != arr.length-1) {
for (int i = 1; i < len; i++) {
if (arr[i-1] > arr[i]) {
int tmp = arr[i-1] ;
arr[i-1] = arr[i];
arr[i] = tmp;
}
System.out.println("after arr[i-1] : " + arr[i-1]);
}
count++;
len--;
System.out.println("count = " + count);
}
// 결과 : arr = [1,2,4,5,7]
after arr[i-1] : 4
after arr[i-1] : 2
after arr[i-1] : 5
after arr[i-1] : 1
count = 1
after arr[i-1] : 2
after arr[i-1] : 4
after arr[i-1] : 1
count = 2
after arr[i-1] : 2
after arr[i-1] : 1
count = 3
after arr[i-1] : 1
count = 4arr의 index(i-1)의 값이 다음 인덱스 안의 값보다 클 경우, 두 숫자의 위치를 바꾸도록 코드를 구현했습니다. for문을 한번 돌때면, 해당 배열의 맨 뒤의 값이 배열의 가장 큰 값이다보니, 배열의 길이를 하나를 줄여서 다시 for문으로 탐색하도록 만들었습니다. 이렇게 반복을 하다보면, 배열이 정렬된 모습을 볼 수는 있습니다.
시간 복잡도 : O(n) = n^2
▶ 선택 정렬 ◀
말 그대로 선택을 해서 조건에 따른 정렬을 해준다라고 생각하면 됩니다. 예를 들어 [5,3,6,2,1]이라는 정렬되지 않는 배열에서 맨 앞의 수와 배열안의 가장 작은수를 찾아 바꾸게 될껍니다. 그러면 결과는 이렇게 되겠죠?
선택정렬전 : [5,3,6,2,1]
선택정렬후 : [1,3,6,2,5]
그리고 맨 앞의 인덱스는 완료되었으므로, 더 이상 신경쓸필요가 없으며, 다음 인덱스의 값과 나머지 인덱스안에서의 최소값과 비교를 해서 바꿔줍니다. 코드로 구성하면 다음과 같습니다.
int[] arr = {5,3,6,2,1};
for (int i = 0; i < arr.length; i++) {
for (int j = i; j < arr.length; j++) {
if (arr[i] > arr[j]) {
System.out.println("before arr[i] = " + arr[i]);
System.out.println("before arr[j] = " + arr[j]);
int tmp = arr[i] ;
arr[i] = arr[j];
arr[j] = tmp;
System.out.println("after arr[i] : " + arr[i]);
System.out.println("after arr[j] : " + arr[j]);
System.out.println("==============================");
}
}
}
// 결과 : [1,2,3,5,6]
before arr[i] = 5
before arr[j] = 3
after arr[i] : 3
after arr[j] : 5
==============================
before arr[i] = 3
before arr[j] = 2
after arr[i] : 2
after arr[j] : 3
==============================
before arr[i] = 2
before arr[j] = 1
after arr[i] : 1
after arr[j] : 2
==============================
before arr[i] = 5
before arr[j] = 3
after arr[i] : 3
after arr[j] : 5
==============================
before arr[i] = 3
before arr[j] = 2
after arr[i] : 2
after arr[j] : 3
==============================
before arr[i] = 6
before arr[j] = 5
after arr[i] : 5
after arr[j] : 6
==============================
before arr[i] = 5
before arr[j] = 3
after arr[i] : 3
after arr[j] : 5
==============================
before arr[i] = 6
before arr[j] = 5
after arr[i] : 5
after arr[j] : 6
==============================앞에서 설명했듯이 선택한 인덱스의 값과 해당 인덱스의 뒤에 값들중 최소값을 찾아 비교를 해서 조건이 맞을경우 숫자 위치를 바꿔서 정렬을 하는 방법입니다.
시간 복잡도 : O(n) = n^2
▶ 삽입 정렬 ◀
삽입정렬은 배열의 맨 앞값과 다음값과 비교를 해 정렬을 한번 한 다음, 다음 값을 가져와서 뒤에서부터 앞의값들을 비교해 정렬을 진행합니다. 규칙을 보면 버블정렬하고 비슷한데요. 버블 정렬은 앞에서 뒤로 진행했다면, 삽입 정렬은 뒤에서 앞으로 진행한다고 생각하면 됩니다. 단, 배열의 맨 뒤부터 조회를 하는것이 아닌, 배열의 길이가 2,3,4,5... 씩 증가하면서 조회를 한다고 생각할 수 있습니다. 예시를 보죠.
배열 : [4,6,2,9,1]
첫번째 비교 : [4,6] - 앞의 값이 작으므로, 변화없이 진행을 합니다.
두번째 비교 : [4,6,2]
> [6,2] 중 2의 값이 작으므로, 2를 앞으로 보냅니다.
> [4,2] 중 2의 값이 작으므로, 2를 앞으로 보냅니다.
두번째 비교 결과물 : [2,4,6]
...
이런 방식으로 쭉 진행이 되면서 정렬이 됩니다. 그러면 코드로 한번 구현을 해보겠습니다.
int[] arr = {4,6,2,9,1};
int insertion_sort_size = 1;
while (insertion_sort_size != arr.length) {
for (int i = insertion_sort_size; i > 0; i--) {
System.out.println("insertion_sort_size = " + insertion_sort_size);
if(arr[i] < arr[i-1]) {
System.out.println("before arr[i-1] = " + arr[i-1] + " | i-1 = " + (i-1));
System.out.println("before arr[i] = " + arr[i] + " | i = " + i);
int tmp = arr[i-1];
arr[i-1] = arr[i];
arr[i] = tmp;
System.out.println("after arr[i-1] = " + arr[i-1] + " | i-1 = " + (i-1));
System.out.println("after arr[i] = " + arr[i] + " | i = " + i);
System.out.println("==================================");
} else {
System.out.println("Do not change!");
System.out.println("i = "+i);
System.out.println("==================================");
break;
}
}
insertion_sort_size++;
}
// 결과 : [1,2,4,6,9]
insertion_sort_size = 1
Do not change!
i = 1
==================================
insertion_sort_size = 2
before arr[i-1] = 6 | i-1 = 1
before arr[i] = 2 | i = 2
after arr[i-1] = 2 | i-1 = 1
after arr[i] = 6 | i = 2
==================================
insertion_sort_size = 2
before arr[i-1] = 4 | i-1 = 0
before arr[i] = 2 | i = 1
after arr[i-1] = 2 | i-1 = 0
after arr[i] = 4 | i = 1
==================================
insertion_sort_size = 3
Do not change!
i = 3
==================================
insertion_sort_size = 4
before arr[i-1] = 9 | i-1 = 3
before arr[i] = 1 | i = 4
after arr[i-1] = 1 | i-1 = 3
after arr[i] = 9 | i = 4
==================================
insertion_sort_size = 4
before arr[i-1] = 6 | i-1 = 2
before arr[i] = 1 | i = 3
after arr[i-1] = 1 | i-1 = 2
after arr[i] = 6 | i = 3
==================================
insertion_sort_size = 4
before arr[i-1] = 4 | i-1 = 1
before arr[i] = 1 | i = 2
after arr[i-1] = 1 | i-1 = 1
after arr[i] = 4 | i = 2
==================================
insertion_sort_size = 4
before arr[i-1] = 2 | i-1 = 0
before arr[i] = 1 | i = 1
after arr[i-1] = 1 | i-1 = 0
after arr[i] = 2 | i = 1
==================================코드를 보면, for문이 버블 정렬과 다른걸 볼 수 있습니다. 버블 정렬은 인덱스 0 부터 시작을 했다면, 삽입 정렬은 배열의 앞의값 2자리만 먼저 분석을 한 다음, 다음 인덱수를 추가해 앞의 값들과 비교를 해야되기에, 인덱스는 1 부터 시작해, 0보다 큰 값일 동안 -1씩 감소시키면서 반복하는 조건을 제시했습니다. 어떻게 보면 코드가 더 햇갈릴수 있지만, 버블 정렬과 선택 정렬의 시간 복잡도랑 다르게 최선의 경우, 좀 더 개선된 모습을 볼 수 있습니다. 그 이유는 바로 코드 중간을 보면 'break;' 때문입니다. 이 방법은 값을 비교했을때 변경을 할 필요가 없다면, 그 앞의 값과 비교를 할 필요가 없기 떄문입니다. 그래서 선택 정렬이 시간 복잡도 부분에서 좀 개선이 되었다 볼 수 있습니다.
시간 복잡도 : [최악] - O(n) = n^2 , [최선의 경우] - Ω(N)
▶ 병합정렬 (merge) ◀
병합 정렬은 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘입니다. 쉽게 이야기하면, 두 개의 배열을 합쳐가면서 정렬하는 방법인데요. 일단 예시를 한번 보죠.
merge arr = []
arr1 = [1,3,4,5]
arr2 = [2,6,7,8]
첫번째 - arr1[0] 과 arr2[0]의 값을 비교하여, 작은값을 merge arr에 추가
merge arr = [1]
arr1 = [1,3,4,5]
arr2 = [2,6,7,8]
두번쨰 - arr1[1] 과 arr2[0]의 값을 비교하여, 작은값을 merge arr에 추가
merge arr = [1,2]
arr1 = [1,3,4,5]
arr2 = [2,6,7,8]
세번쨰 - arr1[1] 과 arr2[1]의 값을 비교하여, 작은값을 merge arr에 추가
...
이런식으로 쭉쭉 진행을 나가면서 양쪽 배열의 끝까지 진행을 해서 merge arr를 완성시키면 됩니다. 그러면 코드로 한번 구현을 해보겠습니다.
ArrayList<Integer> merge_arr = new ArrayList<>();
int[] arr1 = {1,3,4,5}; // 1 2 3
int[] arr2 = {2,6,7,8}; // 1
int arr1_count = 0;
int arr2_count = 0;
while (true) {
System.out.println("arr1_count = " + arr1_count);
System.out.println("arr2_count = " + arr2_count);
System.out.println("=====================================");
if (arr1[arr1_count] < arr2[arr2_count]) {
merge_arr.add(arr1[arr1_count]);
arr1_count++;
} else if (arr1[arr1_count] > arr2[arr2_count]) {
merge_arr.add(arr2[arr2_count]);
arr2_count++;
} else {
merge_arr.add(arr1[arr1_count]);
merge_arr.add(arr2[arr1_count]);
arr1_count++;
arr2_count++;
}
if (arr1_count == arr1.length) {
System.out.println("arr1_count finish. Include the remaining arr2 values.");
for (int i = arr2_count; i < arr2.length; i++) {
merge_arr.add(arr2[i]);
}
break;
} else if (arr2_count == arr2.length) {
System.out.println("arr2_count finish. Include the remaining arr1 values.");
for (int i = arr1_count; i < arr1.length; i++) {
merge_arr.add(arr1[i]);
}
break;
}
}
// 결과 : [1,2,3,4,5,6,7,8]
arr1_count = 0
arr2_count = 0
=====================================
arr1_count = 1
arr2_count = 0
=====================================
arr1_count = 1
arr2_count = 1
=====================================
arr1_count = 2
arr2_count = 1
=====================================
arr1_count = 3
arr2_count = 1
=====================================
arr1_count finish. Include the remaining arr2 values.코드를 보면 두 배열의 값의 맨 앞의 값을 먼저 비교한 다음, 작은값을 merge_sort 배열에 포함시키고 난 다음, 해당 배열의 count값을 증가시켜, 해당 배열의 다음값과 다시 비교를 해서 merge_sort 배열에 포함을 시켰습니다. 이렇게 반복을 하다가 한쪽의 배열의 값이 모두 포함이 된다면, 남아있는 배열의 값들을 다 포함시키면 정렬은 끝나게 됩니다.
시간 복잡도 : [최선의 경우] - O(n log n)
▶ 병합 정렬 [분할 정복] - mergeSort ◀
위에서 언급한 병합 정렬의 경우, 정렬되어있는 배열에서 값을 비교해 넣는 방법이였지만, 정렬이 안되어있는 배열이였다면, 정렬이 안되었을껍니다. 정렬이 안된 두개의 배열을 합치면서 정렬을 하고 싶다면, '분할 정복'의 개념을 적용하면 가능합니다.
★ 분할 정복
- 문제를 작은 2개의 문제로 분리, 각각 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 방법
◎ 예시
arr = [5, 3, 2, 1, 6, 8, 7, 4]
이 배열을 분할 정복의 개념을 활용하면
[5, 3, 2, 1] [6, 8, 7, 4] 로 2개의 배열로 쪼갠 다음,
[5, 3] [2, 1] [6, 8] [7, 4] 로 배열을 한번더 쪼갠 다음,
[5] [3] [2] [1] [6] [8] [7] [4] 로 배열이 쪼개지지 않을때 까지 진행을 합니다.
이렇게 분할 정복으로 진행을 한 다음, 위에서 배웠던 '병합 정렬'을 진행합니다.
[5] [3] [2] [1] [6] [8] [7] [4] 중 두 개씩 묶어서 비교를 합니다.
[5] [3] 을 병합하면 [3, 5] 로
[2] [1] 을 병합하면 [1, 2] 로
[6] [8] 을 병합하면 [6, 8] 로
[7] [4] 을 병합하면 [4, 7] 로 진행을 한 다음,
[3, 5] 과 [1, 2]을 병합하면 [1, 2, 3, 5] 로
[6, 8] 와 [4, 7]을 병합하면 [4, 6, 7, 8] 로 진행을 한 다음,
[1, 2, 3, 5] 과 [4, 6, 7, 8] 를 병합하면 [1, 2, 3, 4, 5, 6, 7, 8] 이 됩니다.
자 그러면 코드로 한번 구현을 해보겠습니다.
public static void main(String[] args) {
ArrayList<Integer> merge_arr = new ArrayList<>();
int[] arr = {5, 3, 2, 1, 6, 8, 7, 4};
int[] result_divide = merge_sort(arr);
for(int i : result_divide) {
System.out.println("i = " + i);
}
}
public static int[] merge_sort(int[] arr) {
int divide = arr.length / 2;
if (arr.length <= 1) {
return arr;
}
int[] left_array = Arrays.copyOfRange(arr,0, divide);
int[] right_array = Arrays.copyOfRange(arr, divide, arr.length);
return merge(merge_sort(left_array), merge_sort(right_array));
}
public static int[] merge(int[] array1, int[] array2) {
int[] result = new int[array1.length + array2.length];
int index_1 = 0;
int index_2 = 0;
int result_index = 0;
while (index_1 < array1.length && index_2 < array2.length) {
if (array1[index_1] < array2[index_2]) {
result[result_index] = array1[index_1];
index_1++;
result_index++;
} else {
result[result_index] = array2[index_2];
index_2++;
result_index++;
}
}
if (index_1 == array1.length) {
while (index_2 < array2.length) {
result[result_index] = array2[index_2];
index_2++;
result_index++;
}
}
if (index_2 == array2.length) {
while (index_1 < array1.length) {
result[result_index] = array1[index_1];
index_1++;
result_index++;
}
}
return result;
}
// 결과 [1,2,3,4,5,6,7,8]위의 코드는 '재귀 함수'를 이용해서 작성되었습니다. 자기 자신을 반복해서 호출해서 배열을 나눌수 없는 형태까지 갔다가 merge 메소드를 이용해서 나누었던 값들의 크기를 비교해 병합 결합을 진행하였습니다.
시간 복잡도 = O(Nlog_2N) = O(NlogN)