Insertion Sort

삽입정렬
선택정렬
버블정렬
Loop Invariant
- 초기조건
- 유지조건
- 종료조건
삽입정렬
#include <iostream>
using namespace std;
void insertion_sort(int* arr, int size){
for(int i=1, j; i<size; ++i){
int key=arr[i];
j=i-1;
while(j>=0 && arr[j]>key){
arr[j+1]=arr[j];
j=j-1;
}
arr[j+1]=key;
}
}
int main(void){
int arr[]={5, 2, 4, 6, 1, 3};
int size=sizeof(arr)/sizeof(int);
insertion_sort(arr, size);
for(int i=0; i<size-1; ++i){
cout<<arr[i]<<", ";
}
cout<<arr[size-1]<<endl;
}
선택정렬
#include <iostream>
#define swap(a, b) {int tmp=a; a=b; b=tmp;}
using namespace std;
void selection_sort(int* arr, int size){
for(int i=0; i<size; ++i){
int ind=i;
for(int j=i; j<size; ++j){
if(arr[ind]>arr[j]) ind=j;
}
swap(arr[i], arr[ind]);
}
}
int main(void){
int arr[]={5, 2, 4, 6, 1, 3};
int size=sizeof(arr)/sizeof(int);
selection_sort(arr, size);
for(int i=0; i<size-1; ++i){
cout<<arr[i]<<", ";
}
cout<<arr[size-1]<<endl;
}
버블정렬
#include <iostream>
#define swap(a, b) {int tmp=a; a=b; b=tmp;}
using namespace std;
void bubble_sort(int* arr, int size){
for(int i=0; i<size-1; ++i){
for(int j=size-1; j>i; --j){
if(arr[j]<arr[j-1]) swap(arr[j], arr[j-1]);
}
}
}
int main(void){
int arr[]={5, 2, 4, 6, 1, 3};
int size=sizeof(arr)/sizeof(int);
bubble_sort(arr, size);
for(int i=0; i<size-1; ++i){
cout<<arr[i]<<", ";
}
cout<<arr[size-1]<<endl;
}