기본적인 정렬방법에 대해서 알아보겠습니다. 틀린점이 있을때 매번 발견해 업데이트 하겠습니다.
BubbleSort(거품정렬)
버블 정렬은 이웃한 두 요소의 대소 관계를 비교해 교환을 반복하는 정렬 방법입니다. 시간 복잡도 O(n^2)시간에 동작합니다.
[과정]
1. 서로 인접한 두 원소를 비교한 후, 큰 원소를 뒤로 보냅니다.
2. 1회전을 수행하면 가장 큰 자료가 맨 뒤로 이동합니다.
3. 이 과정을 요소의 개수가 N개인 배열에서 N-1회 비교 수행합니다.
void bubbleSort(int a[], int n){
for(int i = 0; i < n - 1; i++){
for(int j = n-1; j > i; j--){
if(a[j-1] > a[j])
swap(a[j-1],a[j]);
}
}
}
InsertionSort(삽입정렬)
배열에서 적절한 위치를 찾은 뒤에 해당 위치에 데이터를 삽입합니다. 필요할 때만 위치를 바꾸기 때문에 데이터가 거의 정렬되었을 때 효율적입니다. 시간복잡도는 O(n^2)이며, 데이터가 완전히 정렬된 경우는 O(n)의 시간 복잡도를 가집니다.
[과정]
1. 첫번째 데이터는 그 자체로 정렬되어 있다고 하자
2. 두번째 데이터부터 정렬된 데이터의 끝부터 처음까지 비교하면서 필요할 경우 삽입한다.
3. 마지막 데이터를 비교할 떄까지 반복한다.
void insertionSort(int a[6], int n){
int j = 0;
for(int i = 0; i < n-1; i++){
j = i;
while(a[j] > a[j+1]){
swap(a[j],a[j+1]);
j--;
}
}
}MergeSort(병합정렬)
배열의 앞 부분을 병합 정렬로 정렬하고, 배열의 뒷 부분을 병합 정렬로 정렬해 마지막으로 배열의 앞부분과 뒷부분을 병합하는 과정에서 재귀가 사용됩니다. 항상 O(nlogn)의 시간 복잡도를 갖으며, 추가적인 메모리 공간을 필요로 합니다.
[과정]
1. 중간 지점을 정해서 주어진 배열을 절반씩 나눔
2. 나눈 두 배열에 대해 재귀 호출
3. 두 배열의 값을 비교해가며 합쳐줍니다.
void merge(int left, int right){
int mid = (left + right) / 2;
int i = left;
int j = mid + 1;
int k = left;
while(i <= mid && j <= right){
if(a[i] <= a[j])
a2[k++] = a[i++];
else
a2[k++] = a[j++];
}
int tmp = i > mid ? j : i;
while(k <= right)
a2[k++] = a[tmp++];
for(int i = left; i <= right; i++)
a[i] = a2[i];
}
void partition(int left, int right){
int mid;
if(left < right){
mid = (left + right) / 2;
partition(left,mid);
partition(mid+1,right);
merge(left,right);
}
}QuickSort(퀵소트)
최선은 O(nlogn), 최악은 O(n2)시간에 동작합니다. 값이 이미 정렬되어있거나, 역순으로 정렬될 경우 과정마다 모든 요소를 탐색해야 하기 때문에 O(n2)의 시간이 동작하게 됩니다.
2개의 그룹을 나누는 기준인 피벗을 정해, 피벗 값 이하의 요소를 배열 왼쪽으로, 이상의 배열을 오른쪽으로 옮깁니다.
1. 배열에서 첫번쨰 데이터를 pivot으로 한다. 마지막에 두어도 상관없음
2. 배열을 분할하기 위해 left, right배열을 준비한다.
3. Pivot을 제외한 배열을 왼쪽에서부터 순회하면서 pivot보다 값이 작은 경우 left배열에 넣는다.
4. 같은 방법으로 순회하면서 pivot보다 값이 큰 경우 right 배열에 넣는다.
5. 처음 배열은 pivot보다 작은 값 배열, pivot보다 큰 값 배열로 나뉘어진다.
6. Pivot을 제외한 두 배열에 대해 퀵 정렬을 재귀 수행한다
7. Pivot과 배열을 나눌 수 없을 떄(주어진 배열의 원소가 하나일 때) 재귀를 종료한다.
void quickSort(int a[6], int left, int right){
int PL = left;
int PR = right;
int x = a[(PL+PR)/2];
do{
while(a[PL] < x) PL++;
while(a[PR] > x) PR--;
if(PL <= PR)
swap(a[PL++],a[PR--]);
}while(PL <= PR);
if(left < PR) quickSort(a, left, PR);
if(PL < right) quickSort(a, PL, right);
}HeapSort(힙정렬)
힙(heap)을 사용하는 정렬 방법입니다. 부모의 값이 자식의 값보다 항상 크다 또는 그 반대되는 조건을 만족하는 완전이진 트리를 말합니다. 가장 큰 값이 루트에 위치한다는 특징을 이용해 정렬을 수행하는 방법입니다.
[과정]
1. Downheap 메소드를 사용해 a[left]~a[right]의 요소를 힙으로 만듭니다.
2. 루트 a[0]에 있는 가장 큰 값을 빼내어 배열 마지막 요소와 바꿉니다.
3. 배열의 나머지 부분을 다시 힙으로 만드는 과정을 반복합니다.
Downheap을 수행시 left에 해당하는 i인자를 (n-1)/2로 한 이유는 힙이 완전 이진 트리이므로 노드의 개수의 절반이 리프노드의 부모노드이기 때문입니다.
void downHeap(int a[6], int left, int right){
int temp = a[left];
int child, parent;
for(parent = left; parent < (right+1)/2; parent = child){
int CL = parent*2+1;
int CR = CL + 1;
child = (CR <= right && a[CR] > a[CL]) ? CR : CL;
if(temp >= a[child]) break;
a[parent] = a[child];
}
a[parent] = temp;
}
void heapSort(int a[6], int n){
for(int i = (n-1)/2; i >= 0; i--)
downHeap(a,i,n-1);
for(int i = n-1; i > 0; i--){
swap(a[0],a[i]);
downHeap(a,0,i-1);
}
}CountingSort(계수정렬)
O(n)시간에 동작하며, 최악의 경우 O(n2)시간에 동작합니다. 배열에서 각 숫자가 몇번 들어가는지를 이용하는 정렬방법입니다.
각 숫자가 몇번 들어가는지 세어주고, 이 횟수를 누적합 배열로 만들어줍니다. 원소의 값이 클수록 배열의 길이 자체가 커지기 때문에 퀵 또는 힙 정렬이 이러한 상황에서는 더욱 빠릅니다. 원소의 값이 작은 것들로 이루어진 경우에만 사용하는 것이 좋스빈다.
[과정]
1. 가장 큰 데이터와 가장 작은 데이터의 차이 +1 크기의 배열을 선언한다. 모든 범위를 담을 수 있어야 하기 때문에
2. 배열을 0으로 초기화 하고
3. 데이터가 담긴 배열을 순회하면서 데이터 값에 해당하는 인덱스 위치의 데이터를 1씩 증가시킨다.
4. 계수를 저장한 배열을 순회하면서 그 값만큼 해당 인덱스 값을 출력한다.
void countingSort(int a[6], int n){
// max값을 찾아야하는게 우선이다
// 현재 9가 맥스
int count[9];
memset(count,0,sizeof(count));
for(int i = 0; i < n; i++){
count[a[i] - 1]++;
}
for(int i = 0; i < 9; i++){
if(count[i] != 0){
for(int j = 0; j < count[i]; j++){
cout << i+1 << " ";
}
}
}
cout << endl;
}
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int a[6] = {8,9,2,4,3,1};
int a2[6];
void bubbleSort(int a[6], int n){
cout << "Bubble Sort" << "\n";
for(int i = 0; i < n - 1; i++){
for(int j = n-1; j > i; j--){
if(a[j-1] > a[j])
swap(a[j-1],a[j]);
}
}
for(int i = 0; i < n; i++){
cout << a[i] << " ";
}
cout << endl;
/*
개선된 Bubble Sort
각각의 패스에서 비교, 교환을 하다가 어떤 시점에서 교환이 수행되지 않는다.
그보다 앞쪽의 요소는 이미 정렬을 맞췄다고 생각해도 무방하다.
마지막으로 요소를 교환한 위치를 저장해, 다음 패스에서 그 위치까지만 비교
*/
/*
int k = 0;
while(k < n-1){
int last = n-1;
for(int j = n-1; j > k; j--){
if(a[j-1] > a[j]){
swap(a[j-1],a[j]);
last = j;
}
}
k = last;
}
*/
}
void merge(int left, int right){
int mid = (left + right) / 2;
int i = left;
int j = mid + 1;
int k = left;
while(i <= mid && j <= right){
if(a[i] <= a[j])
a2[k++] = a[i++];
else
a2[k++] = a[j++];
}
int tmp = i > mid ? j : i;
while(k <= right)
a2[k++] = a[tmp++];
for(int i = left; i <= right; i++)
a[i] = a2[i];
}
void partition(int left, int right){
int mid;
if(left < right){
mid = (left + right) / 2;
partition(left,mid);
partition(mid+1,right);
merge(left,right);
}
}
void quickSort(int a[6], int left, int right){
int PL = left;
int PR = right;
int x = a[(PL+PR)/2];
do{
while(a[PL] < x) PL++;
while(a[PR] > x) PR--;
if(PL <= PR)
swap(a[PL++],a[PR--]);
}while(PL <= PR);
if(left < PR) quickSort(a, left, PR);
if(PL < right) quickSort(a, PL, right);
}
void downHeap(int a[6], int left, int right){
int temp = a[left];
int child, parent;
for(parent = left; parent < (right+1)/2; parent = child){
int CL = parent*2+1;
int CR = CL + 1;
child = (CR <= right && a[CR] > a[CL]) ? CR : CL;
if(temp >= a[child]) break;
a[parent] = a[child];
}
a[parent] = temp;
}
void heapSort(int a[6], int n){
for(int i = (n-1)/2; i >= 0; i--)
downHeap(a,i,n-1);
for(int i = n-1; i > 0; i--){
swap(a[0],a[i]);
downHeap(a,0,i-1);
}
}
void countingSort(int a[6], int n){
// max값을 찾아야하는게 우선이다
// 현재 9가 맥스
int count[9];
memset(count,0,sizeof(count));
for(int i = 0; i < n; i++){
count[a[i] - 1]++;
}
for(int i = 0; i < 9; i++){
if(count[i] != 0){
for(int j = 0; j < count[i]; j++){
cout << i+1 << " ";
}
}
}
cout << endl;
}
void insertionSort(int a[6], int n){
int j = 0;
for(int i = 0; i < n-1; i++){
j = i;
while(a[j] > a[j+1]){
swap(a[j],a[j+1]);
j--;
}
}
}
void selectionSort(int a[6], int n){
int j,min,index;
for(int i = 0; i < n; i++){
min = 9999;
for(j = i; j < n; j++){
if(min > a[j]){
min = a[j];
index = j;
}
}
swap(a[i],a[index]);
}
}
int main(){
int temp[6];
memcpy(temp,a,sizeof(temp));
bubbleSort(a,6);
memcpy(a,temp,sizeof(a));
// cout << "mergeSort" << "\n";
partition(0,5);
// for(int i = 0; i < 6; i++){
// cout << a[i] << " ";
// }
// cout << endl;
memcpy(a,temp,sizeof(a));
// cout << "quickSort" << "\n";
quickSort(a,0,5);
// for(int i = 0; i < 6; i++){
// cout << a[i] << " ";
// }
// cout << endl;
memcpy(a,temp,sizeof(a));
// cout << "HeapSort" << "\n";
heapSort(a,6);
// for(int i = 0; i < 6; i++){
// cout << a[i] << " ";
// }
// cout << endl;
// cout << "countingSort" << "\n";
memcpy(a,temp,sizeof(a));
countingSort(a,6);
// cout << "insertionSort" << "\n";
memcpy(a,temp,sizeof(a));
insertionSort(a,6);
// for(int i = 0; i < 6; i++){
// cout << a[i] << " ";
// }
// cout << endl;
// cout << "selectionSort"<< "\n";
memcpy(a,temp,sizeof(a));
selectionSort(a,6);
// for(int i = 0; i < 6; i++){
// cout << a[i] << " ";
// }
// cout << "\n";
return 0;
}