기본정렬

선택, 버블, 삽입, 쉘, 퀵, 합병, 힙, 계수, 기수 정렬

 

모두 오름차순을 기준으로 정렬

 

1. 선택 정렬

첫번째 원소부터 마지막 원소까지 정렬을 한다고 했을때 전체 배열 중 가장 작은 원소를 찾아 첫번째 원소부터 순서대로 교환해가며 최솟값을 차례대로 넣는 정렬이라고 할 수 있다. 그래서 총 n번, 나머지 원소들 n-1, n-2, n-3, ... 개의 원소와 비교하게 되므로 시간복잡도는 O(n^2)이다.

 

2. 버블 정렬

거품이 수중위로 올라가는 것처럼 인덱스를 첫번째에서 마지막으로 이동하는 도중 해당 위치에서의 값이 다음 인덱스의 값보다 크면 교환하여 값이 큰 원소를 마지막으로 계속해서 밀어내는 정렬 방법이라고 할 수 있다. 즉 마지막위치에 최댓값을 쌓아가는 방식으로 정렬한다. 시간복잡도는 O(n^2)이다.

 

3. 삽입 정렬

삽입 정렬은 카드뽑기와 비슷한 원리라고 할 수 있다.  첫번째 원소부터 마지막 원소까지 n번 탐색과정 중 현재 인덱스의 원소값을 임시로 저장한 후 이전인덱스들과 순차적으로 비교해 가며 저장 값보다 큰 원소가 나오는 동안은 계속 이동 한다. 자신보다 작은 원소가 나오면 해당 인덱스의 다음 인덱스에 값을 삽입하는 정렬 방법이라고 할 수 있다. 시간복잡도는 O(n^2).

 

4. 쉘 정렬

부분화일을 선정해서 해당 부분화일들끼리 삽입정렬를 수행하는 방법이라고 할 수 있다.  삽입정렬의 경우 자신보다 작은 원소가 나오게 되면 해당 인덱스에 대한 탐색을 마치기 때문에 쉘 정렬을 통해 거의 정렬이 된 배열을 미리 만들어주는 방식이라고 할 수 있다. 그래서 화일 값을 어떻게 선정하는 지가 가장 중요한 요소 중 하나라고 할 수 있다. 화일 값 선정은 대체로 h = h*3 + 1 의 값들로 선정하되 그 크기가 배열의 전체 크기인 n보다 작은 값을 선정한다. 예를들어 h=4 이고 n=10이면 [1,5,9], [2,6,10], [3,7], [4,8] 번째 원소가 부분 화일(배열)이 되어 각각 삽입정렬을 수행하는 방식이라고 할 수 있다.  시간복잡도는 최악의 경우 O(n^2)이지만 보통 O(n^(2/3)) 을 따른다.

 

5. 퀵 정렬

이분탐색의 개념이 들어간 정렬. 피봇값을 기준으로 왼쪽에 남아있는 원소들 중 첫번째를 i 인덱스로 지정, 마지막 원소를 j 로 지정해서 i는 피봇보다  큰 값이 나올때까지 오른쪽으로 이동 시키고 j는 피봇보다 작은 값이 나올때까지 왼쪽으로 이동시킨다. 그리고 i와 j의 값을 교환한다. 이와 같은 과정을 i>=j가 되면 멈추고 i번째 원소와 피봇값을 교환한다.  

그리고 i-1 값을 다음 분할의 분기점인 피봇값으로 지정한다. 즉 1부터 n까지 배열이 있다고 하면 맨 처음 피봇값은 n번째 원소의 값이 되고 교환과정을 거쳐 n/2 번째 값을 다음 피봇으로 지정하게 되면 그다음 탐색은 1~n/2,  n/2+1 ~ n 범위에서 위와 같은 방식으로 부분정렬을 진행하게 된다. 대체로 이분탐색의 개념이라고 할 수 있기떄문에 시간복잡도는 O(nlogn)이다.

 

6. 합병 정렬

이분탐색을 통해 분할정복을 적용한 정렬 방법이다. 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할 된 리스트를 합하여 전체 리스트를 정렬시키는 방법이다. 시간복잡도는 O(nlogn)

 

7. 힙 정렬

 트리를 최대힙 구성으로 만든 후에 첫번째 원소를 마지막 원소와 교환하여 다시 최대힙 구성으로 만들어주며 리스트의 마지막 원소를 최댓값으로 계속해서 쌓는 방식으로 정렬하는 방법이다. 최대힙 구성은 부모노드와 자식노드와의 값을 비교하며 교환하는 방식이다. 노드의 높이가 logn이기 때문에 최대힙으로 트리를 구성하는 시간복잡도는 logn이다. 거기에 n개의 원소를 정렬하는 방식이기 때문에 총 시간 복잡도는 nlogn이라고 할 수 있다.

 

