정렬 알고리즘은 자료구조에서 빼놓을 수 없는 주제이다.
아래 코드를 미리 설명하자면, C++의 class를 사용해서 정렬하는 방식에 대한 코드와 출력 코드를 Sort class에 정의해두고, 정렬 전과 정렬 후의 결과를 출력하는 코드이다.
개념
1. SelectionSort
: 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복해 모든 수가 정렬될 때까지 반복해서 데이터를 정렬하는 방법[Code]
cppvoid SelectionSort(int* arr, int size){ int index; for(int i=0;i<size;i++){ index=i; for(int j=i+1;j<size;j++){ if(arr[j]<arr[index]){ index=j; } } int temp=arr[i]; arr[i]=arr[index]; arr[index]=temp; } }
pythonfor i in range(len(array)): min_index=i for j in range(i+1,len(array)): if array[min_index]>array[j]: min_index=j array[i],array[min_index]=array[min_index],array[i] #swap
2. InsertionSort
: 두번째 자료부터 시작해서 그 앞의 자료들과 비교하여 삽입할 위치를 지정한 후 뒤로 밀은뒤 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘[Code]
cppvoid InsertionSort(int* arr, int size){ int i,j,key; for(int i=2;i<size;i++){ key=arr[i]; j=i-1; while(j>=0 && arr[j]>key){ arr[j+1]=arr[j]; j--; } arr[j+1]=key; } }
pythonfor i in range(1,len(array)): for j in range(i,0,-1): if array[j]<array[j-1]: #한 칸씩 왼쪽으로 이동 array[j],array[j-1]=array[j-1],array[j] # swap else: #자기보다 작은 데이터를 만나면 반복문 종료 break
- 특징
1) 배열이 길어질수록 효율이 떨어진다
2) 임시변수 tmp가 필요하다
3) 추가적인 공간을 필요로하지 않는다
4) 선택정렬, 버블정렬보다 시간복잡도 측면에서 효율적이다.3. MergeSort
:Divide and Conquer 알고리즘 (분할정복)을 사용하여 정렬하는 방식으로, 더 이상 나눌 수 없을 때까지 Divide한 뒤, Merge하면서 수들을 비교하여 정렬한다.[Code]
void Merge(int* arr, int p, int mid, int r){ int i=p, j=mid+1, t=0; int tmp[r-p+1]; while(i<=mid && j<=r){ if(arr[i]<=arr[j]){ tmp[t++]=arr[i++]; }else{ tmp[t++]=arr[j++]; } } while(i<=mid){ tmp[t++]=arr[i++]; } while(j<=r){ tmp[t++]=arr[j++]; } for(int k=p,t=0;k<=r;k++,t++){ arr[k]=tmp[t]; } } void MergeSort(int* arr, int p, int r){ if(p<r){ int mid=(p+r)/2; MergeSort(arr,p,mid); MergeSort(arr,mid+1,r); Merge(arr,p,mid,r); } }
- 특징
1) 시간복잡도가O(nlogn)이여서O(n^2)인 선택정렬, 삽입정렬에 비해 비교적 안정적이다
2) Linked List로 구현할 경우 index만 변경하면 되기 때문에 데이터의 이동이 줄어들어 훨씬 효율적이다.
3) 데이터의 크기가 커지면 그만큼 데이터의 이동횟수도 증가하기 때문에 비효율적일 수 있다.4. QuickSort
: 데이터에서 pivot을 설정한 뒤 pivot의 좌우 데이터와 pivot을 비교해서 pivot보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 옮기면서 정렬하는 방식[Code]
cppvoid QuickSort(int* arr, int start, int end){ if(start>=end){ return; } int pivot=start; int i=start+1, j=end; int temp; while(i<=j){ while(i<=end && arr[i]<=arr[pivot]) i++; while(j>start && arr[j]>=arr[pivot]) j--; if(i>j) break; temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } temp=arr[j]; arr[j]=arr[pivot]; arr[pivot]=temp; pivot=j; QuickSort(arr,start,pivot-1); QuickSort(arr,pivot+1,end); }
pythondef quick_sort(array,start,end): if start>=end: return pivot=start #pivot은 첫 번째 원소 left=start+1 right=end while left<=right: #pivot보다 큰 데이터를 찾을 때까지 반복 while left<=end and array[left]<=array[pivot]: left+=1 #pivot보다 작은 데이터를 찾을 때까지 반복 while right>start and array[right]>=array[pivot]: right-=1 if left>right: array[right],array[left]=array[right],array[left] #분할 이후 왼쪽, 오른쪽에서 각각 정렬 수행 quick_sort(array, start, right-1) quick_sort(array, right+1,end)
- 특징
1) 병합정렬과 마찬가지로 시간복잡도가O(nlogn)이기 때문에 효율적이다.
2) 추가 메모리 공간을 필요로 하지 않는다.5. HeapSort
: MaxHeap이나 MinHeap을 구성해서 정렬을 하는 방법으로, 완전이진트리 형태를 만든 뒤 한 번에 하나씩 요소를 힙에서 꺼내 배열의 뒤부터 저장하면 정렬이 되게 된다.
<참고 - MaxHeap & MinHeap>
[Code]
void heapify(int* arr, int len, int parent){ int largest=parent; int leftchild=2*parent+1; int rightchild=2*parent+2; if(leftchild<len && arr[leftchild]>arr[largest]){ largest=leftchild; } if(rightchild<len && arr[rightchild]>arr[largest]){ largest=rightchild; } if(largest!=parent){ this->swap(&arr[parent],&arr[largest]); heapify(arr,len,largest); } } void heapSort(int* arr, int len){ for(int i=len/2-1;i>=0;i--){ heapify(arr,len,i); } for(int i=len-1;i>0;i--){ this->swap(&arr[0],&arr[i]); heapify(arr,i,0); } }
6. RadixSort
: 다른 정렬방식과 달리 값을 비교하지 않는 정렬이다. 값을 놓고 비교할 자릿수를 정한 뒤, 해당 자릿수만 비교해서 10개의 queue에 데이터를 삽입하는 과정을 반복한다.[Code]
void RadixSort(int* arr, int size){ int Radix=1, MAX_VAL=arr[0]; for(int i=1;i<size;i++) { if(arr[i]>MAX_VAL) { MAX_VAL=arr[i]; } } while(1){ if(Radix>=MAX_VAL) break; Radix*=10; } for(int i=1;i<Radix;i*=10){ for(int j=0;j<10;j++){ while(!Q[j].empty()){ Q[j].pop(); } } for(int j=0;j<size;j++){ int k; if(arr[j]<i) k=0; else k=(arr[j]/i)%10; Q[k].push(arr[j]); } int idx=0; for(int j=0;j<10;j++){ while(!Q[j].empty()){ arr[idx]=Q[j].front(); Q[j].pop(); idx++; } } } }
- 과정
1) 각 데이터의 1의 자리를 비교해서 같은 것끼리 모은다
-> 같은 자릿수에 여러개의 데이터가 있을 경우 나열된 순서로 데이터를 모은다
2) 그 다음으로 10의 자리를 비교해서 같은 것끼리 모은다
3) 데이터의 최대 자릿수까지 이 과정을 반복한다
소스 코드
#include <iostream>
#include <queue>
const int MAX=100;
using namespace std;
queue<int> Q[10]; // 기수정렬때 사용하기 위함
class Sort{
public:
void swap(int* a, int* b){
int tmp=*a;
*a=*b;
*b=tmp;
}
void InsertionSort(int* arr, int size){
int i,j,key;
for(int i=2;i<size;i++){
key=arr[i];
j=i-1;
while(j>=0 && arr[j]>key){
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
}
void SelectionSort(int* arr, int size){
int index;
for(int i=0;i<size;i++){
index=i;
for(int j=i+1;j<size;j++){
if(arr[j]<arr[index]){
index=j;
}
}
int temp=arr[i];
arr[i]=arr[index];
arr[index]=temp;
}
}
void Merge(int* arr, int p, int mid, int r){
int i=p, j=mid+1, t=0;
int tmp[r-p+1];
while(i<=mid && j<=r){
if(arr[i]<=arr[j]){
tmp[t++]=arr[i++];
}else{
tmp[t++]=arr[j++];
}
}
while(i<=mid){
tmp[t++]=arr[i++];
}
while(j<=r){
tmp[t++]=arr[j++];
}
for(int k=p,t=0;k<=r;k++,t++){
arr[k]=tmp[t];
}
}
void MergeSort(int* arr, int p, int r){
if(p<r){
int mid=(p+r)/2;
MergeSort(arr,p,mid);
MergeSort(arr,mid+1,r);
Merge(arr,p,mid,r);
}
}
void QuickSort(int* arr, int start, int end){
if(start>=end){
return;
}
int pivot=start;
int i=start+1, j=end;
int temp;
while(i<=j){
while(i<=end && arr[i]<=arr[pivot])
i++;
while(j>start && arr[j]>=arr[pivot])
j--;
if(i>j)
break;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
temp=arr[j];
arr[j]=arr[pivot];
arr[pivot]=temp;
pivot=j;
QuickSort(arr,start,pivot-1);
QuickSort(arr,pivot+1,end);
}
void heapify(int* arr, int len, int parent){
int largest=parent;
int leftchild=2*parent+1;
int rightchild=2*parent+2;
if(leftchild<len && arr[leftchild]>arr[largest]){
largest=leftchild;
}
if(rightchild<len && arr[rightchild]>arr[largest]){
largest=rightchild;
}
if(largest!=parent){
this->swap(&arr[parent],&arr[largest]);
heapify(arr,len,largest);
}
}
void heapSort(int* arr, int len){
for(int i=len/2-1;i>=0;i--){
heapify(arr,len,i);
}
for(int i=len-1;i>0;i--){
this->swap(&arr[0],&arr[i]);
heapify(arr,i,0);
}
}
void RadixSort(int* arr, int size){
int Radix=1, MAX_VAL=arr[0];
for(int i=1;i<size;i++) {
if(arr[i]>MAX_VAL) {
MAX_VAL=arr[i];
}
}
while(1){
if(Radix>=MAX_VAL)
break;
Radix*=10;
}
for(int i=1;i<Radix;i*=10){
for(int j=0;j<10;j++){
while(!Q[j].empty()){
Q[j].pop();
}
}
for(int j=0;j<size;j++){
int k;
if(arr[j]<i)
k=0;
else
k=(arr[j]/i)%10;
Q[k].push(arr[j]);
}
int idx=0;
for(int j=0;j<10;j++){
while(!Q[j].empty()){
arr[idx]=Q[j].front();
Q[j].pop();
idx++;
}
}
}
}
void printSorting(int* arr, int size){
for(int i=0;i<size;i++){
cout<<arr[i]<<" ";
}
cout<<'\n';
} // 출력 함수
};
int main(void){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int arr1[9]={4,9,2,8,1,7,5,6,3};
int arr2[9]={2,8,5,1,4,6,7,3,9};
int arr3[9]={3,4,8,2,1,9,6,5,7};
int arr4[9]={1,7,3,9,5,4,2,8,6};
int arr5[9]={7,8,4,2,5,1,3,6,9};
int arr6[9]={1,4,6,8,9,7,5,3,2};
Sort sort;
// 1. 삽입 정렬
cout<<"Original: ";
sort.printSorting(arr1,9);
sort.InsertionSort(arr1,9);
cout<<"InsertionSort: ";
sort.printSorting(arr1,9);
cout<<'\n';
// 2. 선택 정렬
cout<<"Original: ";
sort.printSorting(arr2,9);
sort.SelectionSort(arr2,9);
cout<<"SelectionSort: ";
sort.printSorting(arr2,9);
cout<<'\n';
// 3. 병합 정렬
cout<<"Original: ";
sort.printSorting(arr3,9);
sort.MergeSort(arr3,0,8);
cout<<"MergeSort: ";
sort.printSorting(arr3,9);
cout<<'\n';
// 4. 퀵 정렬
cout<<"Original: ";
sort.printSorting(arr4,9);
sort.QuickSort(arr4,0,8);
cout<<"QuickSort: ";
sort.printSorting(arr4,9);
cout<<'\n';
// 5. 힙정렬
cout<<"Original: ";
sort.printSorting(arr5,9);
sort.heapSort(arr5,9);
cout<<"HeapSort: ";
sort.printSorting(arr5,9);
cout<<'\n';
// 6. 기수정렬
cout<<"Original: ";
sort.printSorting(arr6,9);
sort.RadixSort(arr6,9);
cout<<"RadixSort: ";
sort.printSorting(arr6,9);
return 0;
}결과
출처
각종 image, gif : 나무위키, 블로그 등등
Do it! 알고리즘 코딩테스트 C++
블로그 이전했습니다 (https://phj6724.tistory.com/)