//오름차순
for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {
if (arr[i] > arr[j]) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
}
}
- 시간 복잡도 : O(N^2)
void SelSort(int arr[], int n) // n : 배열크기
{
int i, j;
int maxIdx;
int temp;
for(i = 0; i < n-1; i++)
{
maxIdx = i; // 정렬 순서상 가장 앞서는 데이터의 index
for(j = i + 1; j < n; j++) // 최소값 탐색
{
if(arr[j] < arr[maxIdx])
maxIdx = j;
}
/* 교환 */
temp = arr[i];
arr[i] = arr[maxIdx];
arr[maxIdx] = temp;
}
}
- 시간 복잡도 : O(N^2)
- 정렬이 완료된 영역의 다음에 위치한 데이터가 그 다음 정렬대상이다. (위 그림에서 파란색 영역이 정렬이 완료된 영역)
- 데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾는 것이 효율적이다.
void InserSort(int arr[], int n)
{
int i, j;
int insData;
for(i = 1; i < n; i++)
{
insData = arr[i]; // 정렬 대상을 insData에 저장
for(j = i - 1; j >= 0 ; j--)
{
if(arr[j] > insData)
arr[j+1] = arr[j]; // 비교 대상 한 칸 뒤로 밀기
else
break; // 삽입 위치 찾았으니 탈출!
}
arr[j+1] = insData; // 찾은 위치에 정렬 대상 삽입!
}
}
- 시간 복잡도 : O(N^2)
- 분할 정복 알고리즘 디자인 기법을 활용한 정렬 방법이다.
- 재귀적으로 구현한다.
void MergeTwoArea(int arr[], int left, int mid, int right)
{
int fIdx = left;
int rIdx = mid+1;
int i;
int * sortArr = (int*)malloc(sizeof(int)*(right+1));
int sIdx = left;
while(fIdx<=mid && rIdx<=right)
{
if(arr[fIdx] <= arr[rIdx])
sortArr[sIdx] = arr[fIdx++];
else
sortArr[sIdx] = arr[rIdx++];
sIdx++;
}
if(fIdx > mid)
{
for(i=rIdx; i<=right; i++, sIdx++)
sortArr[sIdx] = arr[i];
}
else
{
for(i=fIdx; i<=mid; i++, sIdx++)
sortArr[sIdx] = arr[i]
}
for(i=left; i<=right; i++)
arr[i] = sortArr[i];
free(sortArr);
}
void MergeSort(int arr[], int left, int right)
{
int mid;
if(left < right)
{
// 중간 지점을 계산한다.
mid = (left+right) / 2;
// 둘로 나눠서 각각을 정렬한다.
MergeSort(arr, left, mid);
MergeSort(arr, mid+1, right);
// 정렬된 두 배열을 병합한다.
MergeTwoArea(arr, left, mid, right);
}
}
- 시간 복잡도 : O(NlogN)
- 공간 복잡도 : 임시 메모리가 필요하기 때문에 다른 정렬에 비해 크다.
- low의 오른쪽 방향 이동 : pivot보다 정렬의 우선순위가 낮은 데이터를 만날 때까지 (오름차순 기준, pivot보다 큰 값을 만날때까지)
- low의 왼쪽 방향 이동 : pivot보다 정렬의 우선순위가 높은 데이터를 만날 때까지 (오름차순 기준, pivot보다 작은 값을 만날때까지)
- 위 low와 high 모두 조건이 만족 되면 서로 값을 교환한다.
- 계속 진행하여 low와 high의 위치가 서로 바뀌면 high와 pivot의 위치를 교환한다.
- pivot값은 정렬이 완료된다.
- left가 right보다 커질 때까지 1) ~ 3) 과정을 반복한다.
int Partition(int arr[], int left, int right)
{
int pivot = arr[left]; // 피벗의 위치는 가장 왼쪽!
int low = left+1;
int high = right;
while(low <= high) // 교차되지 않을 때까지 반복
{
while(pivot >= arr[low] && low <= right)
low++;
while(pivot <= arr[high] && high >= (left+1))
high--;
if(low <= high) // 교차되지 않은 상태라면 Swap 실행
Swap(arr, low, high); // low와 high가 가리키는 대상 교환
}
Swap(arr, left, high); // 피벗과 high가 가리키는 대상 교환
return high; // 옮겨진 피벗의 위치 정보 반환
}
void QuickSort(int arr[], int left, int right)
{
if(left <= right)
{
int pivot = Partition(arr, left, right); // 둘로 나눠서
QuickSort(arr, left, pivot-1); // 왼쪽 영역을 정렬
QuickSort(arr, pivot+1, right); // 오른쪽 영역을 정렬
}
}
- 평균 시간 복잡도 : O(NlogN)
- 최악 시간 복잡도 : O(N^2)
- 최악의 경우는 pivot이 최대값이나 최소값을 선택할 때 이다. 이를 방지하기 위해서는 pivot을 선택하는 방식이 중요한데, 최대한 랜덤하게 선택하는 것이 좋다. (위의 구현은 가장 왼쪽이 pivot이라는 설정이다.)
- 최악의 경우가 있음에도 불구하고, 퀵정렬은 다른 정렬보다 평균적으로 가장 빠르다. 왜냐 하면, 데이터 이동횟수가 상대적으로 적고 별도의 메모리 공간을 요구하지 않는다. 또한 pivot을 설정하는 방식을 랜덤으로 설정한다면 최악의 경우가 나타날 확률은 거의 없기 때문이다.