참고
선택 정렬 (Selection Sort)
NOTE
선택 정렬 ⇒ 크키가 n인 배열에서 가장 작은 값을 선택하여 맨 앞자리 원소와 바꾸는 알고리즘!
배열은 순회하면서 가장 작은 값을 앞으로 보낸다.
public void sortBySelection(int[] arr) {
for (int i = 0; i < arr.length; i++) {
// arr[0, ... ,arr.length] 중 가장 작은 수 arr[indexOfMin] "선택"
int indexOfMin = i;
for(int j = i + 1; j < arr.length; j++) {
if(arr[indexOfMin] > arr[j]) { // 현재까지 최소값 > 현재 값
indexOfMin = j;
}
}
// array[i] <-> arr[indexOfMin] "자리 교환"
int temp = array[indexOfMin];
arr[indexOfMin] = arr[i];
arr[i] = temp;
}
}
Java
복사
구현 코
•
시간 복잡도 :
버블 정렬 (Bubble Sort)
NOTE
버블 정렬 ⇒ 크기가 n인 배열에서 왼쪽 부터 1칸씩 이동하며 이웃한 두 수를 비교해 순서가 제대로 되어있지 않으면 바꾸는 작업을 반복하는 알고리즘!
보글보글 알고리즘
public void sortByBubble(int[] arr) {
for (int i = arr.length - 1; i > 0; i--) {
for (int j = 0; j <= i; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
}
Java
복사
•
시간복잡도 : , 최선의 경우 :
삽입 정렬 (Insertion Sort)
NOTE
삽입 정렬 ⇒ 이미 정렬된 크기가 1인 배열에 하나씩 원소를 삽입하여 정렬된 크기가 n인 배열을 만드는 알고리즘!
크기가 1, 2, 3, 4 .. 이런씩으로 진행하면서 n까지 진행된다.
// int[] arr = {3, 5, 38, 44, 47, 15, 36, 26}
public void sortBySelection(int[] arr) {
// 크기 2 ~ n 까지 진행
for (int i = 1; i < arr.length; i++) { (1)
int currentValue = arr[i];
int pointer = i - 1;
// arr[0], arr[1], ..., arr[i-1]까지는 정렬된 상태
while (pointer >= 0 && arr[pointer] > currentValue) { (2)
// 비교하는 값이 현재 값보다 작으면, 뒤로 이동
arr[pointer + 1] = arr[pointer];
pointer--;
}
arr[pointer + 1] = currentValue;
}
}
Java
복사
•
시간복잡도 : , 최선의 경우 :
병합 정렬 (Merge Sort)
NOTE
병합 정렬 ⇒ 분할 정복과 재귀 알고리즘을 사용한 방식이며, 배열을 모두 분할하고, 다시 병합하는 과정을 재귀적으로 반복한다!
아래로 내려가는 과정이 분할, 올라오는게 병합
public void sortByMerge(int arr[], int start, int last) {
if (start < last) {
int mid = (start + last) / 2;
sortByMerge(arr, start, mid);
sortByMerge(arr, mid+1, last);
merge(arr, start, mid, last);
}
}
public void merge(int[] arr, start, mid, last) {
// 정렬된 첫번째 배열 arr[first...mid]
int[] leftArray = Arrays.copyOfRange(array, start, mid);
// 정렬된 두번째 배열 arr[mid+1...last]
int[] rightArray = Arrays.copyOfRange(array, mid + 1, last);
int i = 0, j = 0, k = start;
// 병합
while (i <= mid && j <= last) {
if(leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++;
} else {
arr[k] = rightArray[j];
j++;
}
k++;
}
// 왼쪽 배열에서 남은 원소 복사
while (i <= mid) {
arr[k] = leftArray[i];
i++;
k++;
}
// 오른쪽 배열에서 남은 원소 복사
while (j <= last) {
arr[k] = rightArray[j];
j++;
k++;
}
}
Java
복사
•
시간 복잡도 :