알고리즘/정렬
-
계수 정렬알고리즘/정렬 2021. 12. 25. 00:32
계수 정렬: 범위 조건이 있는 경우에 한해 빠른 정렬 알고리즘 크기를 기준으로 개수를 세는 알고리즘이며, 모든 데이터에 한번씩만 접근하면 된다는 점에서 효율적이라 할 수 있음. 그러나, 데이터의 크기가 한정되어 있을 때에 한해서만 사용할 수 있음. 시간 복잡도: O(N) 앞에서 차례대로 데이터를 하나씩 읽어 주기만하면 되므로 N에 비례하는 시간 복잡도를 가진다. #include int main() { int temp; int count[5]; // 범위 기준 : 1~5 int arr[30] = { 1, 3, 2, 4, 3, 2, 5, 3, 1, 2, 3, 4, 4, 3, 5, 1, 2, 3, 5, 2, 3, 1, 4, 3, 5, 1, 2, 1, 1, 1 }; for(int i = 0; i
-
힙 정렬알고리즘/정렬 2021. 12. 25. 00:27
heap : 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리. 최대 힙 : 부모 노드가 자식 노드의 값보다 더 큰 힙 (최소 힙은 이와 반대) 힙 정렬(오름차순 기준)을 하기 위하여 힙 구조를 가지도록 만들어야 하며, 최대 힙이 아닌 경우 힙 생성 알고리즘을 통해 부모 노드와 부모 노드보다 더 큰 값을 가지는 자식노드를 바꿔주는 과정을 거친다. Heapify algorithm : 특정 노드의 두 자식 중 더 큰 자식과 자신의 위치를 바꾸는 알고리즘 처음에 최대 힙 구조를 만든다. 루트 노드와 마지막 원소를 바꿔준 후 집합의 크기를 감소시킨다. 가장 큰 값이 마지막 원소로 바뀌면서, 이 원소를 제외하고 다시 힙 구조를 형성하여 2, 3번의 과정이 반복되면 마지막에 힙 정렬이 ..
-
병합 정렬알고리즘/정렬 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, ..