20210704
1.버블정렬
bubble sort 라고도 하고 가장 무지성 정렬인것.
#include <iostream>
using namespace std;
void bubblesort(int arr[]) {
int temp = 0;
for (int i = 0; i < 5; i++) { //n
for (int j = 0; j < i; j++) { //n-1
if (arr[j] < arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
/*
* 처음엔 n개를 비교함.
* 그다음엔 n-1개 비교함.
* ...
* O(n^2)
*/
int main() {
int arr[5] = { 7,4,5,1,3 };
bubblesort(arr);
for (int w = 0; w < 5; w++) {
cout << arr[w];
}
}배열에
<0,1,2,3,4>
<7,4,5,1,3> 이라고 들어가있으면
0번칸 7하고 1번칸 4하고 비교해서
7이 4보단 크니까
temp에 집어넣어서 바꿔주고 (또는 swap을 이용하던가)
그걸 배열의 끝까지 반복하는 정렬방법이다.
장점 : 쉬움.
단점 : 인접한 요소랑 교환하기에 하나가 가장 왼쪽에서 오른쪽 가려면 다른애들 다 건드려야함. 교환이 이동보다 복잡하기에 잘 안씀.
시간복잡도 : n번만큼 하고 그다음엔 n-1번만큼 하고 이게 반복이니까 시간복잡도는 O(n^2)을 가진다.
2.Counting Sort
#include <iostream>
using namespace std;
# define max 100
void counting_sort(int* arr, int size) { //배열과 배열크기를 넘겨받음
int count[max] = { 0, }; //100개까지만 받겠슴
for (int i = 0; i < max; i++) {
count[i] = 0; // 초기화
}
for (int i = 0; i < size; i++) {
count[arr[i]]++; // 갯수세기
}
for (int i = 0; i < max; i++) {
for (int j = 0; j < count[i]; j++) {
cout << " "<< i;
} // 출력
}
}
int main() {
int arr[] = { 1,1,0,1,0,2,3,4,5,1,1,5,4,3,2,5,4,1,1,4,5,2,3,3,2,1,4,4,1,2 };
int size = sizeof(arr)/4 ; //크기 는 배열크기 입니다.
//sizeof(arr) -> 메모리크기
//cout << size << endl;
counting_sort(arr, size);
return 0;
}이 배열은 버블소트마냥 그러기보단 같은게 반복될때 사용하면 더 좋다.
1,1,0,1,0,2,3,4,5,1,1,5,4,3,2,5,4,1,1,4,5,2,3,3,2,1,4,4,1,2 이렇게 있으면
0은 몇개 1은 몇개 2는 몇개... 이렇게 세는것이 카운팅소트이다.
끝까지 다 읽어오기에 이친구 시간복잡도는 O(n^2).
처음에 안보고
#include <iostream>
using namespace std;
void counting_sort(int arr[], int a) {
int size = a;
int counting_arr[7] = { 0, };
for (int i = 0; i < size; i++) {
if (i = arr[i]) {
counting_arr[i] += arr[i];
}
}
}
int main() {
int arr[14] = { 0,0,1,1,1,2,2,3,3,3,3,4,4,5 };
int len = sizeof(arr);
cout << "초기배열"<< endl;
for (int q = 0; q < len; q++) {
cout << arr[q] << endl;
}
cout <<"size of arr" << len << endl;
counting_sort(arr, len);
for (int q = 0; q < len; q++) {
cout << arr[q] << endl;;
}이렇게 구현했더니 결과값이
초기배열
0
0
1
1
1
2
2
3
3
3
3
4
4
5
-858993460
1536147693
16382964
4010115
1
19681432
19685080
1
19681432
19685080
16383056
4009687
1536149353
4001827
4001827
17571840
0
0
0
0
0
0
0
0
4048256
4048268
0
16382972
0
16383164
4017440
1531676937
0
16383064
4009325
16383072
4010248
16383088
1979906601
17571840
1979906576
16383180
size of arr56이따구로 나와서 개고생했는데
main문 內 사이즈 해주는걸
int len = sizeof(arr);
이렇게 하지말고
int len = sizeof(arr)/4;
를 해줬어야 했다.
int값이 4여서 그냥 했으면 120개나 나왔기 때문이다.
3. 삽입정렬 selection sort
쭈르르르 읽어보다가
젤 작은걸 새 배열에 가장 앞에 쑤셔넣는 방법이다.
#include <iostream>
using namespace std;
void selection_sort(int arr[]) {
int indexMin, temp;
for (int i = 0; i < 5 - 1; i++) {
indexMin = i;
for (int j = i + 1; j < 5; j++) {
if (arr[j] < arr[indexMin]) {
indexMin = j;
}
}
temp = arr[indexMin];
arr[indexMin] = arr[i];
arr[i] = temp;
}
}
int main() {
int arr[5] = { 9,6,7,3,5 };
selection_sort(arr);
for (int q = 0; q < 5; q++) {
cout << arr[q] << endl;;
}
}이친구도 어쨌든 끝까지 읽어보는 친구여서
n, n-1, ... 이기에 시간복잡도는 O(n^2)
4. 기수정렬 Radix sort
오늘의 하이라이트. 이해하기 어려웠음.
12,15,42,30,51,32,45,35,65,56,71,13,17,28,39,44
이런 난수들이 있다고 치면
일단 가장 긴 친구를 고른다.
그리고 가장 작은 수부터 가장 큰 수까지 카운팅소트를 해준다.
지금은 다 10의자리수니까 2라고 잡고
일단 전부 일의자리수를 기준으로 정렬을 한다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 30 | 51 | 12 | 13 | 44 | 15 | 56 | 17 | 28 | 39 |
| 71 | 32 | 35 | |||||||
| 42 | 45 | ||||||||
| 65 |
대신 이걸 한줄에 집어넣어야 한다.
Queue*를 활용한다.
큐는 선입 선출이다.
a b c d e 가 있으면
앞에서부터 a b c d e 집어넣고
뺄땐 a b c d e 순서대로 나온다. 유통기한 생각하면 편함. 마트나 편의점 정렬방식이다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 30 | 51,71 | 12,32,42 | 13 | 44 | 15,35,45,65 | 56 | 17 | 28 | 39 |
이렇게 들어가있는것이다.
이걸 다시 십의자리에 집어넣으면
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 12 13 17 |
28 | 30 32 35 39 |
44 45 |
51 56 |
65 |
이렇게 깔끔쓰하게 정렬되고
그냥 이걸 앞에서부터 긁으면서 순서대로 뽑아오면 되는 것이다.
그러면 12 13 17 28 30 32 35 39 44 45 51 56 65 이렇게 깔끔하고 빠르게 나온다. 왜냐면 한번만 읽어오면 충분하기 때문이다.
#include <iostream>
#include <queue>
using namespace std;
int get_radixsort(int* arr, int size) {
int max = 0;
for (int i = 0; i < size; i++) { //젤큰거찾기
if (max < arr[i]) {
max = arr[i];
}
}
int jaresu = 1;
while ((max / 10) > 0) {
max = max / 10;
jaresu*=10;
}
//자릿수 세기
return jaresu;
}
void radixsort(int* arr, int size) {
int new_arr[30] = { 0, };
int output = 0; // 출력
int max_jaresu = get_radixsort(arr, size);
cout << endl << "max" << max_jaresu << endl;
queue<int> Q[10]; // queue 에 열개나 집어넣기
for (int i = 1; i <= max_jaresu; i*=10) { // 10씩 곱하면서 max_jaresu까지.
for (int j = 0; j < size; j++) { //배열 Index
int q = 0; //num
if (arr[j] >= i) {
q = (arr[j] / i) % 10; // 10씩 나누기. 나머지는 버림.
}
Q[q].push(arr[j]); // 맞는지 보고 집어넣기.
}
output = 0; /*
*/
for (int e = 0; e < 10; e++) { //새로 돌리면서
while (!Q[e].empty()) { //큐가 빌 때 까지
arr[output] = Q[e].front(); //처음꺼 빼고
Q[e].pop(); //지워주는것.
output++;
}
}
}
}
int main() {
int arr[] = { 123,12,15,145,13,15,21,354,15,48,53,12,53,12,45,8,56,35,15,45,32,15,18,563,2,15,24,15,78,65 };
int size = sizeof(arr)/4;
radixsort(arr, size);
for (int i = 0; i < size; i++) {
cout << arr[i] << endl;
}
}정렬속도는 제일 빠르지만 데이터 전체 크기에 테이블만큼의 메모리가 더 필요한게 단점이다.
시간복잡도는 O(n).
'_스타디 > 알고리'듬'' 카테고리의 다른 글
| 03_stack&queue 스텍 큐 (0) | 2021.07.16 |
|---|---|
| 03-divide and conquer -Quick sort (0) | 2021.07.08 |
| 02-Divide_and_Conquer_분할정복 (0) | 2021.07.06 |
