⛳ 선택 정렬 (Selection Sort)
● 배열을 계속 순환하면서 적절한 값을 찾게 되면 현재 인덱스에 있는 값과 교환해줌
● 배열 전체를 비교하므로 시간 복잡도는 O(N^2) 이다.
● 단 하나의 배열로 정렬을 하는 것이기 때문에 공간복잡도는 O(N) 이다.
void selectionSort(int *list, const int n)
{
int i, j, indexMin, temp;
for (i = 0; i < n - 1; i++)
{
indexMin = i;
for (j = i + 1; j < n; j++)
{
if (list[j] < list[indexMin])
{
indexMin = j;
}
}
temp = list[indexMin];
list[indexMin] = list[i];
list[i] = temp;
}
}⛳ 삽입 정렬 (Insertion Sort)
● 자신보다 이전의 인덱스 값을 비교하면서 적절한 위치를 찾아가는 알고리즘
● 최악의 경우인 역으로 정렬되있을 때는 시간 복잡도가 O(N^2) 이지만, 이미 정렬 되있는 경우 시간 복잡도가 O(N) 이다.
● 단 하나의 배열로 정렬을 하는 것이기 때문에 공간복잡도는 O(N) 이다.
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;
}
}⛳ 버블 정렬 (Bubble Sort)
● 자신의 앞쪽에 있는 인덱스하고 비교하면서 적잘한 위치를 찾아가는 알고리즘
● 선택 정렬과 마찬가지로 시간 복잡도가 O(N^2) 이다.
● 단 하나의 배열로 정렬을 하는 것이기 때문에 공간복잡도는 O(N) 이다.
void Bubble_Sort(int arr[], int len) {
int i, j, tmp;
for (i = 0; i < len - 1; ++i) {
for (j = 0; j < len - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}⛳ 합병 정렬 (Merge Sort) ★
● 배열을 반씩 나누면서 더 이상 분할 할 수 없을 때까지 분할하고, 그 안에서 정렬을 진행한다. 그 다음 다시 배열을 합치면서 정렬이 된 배열끼리 다시 정렬을 하는 알고리즘
● 성능은 전반적으로 퀵 정렬보다 떨어지고 추가적인 메모리를 필요로 하지만, 데이터 상태에 크게 영향을 받지 않음
● 시간 복잡도는 O(NlogN), 공간 복잡도는 2n개
void mergeSort(int A[], int low, int high, int B[]){
if(low >= high) return;
int mid = (low + high) / 2;
mergeSort(A, low, mid, B);
mergeSort(A, mid+1, high, B);
int i=low, j=mid+1, k=low;
for(;k<=high;++k){
if(j > high ) B[k] = A[i++];
else if(i > mid) B[k] = A[j++];
else if(A[i] <= A[j]) B[k] = A[i++];
else B[k] = A[j++];
}
// 5. copy
for(i=low;i<=high;++i) A[i] = B[i];
}⛳ 퀵 정렬 (Quick Sort) ★
● 인덱스 한개를 기준(Pivot)으로 두고, Left는 기준으로 둔 값보다 작은 값, Right는 기준으로 둔 값보다 큰 값으로 정렬하는 알고리즘
● Pivot의 값을 잘못 선택하는 최악의 경우, 시간 복잡도는 O(n^2) 이기 때문에 데이터 상태에 따라 알고리즘 성능이 달라지긴 하나, 메모리의 제약을 받지 않음
● 일반적인 시간 복잡도는 O(NlogN), 공간 복잡도는 O(N)
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int pivot = arr[(left + right) / 2];
int temp;
while (i <= j)
{
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j)
{
// SWAP(arr[i], arr[j])
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (left < j) quickSort(arr, left, j);
if (i < right) quickSort(arr, i, right);
}