선택정렬
현재 위치에 들어갈 값을 찾아 정렬하는 방식
- 현재 위치에 저장될 값의 크기가 작냐 크냐에 따라 최대 선택 정렬(Max Selection Sort)과 최소 선택 정렬(Min-Selection Sort)로 구분이 가능하다.
- 최대 선택 정렬 → 내림 차순으로 정렬이 진행되는 방식
- 최소 선택 정렬 → 오름 차순으로 정렬이 진행되는 방식
동작 방식
- 주어진 리스트중에 최소값을 찾는다
- 그 값을 맨 앞에 위치한 값과 교체한다
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다
소스코드
void selectionSort(int[] list) {
int indexMin, temp;
for (int i = 0; i < list.length - 1; i++) {
indexMin = i;
for (int j = i + 1; j < list.length; j++) {
if (list[j] < list[indexMin]) {
indexMin = j;
}
}
temp = list[indexMin];
list[indexMin] = list[i];
list[i] = temp;
}
}
시간복잡도
최선, 평균, 최악의 경우일 때 선택 정렬에 소요되는 비교 횟수를 C라고 할 때, 이를 수식으로 나타내면 위와 같다.
삽입정렬
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교해 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
예시
31 25 12 22 11를 처음 상태라고 가정한다.
| 31 | [25] | 12 | 22 | 11 | 두 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다. |
| <25> | 31 | [12] | 22 | 11 | 세 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다. |
| <12> | 25 | 31 | [22] | 11 | 네 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다. |
| 12 | <22> | 25 | 31 | [11] | 마지막 원소를 부분 리스트에서 적절한 위치에 삽입한다. |
| <11> | 12 | 22 | 25 | 31 | 종료. |
소스코드
void insertionSort(int[] arr)
{
for(int index = 1 ; index < arr.length ; index++){
int temp = arr[index];
int aux = index - 1;
while( (aux >= 0) && ( arr[aux] > temp ) ) {
arr[aux + 1] = arr[aux];
aux--;
}
arr[aux + 1] = temp;
}
}
시간복잡도
n개의 데이터가 있을 때 최악의 경우는 위의 수식과 같으므로, 시간복잡도는 O(n^2)가 된다.
버블정렬
배열의 두 수를 선택한 뒤, 그 두 수가 정렬되어 있다면 놔두고 아니라면 바꾸는 방식으로 진행되는 정렬이다.
정렬 과정
다음과 같은 정렬되지 않은 배열이 있다고 가정한다. 프로그램은 이 배열을 오름차순으로 정렬해야 한다.
[7,2,0,1,5,6,4]
알고리즘은 배열의 첫 두 숫자(7,2)를 비교한다. 7>2로 정렬되지 않았으니 두 수를 바꾼다.
[2,7,0,1,5,6,4]
이를 배열의 처음부터 끝까지 작업한다면 다음이 된다.
1회
[2,0,1,5,6,4,7]
⇒ 가장 큰 수인 7이 정렬되었다.
2회
[0,1,2,5,4,6,7]
3회
[0,1,2,4,5,6,7]
4회
[0,1,2,4,5,6,7]
⇒ 3회부터 4회까지는 아무런 변화가 없으니 정렬된 것으로 판단한다.
소스코드
void bubbleSort(int[] arr) {
int temp = 0;
for(int i = 0; i < arr.length - 1; i++) {
for(int j= 1 ; j < arr.length-i; j++) {
if(arr[j]<arr[j-1]) {
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
시간복잡도
O(n^2)으로 느리지만, 코드가 간단해서 자주 사용된다.
합병정렬
비교 기반의 정렬 알고리즘으로 분할 정복 알고리즘의 일부이다.
알고리즘
n-way 합병 정렬의 개념은 다음과 같다.
- 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할한다. (한 원소만 든 리스트는 정렬된 것과 같으므로)
- 부분리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부분리스트를 생성한다. 마지막 남은 부분리스트가 정렬된 리스트이다.
흔히 쓰이는 하향식 2-way 합병 정렬은 다음과 같이 작동한다.
- 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
- 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
- 정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
- 결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
- 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다.
소스코드
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length <= 1)
return;
int[] temp = new int[arr.length];
mergeSort(arr, temp, 0, arr.length - 1);
}
private static void mergeSort(int[] arr, int[] temp, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, temp, left, mid); // 왼쪽 부분 배열 정렬
mergeSort(arr, temp, mid + 1, right); // 오른쪽 부분 배열 정렬
merge(arr, temp, left, mid, right); // 정렬된 부분 배열 병합
}
}
private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
// 임시 배열에 정렬된 값을 복사
for (int i = left; i <= right; i++) {
temp[i] = arr[i];
}
int i = left;
int j = mid + 1;
int k = left;
// 두 부분 배열을 비교하여 합병
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) {
arr[k++] = temp[i++];
} else {
arr[k++] = temp[j++];
}
}
// 남은 요소들 복사
while (i <= mid) {
arr[k++] = temp[i++];
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
System.out.println("정렬 전 배열:");
printArray(arr);
mergeSort(arr);
System.out.println("\\n정렬 후 배열:");
printArray(arr);
}
private static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
}
시간복잡도
크기가 N인 배열을 분할하면 한번 분할하면 N/2씩 2개, 그다음 분할하면 N/4씩 4개가 되므로, 분할과정이 매번 반씩 감소해 LogN만큼 반복해야 크기가 1인 배열로 분할이 가능하다.
퀵 정렬
알고리즘
퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.
- 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
- 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다.
- 이렇게 리스트를 둘로 나누는 것 → 분할이라고 한다.
- 분할을 마친 뒤에 피벗은 더이상 움직이지 않는다
- 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.
재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
예시
5 - 3 - 7 - 6 - 2 - 1 - 4
p
리스트 왼쪽에 있는 i 위치의 값이 피벗보다 크고, 오른쪽에 있는 j위치의 값은 피벗보다 작으므로 둘을 교환해야 한다.
5 - 3 - 7 - 6 - 2 - 1 - 4
i j p
1 - 3 - 7 - 6 - 2 - 5 - 4
i j p
j 위치의 값이 피벗 값보다 작지만, i 위치의 값도 피벗값보다 작으므로 교환하지 않는다.
1 - 3 - 7 - 6 - 2 - 5 - 4
i j p
i위치를 피벗 값보다 큰 값이 나올 때까지 진행해 j 위치의 값과 교환한다.
1 - 3 - 7 - 6 - 2 - 5 - 4
i j p
1 - 3 - 2 - 6 - 7 - 5 - 4
i j p
i위치가 j 위치보다 커지면, i 위치의 값과 피벗 값을 교환한다.
1 - 3 - 2 - 6 - 7 - 5 - 4
p
1 - 3 - 2 - 4 - 7 - 5 - 6
p
피벗 값 좌우의 리스트에 대해 각각 퀵 정렬을 재귀적으로 수행한다.
1 - 3 - 2 7 - 5 - 6
1 - 2 - 3 5 - 6 - 7
완성된 리스트는 다음과 같다.
1 - 2 - 3 - 4 - 5 - 6 - 7
소스코드
public void quickSort(int[] arr, int left, int right) {
// base condition
if (left >= right) {
return;
}
int pivot = arr[right];
int sortedIndex = left;
for (int i = left; i < right; i++) {
if (arr[i] <= pivot) {
swap(arr, i, sortedIndex);
sortedIndex++;
}
}
swap(arr, sortedIndex, right);
quickSort(arr, left, sortedIndex - 1);
quickSort(arr, sortedIndex + 1, right);
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
출처
https://ko.wikipedia.org/wiki/선택_정렬
https://ko.wikipedia.org/wiki/삽입_정렬
https://ko.wikipedia.org/wiki/버블_정렬
'Algorithm' 카테고리의 다른 글
| [자료구조] 우선순위 큐 (0) | 2024.07.23 |
|---|
보안 전공 개발자지만 대학로에서 살고 싶어요
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!
![[자료구조] 우선순위 큐](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdna%2FcfjgO4%2FbtsILQTvEd4%2FAAAAAAAAAAAAAAAAAAAAANq07HyD6Lhe-MPb03kr0OGcNDroQKJ-CKFm10Cl_qHY%2Fimg.png%3Fcredential%3DyqXZFxpELC7KVnFOS48ylbz2pIh7yKj8%26expires%3D1759244399%26allow_ip%3D%26allow_referer%3D%26signature%3DSWJUkx0nv4%252BOQgqxzI4HA7j%252Fucg%253D)