| 버블 정렬 비교 횟수 | 3n(n-1) / 4 | 시간복잡도 O(n^2) 으로 효율이 좋지않은 알고리즘 |
| 단순 선택 정렬 비교 횟수 | n(n-1) / 2 | |
| 단순 삽입 정렬 비교 횟수 | n^2 /2 |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
#include <iostream>
#define Swap(type, x, y) do{type t = x; x = y; y = t;} while(0)
using namespace std;
//버블정렬
void Swap_1(int iArr[], int n)
{
for (int i = 0; i < n - 1; ++i)
{
for (int j = n - 1; j > i; --j)
{
if (iArr[j - 1] > iArr[j])
Swap(int, iArr[j - 1], iArr[j]);
}
}
}
//알고리즘 개선된 버블정렬
void Swap_2(int iArr[], int n)
{
for (int i = 0; i < n - 1; ++i)
{
int exchg = 0;
for (int j = n - 1; j > i; --j)
{
if (iArr[j - 1] > iArr[j])
{
Swap(int, iArr[j - 1], iArr[j]);
++exchg;
}
}
if (exchg == 0) break;
}
}
//알고리즘 더 개선된 버블정렬
void Swap_3(int iArr[], int n)
{
int k = 0;
while (k < n - 1)
{
int last = n - 1;
int j = 0;
for (int j = n - 1; j > k; --j)
{
if (iArr[j - 1] > iArr[j])
{
Swap(int, iArr[j - 1], iArr[j]);
last = j;
}
}
k = last;
}
}
//단순 선택 정렬___최솟값을 골라 앞에서부터 순차적으로 넣어줌
// 서로 떨어져있는 요소를 뒤바꾸는거라 안정적이지 않다.
void selection(int iArr[], int n)
{
int i, j;
for (i = 0; i < n - 1; ++i) //반복수 n-1
{
int min = i;
for (j = i + 1; j < n; j++) //n-1까지 검사
{
if (iArr[j] < iArr[min]) //최솟값 구하기
{
min = j;
}
}
Swap(int, iArr[i], iArr[min]);
}
}
//단순 삽입 정렬___i는 1부터 시작하여 앞의 수랑 비교해서 앞보다 작을경우 앞의 수를 i위치에 넣어줌
//원래 값을 담을 또다른 변수 필요
//그변수를 마지막에 작지 않을 경우 그자리에 넣어줌 //같은 값이 나와도 순서는 그대로라서 안정적이다.
//셔틀정렬
void insert(int iArr[], int n)
{
int i, j;
for (i = 1; i < n; ++i)
{
int tmp = iArr[i];
for (j = i; j > 0 && iArr[j - 1] > tmp; --j)
{
iArr[j] = iArr[j - 1];
}
iArr[j] = tmp;
}
}
|
cs |
'알고리즘' 카테고리의 다른 글
| [알고리즘] 스택 (0) | 2021.10.01 |
|---|---|
| [알고리즘] 선형검색 문제 (0) | 2021.10.01 |
| [알고리즘] 이진검색 (0) | 2021.10.01 |
| [알고리즘] 선형검색 (0) | 2021.10.01 |
| [알고리즘] 구조체 (0) | 2021.09.30 |