1. 정렬
|
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
|
#include <iostream>
#include <string>
using namespace std;
const int SIZE = 99;
void sort(double arr[], int low, int mid, int high) {
int j = mid + 1;
int i = low;
int i_i = 0;
double result[99];
while (i <= mid && j <= high) {
if (arr[i] > arr[j]) {
result[i_i++] = arr[j++];
} else {
result[i_i++] = arr[i++];
}
}
while (j <= high) {
result[i_i++] = arr[j++];
}
while (i <= mid) {
result[i_i++] = arr[i++];
}
for (i = low, i_i = 0; i <= high; i++, i_i++) {
arr[i] = result[i_i];
}
}
void merge(double arr[], int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2;
merge(arr, low, mid);
merge(arr, mid + 1, high);
sort(arr, low, mid, high);
}
}
int main() {
double arr[SIZE] = {11.04,3.09,09.16,1.30,7.06,1.17,5.19,10.16,8.28,
11.29,7.10,04.28,10.12,05.18,12.29,5.12,09.08,9.07,7.04,
10.25,9.05,7.19,3.09,1.20,3.28,9.25,12.01,3.05,
1.19,4.28,10.04,12.31,4.25,12.04,11.28,3.10,6.08,
5.29,6.16,10.29,5.18,5.22,10.23,8.23,3.26,1.20,
10.28,1.27,4.07,12.19,7.02,2.02,5.01,1.12,12.16,
9.02,2.07,4.02,12.21,9.13,9.25,1.19,8.02,3.03,4.11,1.28,6.09,
2.20,6.20,6.23,1.01,8.12,5.25,2.25,12.05,11.21,11.15,10.19,8.21,12.29,9.05,1.09,2.07,9.27,
1.14,3.28,1.15,10.19,6.03,11.15,2.22,9.03,6.14,7.19,8.02,4.20,5.31};
merge(arr,0,SIZE-1);
for (int i=0;i<99;i++){
cout<<arr[i]<<" ";
}
}
|
cs |
정렬 돼있지 않은 배열을 병합 정렬로 정리해주었다.
find, insert,delete는 정렬된 배열과 아닌 배열 둘 다 따로 함수를 써야한다.
반면에 정렬된 배열은 find_min, find_max에서 0번째와 마지막 인덱스의 값만 반환해주면 된다
example code
|
1
2
3
4
5
6
7
8
|
merge(arr,0,SIZE-1);
//find_min
cout<<arr[0]<<endl;
//find_max
cout<<arr[SIZE-1]<<endl;
//find_next,prev
cout<<arr[n+1]<<arr[n-1]<<endl;
|
cs |
(메인 함수에 추가만 해주면 됨)
|
1
2
3
4
5
6
7
8
9
10
11
|
double find(double arr[],double a){
double a;
for(int i=0;i<SIZE;i++){
if(arr[i]==a){
return a;
}
else{
return 0;
}
}
}
|
cs |
(메인함수 밖에서 따로 선언해서 구현해줘야 함)
2. 시간 복잡도와 linked list vs array
1) n개의 노드에서의 트리에서 노드가 균등하게 분포돼있다고 가정,
이때의 최소 높이가 됨
2) 1부터 n까지 높이를 구해보면 대략 lg(n)이 되고
위처럼 평균을 구하게 되면 저렇게 식이 나오게 됨
2) linked list와 array
array 는 처음부터 메모리에 공간을 할당해주고 변수가 지정될 장소, 장소의 주소까지 지정된다.
이와 다르게 linked list(이하 연결리스트)는 동적할당으로 메모리에 공간을 유동적으로 할당받고,
장소와 장소의 주소는 랜덤으로 지정받으며 요소의 장소는 노드에 직접 접근해야 알 수 있다.
따라서 둘의 장단점이 갈리고 무엇을 할 때 쓰느냐에 따라 쓰임이 다르다.
메모리를 유동적으로 줄이고 늘릴 수 있는 delete, insert같은 연산에서 연결리스트가 선호되고,
메모리가 정해져있고 이에 따라 주소까지 정해져 접근이 쉬운 array에서 find같은 함수가 선호된다.
'ASSINGMENT > 알고리즘' 카테고리의 다른 글
| [과제] 4주차 과제(2) - quick, tuple sorting (0) | 2023.04.01 |
|---|---|
| [과제] 알고리즘 2주차 과제 (0) | 2023.03.13 |
| Problem set 1 (0) | 2023.03.07 |