알고리즘
-
병합 정렬알고리즘/정렬 2021. 12. 25. 00:18
병합 정렬: 모든 원소들이 하나로 남을때까지 정확하게 절반으로 나눈 후 나중에 합쳐서 정렬하는 알고리즘. Ex) (이미 하나까지 전부 반으로 쪼게진 상태라 가정하고 2의 배수만큼 차례대로 합쳐진다.) 7 6 5 8 3 5 9 1 67 58 35 19 5678 1359 13556789 시간 복잡도: O(N*log N) 너비가 n이고 높이가 log n (정렬이 되어있는 상태에서 데이터를 하나씩 읽어나가 새롭게 정렬을 하므로 n * log n에 비례.) 병합 정렬의 경우 항상 정확히 절반으로 분할되고 정복하는 과정이 반복되므로 최악의 경우에도 O(N*log N)을 보장한다. (퀵 정렬은 편향되게 분할 할 가능성이 있으므로 최악의 경우 O(N^2)) 단점: 기존의 데이터를 담을 추가적인 배열 공간이 필요하여 메..
-
퀵 정렬알고리즘/정렬 2021. 12. 25. 00:07
퀵 정렬 : 하나의 큰 문제를 두 개의 작은 문제로 분할하는 정렬 알고리즘이다. 특정한 값을 기준(pivot)으로 큰 숫자와 작은 숫자를 선택해 서로 교환한 뒤 배열을 반으로 나눈다. 일반적으로 pivot은 첫번째 원소부터 설정된다. Ex) pivot을 기준으로 왼쪽에선 큰값을 찾고, 오른쪽에선 작은 값을 찾는다. 3 7 8 1 5 9 6 10 2 4 3 2 8 1 5 9 6 10 7 4 3 2 1 8 5 9 6 10 7 4 (작은 값의 인덱스가 큰 값의 인덱스보다 작아 엇갈릴 때 작은 값과 pivot이 교환되어 첫번째 분할이 일어남.) 1 2 3 8 5 9 6 10 7 4 (3을 기준으로하여 왼쪽의 집합과 오른쪽의 집합에서 각각 pivot이 정해진 뒤 정렬을 수행함.) 위의 과정 반복 1 2 3 8 5..
-
삽입 정렬알고리즘/정렬 2021. 12. 24. 23:50
삽입 정렬: 각 숫자를 적절한 위치에 삽입하는 정렬 알고리즘. 반복적으로 새로운 원소를 이미 정렬된 데이터에 필요할 때만 그 위치를 정해주어 그 곳으로 넣어주는 것이 핵심이다. Ex) 1 10 5 8 7 6 4 3 2 9 1 5 10 8 7 6 4 3 2 9 1 5 8 10 7 6 4 3 2 9 1 5 7 8 10 6 4 3 2 9 ~ 1 2 3 4 5 6 7 8 9 10 시간복잡도 : O(N^2) 삽입 정렬은 앞에 정렬되어 있는 것을 알고있는 상황을 가정하므로 적절한 위치에 삽입만 하기때문에 O(N^2) 정렬 알고리즘 중에서는 효율적인 편임. (거의 정렬된 상태라면 모든 정렬 알고리즘에서도 굉장히 효율적.) Ex) 2 3 4 5 6 7 8 9 10 1 (이미 정렬되어 있으므로 한번씩만 비교하고 마지막 ..
-
버블 정렬알고리즘/정렬 2021. 12. 24. 23:47
버블 정렬: 옆에 있는 값과 비교해서 작은 값을 앞으로 보내기 사이클이 돌때마다 가장 큰 값이 맨뒤로 이동하게 된다. Ex) 1 10 5 8 7 6 4 3 2 9 1 5 8 7 6 4 3 2 9 10 1 5 7 6 4 3 2 8 9 10 ~ 1 2 3 4 5 6 7 8 9 10 시간 복잡도 : O(N^2) 구현은 쉬우나 가장 비효율적인 정렬 알고리즘. 실제로 선택정렬과 시간 복잡도는 같으나 수행 시간이 더 오래걸리는 이유 선택 정렬은 최솟값을 선택하여 마지막에만 스왑을 하지만 버블 정렬의 경우 비교 연산과 스왑을 사이클마다 수행하므로 연산 횟수가 사실상 훨씬 더 많아진다. #include int main() { int i, j, temp; int array[10] = {1, 10, 5, 8, 7, 6, ..
-
선택 정렬알고리즘/정렬 2021. 12. 24. 23:42
선택 정렬: 가장 작은 것을 반복적으로 선택하여 제일 앞으로 보내는 정렬 알고리즘. 정렬이 안된 숫자들 중에서 최소값을 선택하여 배열의 맨 앞쪽 요소와 교환한다. Ex) 정렬할 데이터 : 1 10 5 8 7 6 4 3 2 9 1 2 5 8 7 6 4 3 10 9 1 2 3 8 7 6 4 5 10 9 1 2 3 4 7 6 8 5 10 9 ~ 1 2 3 4 5 6 7 8 9 10 시간복잡도 : O(N^2) 최악의 경우 연산의 횟수가 기하급수적으로 늘어나므로 비효율적인 정렬 알고리즘. #include #include int main() { int i, j, min, index, temp; // index : 가장 작은 원소가 존재하는 위치 int array[10] = {1, 10, 5, 8, 7, 6, 4, ..