가장 기본적으로 배우는 알고리즘인 정렬
대부분의 개발자들이 처음 배우는 알고리즘이라는 것이 아마 정렬 알고리즘일 것입니다. 데이터를 왜 정렬해야 할까요? 실생활에 예를 들어 내 방에 책 한권을 찾는 것은 몇분 걸리지 않습니다만(책이 몇권없음..) 도서관에서 책을 찾는다면 번호가 매긴 상태거나 제목, 구매일자, 등록일자 등등 기준으로 정리가 되어있지 않는다면 하루종일 찾아야 합니다. 이렇게 수백만, 수천만, 그냥 이론상 무한 개의 데이터를 다루어야하는 컴퓨터에게 정렬이란 정말인지 중요한 요소입니다. 그리고 이렇게 정렬을 수행하는 이유는 책을 찾는 것 처럼 데이터를 탐색하기 위해서이죠. 데이터를 탐색하는 알고리즘은 이진탐색 알고리즘으로 다음에 다루어 보고자 합니다. (다음에 뭐하지 하다가 블로그 정리로 찾아가는 공부의 방향성!)
대표적인 정렬 알고리즘
잘 모르는 사람에 경우 정렬이 종류가 다양한 것에 의문을 가질 수 있죠. 정리가 되기만 하면 되는 것이 아닌가..? 하지만 수 없이 메모리와 레지스터를 들낙거리는 컴퓨터에게 데이터에 유형에 따른 효율적인 정렬은 정말 중요합니다. 사실 나도 정렬 알고리즘을 따로 공부하기 전에는 필요성을 잘 몰랐습니다. 심지어 요즘 개발언어에 내장된 sort() 함수들은 내가 정렬 알고리즘에 대한 지식이 아얘 존재하지 않아도 정렬을 할 수 있게 해줍니다! 하지만 정렬 알고리즘을 공부함으로서 시간복잡도에 대한 이해도 생기고 효율적인 알고리즘이 왜 필요한 지에 대하여 체감할 수 있는 것 같아서 알고리즘 입문자에게 꼭 필요한 것 같습니다.
- 버블정렬(Bubble Sort)
- 선택정렬(Select Sort)
- 퀵정렬(Quicksort)
- 병합정렬(Merge Sort)
오늘 정리해 볼 정렬들 입니다. 대표적인 친구들이고 소스는 java로 구현하겠습니다.
버블정렬(Bubble Sort)
이름이 버블정렬이라 다른 정렬들은 이름만 보아도 어떻게 정렬한다는건지 느낌이라도 올탠데 이 녀석은 도대체 어떤식으로 정렬하겠다는 건지 감도 안옵니다. 버블정렬은 1번째와 2번째 원소를 비교하여 정렬하고 2번째와 3번째 n-1번째와 n번째를 계속 비교해가는 정렬로 어떤 개발자가 버블정렬을 실제 개발에서 사용하는 것을 보고 다른 개발자가 입에 거품을 물어서 버블정렬이 되었다는 슬픈 사연이.. 앞에는 헛소리고 이렇게 한 번 돌 때마다 하나씩 정렬되는 모습이 꼭 거품이 올라는 모습처럼 보여서 지어진 이름입니다. 이미 정렬된 자료를 정렬하는 것이 아니라면 정말 비효율적이어서 앞에 농담할 정도로 실제 개발에서는 거의 사용하지 않는다고 봅니다. 구현이 상당히 간단해서 자바에서 반복문 공부할 때 해봤던 기억이 있습니다. 시간복잡도는 O(n^2)
예시코드
public static void bubbleSort(int arr[]){
int result = 0;
int length = arr.length;
for(int i = length - 1; i > 0; i--){
for(int j = 0; j < i; j++){
if(arr[j] > arr[j+1]){
result = arr[j];
arr[j] = arr[j+1]; // j번째와 j+1번째의 수 자리바꿈
arr[j+1] = result;
}
}
}
}선택정렬(Selection Sort)
이름처럼 하나를 선택해서 모든 요소의 최솟값을 찾아주고 선택값과 변경하는 형식입니다. 버블정렬이 계속 서로 비교해서 바꾸어 넣는 방식이기에 선택정렬이 2배정도 빠르다고 합니다. 자료 수가 많아지면 효율이 떨어지지만 적은 자료라면 성능이 괜찮습니다. 코드는 최솟값만 잘 찾아주면 문제없이 구현 가능합니다. 시간복잡도는 O(n^2)
public static void selectionSort(int arr[]){
int min = 0;
int temp = 0;
int length = arr.length;
for(int i = 0; i < length-1; i++){ //마지막 요소는 정렬할 필요X
min = i; // 최솟값 인덱스를 min 변수에 담음
for(int j = i+1; j < length; j++){
if(arr[min] > arr[j]){
min = j;
}
}
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}퀵정렬(Quicksort)
퀵정렬은 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한다음, 각 부분리스트에 대해 다시 재귀적으로 수행하여 정렬하는 방법이다. 이 방법의 착안은 분할정복알고리즘이다.
병합정렬(Merge Sort)
퀵소트와 마찬가지로 분할정복알고리즘에서 착안한 이 알고리즘은 퀵소트가 불규칙한 크고 작은 피벗으로 나누어지는 반면에 이 정렬은 안정정렬에 속하면서 크기가 비슷한 두 부분의 피벗을 가진 리스트로 나누고 재귀적으로 수행하여 정렬하는 방법이다.
public static void mergeSort(int arr[]){
int[] temp = new int[arr.length]; // 정렬된 원소를 임시저장하는 배열
mergeSort(arr, temp, 0, arr.length - 1);
}
public static void mergeSort(int arr[], int[] temp, int start, int end){
if(start < end){
int mid = (start+end) / 2;
mergeSort(arr, temp, start, mid);
mergeSort(arr, temp, mid + 1, end);
merge(arr, temp, start, mid, end);
}
}
public static void merge(int arr[], int[] temp, int start, int mid, int end){
for(int i = start; i <= end; i++){
temp[i] = arr[i] ;
}
int part1 = start;
int part2 = mid + 1;
int index = start;
while (part1 <= mid && part2 <= end){
if(temp[part1] <= temp[part2]){
arr[index] = temp[part1];
part1++;
}else{
arr[index] = temp[part2];
part2++;
}
index++;
}
for(int i = 0; i <= mid - part1; i++){
arr[index + i] = temp[part1 + i];
}
}