[알고리즘] 정렬(삽입 정렬, 버블 정렬, 선택 정렬, 퀵 정렬)

오늘 알아볼 알고리즘은 바로 정렬 알고리즘인데요 !

정렬 알고리즘에는 삽입 정렬, 버블 정렬, 선택 정렬, 퀵 정렬 등 많은 알고리즘들이 있지만

그 중 하나의 구현 방법만 익혀두면 유용하게 쓸 수 있습니다!

 

선택 정렬 

; 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

- 1번째부터 끝까지 훑어서 가장 작은 게 1번째, 2번째부터 끝까지 훑어서 가장 작은 게 2번째,.. 반복

- 장 ; 알고리즘이 단순함 / 교환이 버블 정렬에 비해 적게 일어나 많은 교환이 일어나는 자료상태에서 효율적

- 단 ; 시간 복잡도가 O(n^2)로 비효율적 

 

 

버블 정렬 

; 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘

- 1번째와 2번째 원소 비교하여 정렬, 2번째와 3번째,...,n-1번째와 n번째 정렬한 뒤 다시 처음으로 돌아와 이번에는 n-2번째와 n-1번쨰까지,.. 반복

- 장 ; 구현이 매우 간단 / 소스코드가 직관적 / 안정 정렬

- 단 ; 시간복잡도의 최악,최선,평균 모두 O(n^2)로, 매우 비효율적

 

 

삽입 정렬

; 2번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후 , 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입

- 장 ; 알고리즘이 단순함 / 선택 정렬, 버블 정렬에 비해 상대적으로 빠름

- 단 ; 평균과 최악의 시간복잡도가 O(n^2)로 비효율적

 

셸 정렬

; 일정한 거리만큼 떨어진 데이터와 비교하여 교환작업을 수행

- 삽입정렬의, 이웃한 위치로만 이동한다는 단점을 보완한 알고리즘

- h=h/2+1(h>3) / h=h-1(h<=3)

=> h거리만큼 떨어진 데이터와 비교하며 수행

 

 

퀵 정렬 

; 피벗을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법

- 장 ; 시간복잡도가 O(nlog2n)으로 빠름

- 단 ; 정렬된 배열에 대해서는 불균형 분할에 의해 오히려 수행시간이 더 오래걸림

 

#include <algorithm>
using namespace std;

void swap(int &a,int &b){
	int tmp=a;
	a=b;
	b=tmp;
}

// 1. 선택 정렬 
int arr[10]={1,5,3,4,7,2,10,6,12,63};
int n=10;

void selection_sort(){
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(arr[i]>arr[j]) swap(arr[i],arr[j]);
		}
	}
}
// 2. 버블 정렬 
void bubble_sort(){
	for(int i=n-1;i>0;i--){
		for(int j=i;j>0;j--){
			if(arr[j-1]>arr[j]) swap(arr[j-1],arr[j]);
		}
	}
}
// 3. 삽입 정렬
void insert_sort(){
	int i,j,tmp;
	for(i=1;i<n;i++){
		tmp=arr[i];
		for(j=i-1;j>=0 && arr[j]>tmp;j--){
			arr[j+1]=arr[j];
		}
		arr[j+1]=tmp;
	}
} 
// 4. 셸 정렬 
void shell_sort(){
	int h;
	if(n>3) h=n/2+1;
	else h=n-1;
	while(h>0){
		for(int i=0;i+h<n;i++){
			if(arr[i]>arr[i+h]) swap(arr[i],arr[i+h]);
		}
		if(h>3) h=h/2+1;
		else h=h-1;
	}
}
// 5. 퀵 정렬 
void quick_sort(int left,int right){
	int start=left, end=right, pivot=arr[left];
	do{
		while(arr[start]<=pivot) start++;
		while(arr[end]>pivot) end--;
		if(start<end){ swap(arr[start],arr[end]); }
	}while(start<end);
	swap(arr[left],arr[end]);
	if(left<end-1) quick_sort(left,end-1);
	if(end+1<right)	quick_sort(end+1,right);
}

int main() {
//	selection_sort();
//	bubble_sort();
//	insert_sort();
// 	shell_sort();
//	quick_sort(0,n-1);

	for(int i=0;i<n;i++) cout<<arr[i]<<' ';
	
	
	return 0;
}

 

2-way 병합 정렬 

; 요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식

- 데이터를 각 pass단계에서 2,4,8,16…순서로 묶어서 정렬하는 과정을 수행

- 각 pass에서 다른 정렬 방법을 적용해야 하므로 효율적인 방법은 아님

 

 

 

힙 정렬 

; 완전 이진트리를 기본으로 힙 자료구조를 기반으로 한 정렬 방식

1. 최대 힙(부모노드>자식노드)을 구성 

2. 루트 노드와 마지막 요소(마지막 레벨 우측 노드)와 교환한 후 다음 힙에서 배제

3. 힙의 사이즈가 0이 될때까지 반복

 

 

 

기수 정렬

; 큐를 사용하여 데이터를 일의자리수, 십의자리수, 백의 자리수 … 순서대로 입출력을 수행하면서 정렬을 수행

- 장 ; 문자열, 정수 정렬 가능

- 단 ; 자릿수가 없는 것(부동 소숫점)은 정렬 불가