8. 계수 정렬

리스트의 값의 범위가 작을 때 쓰기 좋은 정렬이다. Counting 이라고 하는 값의 갯수를 저장하는 배열을 추가로 사용한다. 그래서 해당 원소의 갯수만큼 차례대로 리스트를 재정렬 하는 방법이기 때문에 시간복잡도는 O(N) 밖에 되지 않는다. 하지만 원소 값의 범위가 클때 Counting 배열 공간이 매우 커지기 때문에 메모리의 낭비가 있다는 단점이 있다.

 

9. 기수 정렬 

기수 정렬은 리스트의 원소값의 자릿수를 기준으로 0~9까지 표현되기 때문에 10개의 큐를 생성하여 1의 자리에서부터 10, 100, 1000, ... , 원소값의 최대 자릿수 까지 원소의 숫자에 해당하는 큐에 넣어 리스트를 재정렬 하는 방식이다. 그래서 원소값의 최대 자릿수까지 이 과정을 반복하면 리스트의 정렬이 끝나게 된다. 이 방법은 O(자릿수 * n )의 시간 복잡도를 가지고 있지만  자릿수가 커지게 되면 큐를 자릿수 만큼 생성해야하는 메모리 낭비와 그만큼 시간복잡도가 커지는 단점을 가지고 있다. 따라서 자릿수의 범위가 작을 때 유용하게 사용된다.

 

반응형

 

