배열에서 가장 작은 원소를 찾아 첫 번째 원소와 교환하고 두 번째 작은 원소를 찾아 두 번째 원소와 교환하는 방식으로 전체를 정렬하는 알고리즘
전체 데이터(N)에 대해서 비교 횟수는N(N-1)/2가 되고 시간 복잡도는O(N2)이 되므로 입력 데이터의 수에 따라 시간이 오래 걸리는 알고리즘이고[1,2’,2]와 같은 입력 배열을 정렬하면[1,2,2’]와 같이 크기가 같음에도 상대적인 위치가 변경될 수 있다는 단점을 보유(불안정)
하지만 비교 횟수는 많아도 교환 횟수는 적어 교환이 많이 발생해야 하는 상황에서 효율적이며 구현하기 쉽다는 장점을 가짐
int* Selection(int* a, int n)
{
for (int i = 0; i < n; i++)
{
int minidx = i;
for (int j = i + 1; j < n + 1; j++)
{
if (a[j] < a[minidx])
minidx = j;
}
Swap(&a[i], &a[minidx]);
}
return a;
}
버블 정렬
서로 인접한 두 원소를 비교해 루프가 한 번 반복되면 가장 큰 원소를 맨 뒤로 보내는 알고리즘
구현이 매우 간단한 장점이 있지만, 가장 큰 원소가 맨 앞에 있는 경우 뒤로 이동하기 위해서 모든 요소와 교환되어야 하는 구조를 가짐. 따라서 레코드의 크기가 큰 경우 매우 비효율적인 알고리즘으로 O(N2)의 시간 복잡도를 가짐 (안정적) 전체 비교 횟수는 N(N-1)/2
void Bubble(int* a, int n)
{
for (int i = n; i >= 0; i--) // 큰 원소들을 뒤로 빼주니 줄여나가는 것
{
for (int j = 0; j < i; j++)
{
if (a[j] > a[j + 1])
Swap(&a[j], &a[j + 1]);
}
}
}
삽입 정렬
카드놀이 할 때와 유사 (왼쪽에서 오른쪽으로 움직이며 정렬 안된 원소를 빼서 임시 저장소에 두고 정렬된 원소들 사이에 적절한 위치에 끼어 넣음)
버블정렬의 비교횟수를 효율적으로 줄이기 위해 고안된 알고리즘으로 앞에서부터 차례대로 뒷부분의 배열과 비교하며 적절한 위치에 삽입하는 알고리즘
교환이 아닌 이동을 하기 때문에 버블정렬보다 빠른 효과를 볼 수 있으며 almost sorted 데이터에 가장 좋음, 평균적으로 O(N2)의 시간 복잡도를 가짐.
삽입정렬을 보완한 알고리즘으로 멀리 떨어진 원소끼리 교환이 가능하도록 해 정렬 속도를 향상시킴.전체를 여러 개의 부분 리스트로 만들어 각 부분 리스트를 삽입 정렬을 이용해 정렬시키고 모든 부분 리스트가 정렬되면 다시 전체를 더 적은 부분 리스트의 수로 만드는 방식으로 정렬함
삽입정렬보다 우수한 능력을 보이고 멀리 떨어진 원소간 여러 번 교환을 통해 정렬하던 버블정렬의 단점을 해결할 수 있음. 하지만 부분 리스트로 나눌 때 간격을 잘못 설정하면 성능이 매우 안좋아질 수 있음 (불안정)
i가 7이 됐을 때 피봇(r)과 교환되었으므로, 다음 부분 파티션은 [1~6], [8~10]이 됨
파티션[1~6] 부분에서 i는 4에서 피봇과 교환, 다음 부분 파티션은 [1~3], [5~6]위에서 나뉜 파티션 처리 [1~3], [5~6]처음 나뉜 파티션 처리 [8~10]
divide and conquer기법을 사용한 정렬 방법 중 하나로 피봇을 정해 두 개의 파티션으로 분할 후 왼쪽 파티션에서는 피봇보다 큰 원소가 존재하지 않도록, 오른쪽 파티션에는 피봇보다 작은 원소가 없도록 정렬하는 방식임
평균적으로 O(NlogN)의 시간복잡도를 갖고 입력 데이터가 역순의 데이터가 들어왔을 때 O(N2)이 되는 최악의 경우도 있음, 또 스택이 필요하다는 단점이 존재
가장 많이 사용되는 정렬법(평균적으로 아주 좋은 성능)이지만 불안정적인 제자리 정렬 알고리즘이며 입력 데이터에 대해 민감하다는 단점을 가짐. 그래서 퀵정렬의 성능을 향상시키는 방법으로 부분 리스트의 크기가 일정 크기 이하로 작아지면 almost sorted가 되므로 삽입 정렬을 수행하는 작은 부분화일 방법과 정렬되거나 역순으로 데이터가 들어올 경우 정렬을 못할 수도 있는 것을 막고자 중간 값 분할 방법이 존재함
int Partition(int* a, int left, int right)
{
int pivot = a[right]; // 가장 우측 값이 피봇
int i = left - 1; // 좌에서 우로 이동하는 포인터
int j = right; // 우에서 좌로 이동하는 포인터
while (true)
{
// 피봇 값보다 작으면 i값 증가
i++;
while (a[i] < pivot)
i++;
// 피봇 값보다 크면 j값 감소
j--;
while (a[j] > pivot)
j--;
if (i >= j) // i가 j를 넘어서면 교환해줘야 함
break;
// 피봇보다 작은 i값 찾았고
// 피봇보다 큰 j값 찾았다면
// 서로 값 교환
Swap(&a[i], &a[j]);
}
Swap(&a[i], &a[right]);
return i;
}
void Quick(int* a, int left, int right)
{
if (right > left)
{
int i = Partition(a, left, right);
Quick(a, left, i - 1);
Quick(a, i + 1, right);
}
void Merge(int* a, int left, int middle, int right)
{
int* b = new int[MAX + 1]; // 입력 데이터만큼 추가적인 메모리 공간 할당
// i: Left 배열의 좌측, j: Right 배열의 좌측, k: b메모리의 좌측
int i = left;
int j = middle + 1;
int k = left;
// b 메모리에 정렬하는 과정
while (i <= middle && j <= right)
{
if (a[i] < a[j])
{
b[k] = a[i];
k++; i++;
}
else
{
b[k] = a[j];
k++; j++;
}
}
// Left 배열이 끝나면 나머지 Right에 있는 원소들을 b로 옮김
if (i > middle)
{
for (int p = j; p <= right; p++)
{
b[k] = a[p];
k++;
}
}
else // Right 배열이 끝나면 Left의 나머지를 b로 옮김
{
for (int p = i; p <= middle; p++)
{
b[k] = a[p];
k++;
}
}
// 값 넘겨줌
for (int p = left; p <= right; p++)
a[p] = b[p];
delete[] b;
}
void MergeSort(int* a, int left, int right)
{
if (right > left)
{
int middle = (right + left) / 2;
MergeSort(a, left, middle); // divide 과정
MergeSort(a, middle + 1, right);
Merge(a, left, middle, right); // conquer 과정
}
}
힙은 힙 조건을 만족하는 완전 이진트리로 힙 조건은 각 노드의 값이 자식 노드의 값보다 커야 함. 힙정렬은 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법으로 힙의 루트를 가장 마지막 노드의 수와 교환함으로써 루트에 새로 저장된 수로 인해 위배된 힙 조건을 해결해 조건을 만족시키고 힙 크기를 1로 줄이면서 루트를 출력시킴. 이러한 과정을 반복하여 나머지 원소를 정렬
퀵정렬보다 느린 O(NlogN)이지만 추가적인 메모리를 요구하지 않고 입력 데이터에 민감하지 않아 항상 O(NlogN)을 보장한다는 점에서 장점임. 하지만 불안정하다는 단점을 보유(퀵도 불안정)
void Heapify(int* a, int h, int m) // 완전 이진트리화
{
// 루트 h를 제외한 h의 왼쪽 서브트리와 오른쪽 서브트리는 히프
// 초기 m: 노드의 최대 레벨 순서 번호
int temp = a[h];
int j;
for (j = 2 * h; j <= m; j = j * 2)
{
if (j < m && a[j] < a[j + 1])
j++;
if (temp >= a[j])
break;
else
a[j / 2] = a[j];
}
a[j / 2] = temp;
}
void Heap(int* a, int n)
{
for (int i = n / 2; i >= 0; i--)
Heapify(a, i, n); // a를 히프로 변환
for (int i = n - 1; i >= 0; i--) // a를 오름차순으로 정렬
{
Swap(&a[0], &a[i + 1]); // 0번째가 가장 큰 원소
Heapify(a, 0, i);
}
}
void Counting(int* a, int n, int m)
{
for (int j = 0; j <= m; j++) // 카운트 배열 초기화
cnt[j] = 0;
for (int i = 0; i <= n; i++) // 원소 개수 세기
cnt[a[i]]++;
for (int j = 1; j <= m; j++) // 원소 들어갈 위치 계산
cnt[j] = cnt[j - 1] + cnt[j];
for (int i = n; i >= 0; i--)
{
b[cnt[a[i]]] = a[i]; // a원소를 b의 미리 계산된 위치로 이동
cnt[a[i]]--;
}
for (int i = 0; i <= n; i++) // 임시 배열에 있는 값들 a로 이동
a[i] = b[i];
}