소스코드

 

 

	#include <iostream>
	#include <cstring>
	#include <string>
	#include <deque>
	#define MAX 100
	#define INF 1000000000
	using namespace std;
	int arr[MAX + 1];
	int visit[MAX + 1];
	int n;
	void Swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
	}
	void Print() {
	for (int i = 1; i <= n; i++) {
	cout << arr[i] << " ";
	}
	cout << endl;
	}
	// 선택, 버블, 삽입, 쉘 정렬
	void selection_sort(int *a) {
	// 선택정렬 알고리즘은 가장 높은 수를 찾아서 0,1,2,3,... 번째 인덱스에 순차적으로
	//넣는 알고리즘이다. 시간복잡도는 O(n^2)
	int idx;
	int x, y;
	for (int i = 1; i <= n-1; i++) {
	x = a[i];
	for (int j = i + 1; j <= n; j++) {
	y = a[j];
	if (x > y) {
	x=y;
	idx = j;
	}
	}
	if (a[i] > x) {
	Swap(&a[i], &a[idx]);
	}
	}
	}
	void bubble_sort(int *a) {
	//버블정렬은 오름차순 정렬을 한다고 가정했을 떄
	//거품이 수중에서 올라가는 것처럼 현재 위상에서 다음숫자가 현재숫자보다 작으면
	//스왑을 하고 이 과정을 마지막 인덱스에 도달할떄까지 반복하는 과정이다. 시간복잡도는 O(n^2)
	for (int i=n; i >=2; i--) {
	for (int j = 1; j < i; j++) {
	if (a[j] > a[j + 1])Swap(&a[j], &a[j + 1]);
	}
	}
	}
	void insert_sort(int *a) {
	//삽입정렬은 카드뽑기 원리와 비슷하다
	//4132 2번 인덱스부터 시작 자기보다 작은수가 나오기 직전까지 모든 수들을 오른쪽으로 민다.
	// 해당 위치에 자신의 수를 넣는다. 시간복잡도 O(n^2)
	for (int i = 2; i <= n; i++) {
	int temp = a[i];
	int idx = i;
	while (a[idx-1]>temp) {
	a[idx] = a[idx - 1];
	idx--;
	}
	a[idx] = temp;
	}
	}
	void shell_sort(int *a) {
	//부분화일값 생성// 화일 값 계속 해서 줄여나가면서 해당 화일 인덱스 간격끼리
	//삽입정렬 수행하는 방법, 시간복잡도는 O(n^3/2)
	int h;
	for (h = 1; h < n; h = h * 3 + 1);
	for (; h > 0; h /= 3) {
	for (int i = h + 1; i <= n; i++) {
	int temp = a[i];
	int idx = i;
	while (idx>h&&a[idx - h] > temp) {
	a[idx] = a[idx - h];
	idx -= h;
	}
	a[idx] = temp;
	}
	}
	}
	//퀵정렬
	int find_pibot(int *a, int s, int e) {
	int v = a[e];
	int i = s, j = e - 1;
	while (true) {
	while (a[i] < v)i++;
	while (a[j] > v)j--;
	if (i >= j)break;
	Swap(&a[i], &a[j]);
	}
	Swap(&a[i], &a[e]);
	return i - 1;
	}
	void quick_sort(int *a,int s,int e) {
	if (s >= e)return;
	int m = find_pibot(a, s, e);
	quick_sort(a, s, m);
	quick_sort(a, m + 1, e);
	}
	//합병정렬
	void merge(int *a,int s,int m,int e) {
	int b[MAX + 1];
	int idx = 0;
	int l_idx = s, r_idx = m + 1;
	while (l_idx <= m&&r_idx<=e) {
	if (a[l_idx] < a[r_idx]) {
	b[idx++] = a[l_idx++];
	}
	else {
	b[idx++] = a[r_idx++];
	}
	}
	while (l_idx <= m) {
	b[idx++] = a[l_idx++];
	}
	while (r_idx <= e) {
	b[idx++] = a[r_idx++];
	}
	for (int i = s; i <= e; i++) {
	a[i] = b[i - s];
	}
	}
	void merge_sort(int *a,int s,int e) {
	//합병정렬은 분할 정복을 통해 이분탐색 방법으로 계속해서 분할을 해나가며 분할이 끝난
	//원소부터 (left부터) 순차적으로 합병해 나가는 정렬방법 , O(nlogn)
	if (s >= e)return;
	int mid = (s + e) / 2;
	merge_sort(a, s, mid);
	merge_sort(a, mid + 1, e);
	//cout << "s " << s << " e " << e << endl;
	merge(a, s, mid, e);
	}
	//힙정렬
	void heapfify(int *a,int h,int m) {//히피파이 -> h에서부터 말단노드 m까지 수행
	int temp = a[h];
	int idx;
	for (idx = h*2; idx <= m; idx *= 2) {
	if (idx + 1 <= m && a[idx] < a[idx + 1])idx++;
	if (a[idx] > a[idx / 2])Swap(&a[idx], &a[idx / 2]);
	}
	}
	void heap_sort(int *a,int n) {
	//말단 부모 노드 먼저 히피파이 시켜주고
	for (int i = n / 2; i >= 1; i--) {
	heapfify(a, i, n);
	}
	//그 이후에는 1번과 마지막 노드 스왑시켜준후
	//1번 히피파이 쭉쭉 시간복잡도 O(nlogn)
	for (int i = n-1; i >= 1; i--) {
	Swap(&a[1], &a[i+1]);
	heapfify(a, 1, i);
	}
	}
	//계수, 기수 정렬
	void counting_sort(int *a,int k) {
	//배열값의 범위가 좁을 떄 사용 왜냐하면 이범위가 넓어지면 이것을 기억하는 저장소 배열인
	//Count배열 크기가 매우 커짐 -> 공간낭비 가능성 커짐 시간복잡도는 O(N)
	int Count[MAX + 1];// k값의 범위가 1~100까지만 있다고 가정
	memset(Count, 0, sizeof(Count));
	for (int i = 1; i <= n; i++)Count[a[i]]++;
	for (int i = 1; i <= k; i++)Count[i + 1] += Count[i];
	//for (int i = 1; i <= k; i++)cout << Count[i] << " ";
	//cout << endl;
	int cnt = n;
	while (cnt >= 1) {
	if (Count[k] > Count[k - 1]) {
	a[cnt--] = k;
	Count[k]--;
	}
	else k--;
	}
	}
	void radix_sort(int *a) {
	//자릿수 별로 정렬하는 방법
	//가장 높은 자릿수 찾기
	int tempmax = 0;
	for (int i = 1; i <= n; i++) {
	if (tempmax < a[i])tempmax = a[i];
	}
	int cnt = 0;
	int idx = 1;
	while (true) {
	if (tempmax / idx == 0)break;
	idx *= 10;
	cnt++;
	}
	//cout << cnt << endl;
	idx = 10;
	for (int i = 1; i <= cnt; i++) {
	deque <int> q[10];
	for (int j = 1; j <= n; j++) {
	int num = (arr[j] % idx) / (idx / 10);
	q[num].push_back(arr[j]);
	}
	idx *= 10;
	int arr_idx = 1;
	for (int j = 0; j <= 9; j++) {
	while (!q[j].empty()) {
	a[arr_idx++] = q[j].front();
	q[j].pop_front();
	}
	}
	}
	}
	int main() {
	int k=0;//계수정렬을 위한 수들의 범위 값
	cin >> n;
	for (int i = 1; i <= n; i++) {
	cin >> arr[i];
	if (!visit[arr[i]]) {
	visit[arr[i]] = true;
	k++;
	}
	}
	//selection_sort(arr);
	//bubble_sort(arr);
	//insert_sort(arr);
	//shell_sort(arr);
	//quick_sort(arr, 1, n);
	//merge_sort(arr, 1, n);
	//heap_sort(arr, n);
	//counting_sort(arr, k);
	//radix_sort(arr);
	Print();
	}

view raw sort.cpp hosted with ❤ by GitHub