알고리즘
-
알고리즘...19일지 2021. 7. 13. 14:14
퀵 정렬 구현 배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다. QuickSort.hpp #pragma once #include "../Common.hpp" void QuickSort(int arr[], int p, int r, bool printData = false, int n = 0); int Partition(int arr[], int p, int r); /// /// 주어진 배열을 정렬한다. /// /// 정렬을 진행할 배열 /// 배열의 길이 /// 중간 결과 출력 여부 void QuickSort(int arr[], int n, bool printData = false) { if (printData) { Common::PrintArray(arr, n); } QuickSort(ar..
-
알고리즘...18일지 2021. 7. 12. 12:05
퀵 정렬 가장 끝 원소를 기준으로 그보다 작은 원소를 왼쪽에 큰 원소를 오른쪽으로 옮겨 정렬한다. 퀵 정렬 알고리즘 끝 원소를 기준으로 작은 원소를 좌측에 큰 원소를 우측으로 옮기고 좌측 배열과 우측 배열에 대해 같은 과정을 반복한다. 퀵 정렬 알고리즘 QuickSort(A[], p, r) { if (p < r) then { q ← Partition(A, p, r) QuickSort(A, p, q - 1) QuickSort(A, q + 1, r) } } Partition(A[], q, r) { 배열 A[p...r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고 A[r]이 자리한 위치를 리턴한다. } 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘
-
병합 정렬 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 9. 11:44
병합 정렬 입력 배열을 반으로 나누고 나눈 배열을 하나의 배열로 병합하여 정렬을 진행한다. 병합 정렬 알고리즘 배열의 크기를 반으로 나누는 과정을 각각의 크기가 1이 될 때까지 반복하고 이후 각각의 배열을 병합할 때 정렬을 진행한다. 병합 정렬 알고리즘 MergeSort(A[], p, r) { if (p < r) then { q ← └(p + r) / 2┘ MergeSort(A, p, q) MergeSort(A, q + 1, r) Merge(A, p, q, r) } } Merge(A[], p, q, r) { 정렬되어 있는 두 배열 A[p...q]와 A[q + 1...r]을 합쳐 정렬 된 하나의 배열 A[p...r]을 만든다. } ※ 병합 정렬 시 배열을 둘로 나누는 것을 반복할 때 logn, 배열을 다시..
-
알고리즘...17일지 2021. 7. 8. 12:33
병합 정렬 구현 배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다. MergeSort.hpp #pragma once #include "../Common.hpp" void MergeSort(int arr[], int tempArr[], int p, int r, bool printData = false, int n = 0); void Merge(int arr[], int tempArr[], int p, int q, int r); /// /// 주어진 배열을 정렬한다. /// /// 정렬을 진행할 배열 /// 배열의 길이 /// 중간 결과 출력 여부 void MergeSort(int arr[], int n, bool printData = false) { if (printData) { Common:..
-
알고리즘...16일지 2021. 7. 7. 12:02
병합 정렬 입력 배열을 반으로 나누고 나눈 배열을 하나의 배열로 병합하여 정렬을 진행한다. 병합 정렬 알고리즘 배열의 크기를 반으로 나누는 과정을 각각의 크기가 1이 될 때까지 반복하고 이후 각각의 배열을 병합할 때 정렬을 진행한다. 병합 정렬 알고리즘 MergeSort(A[], p, r) { if (p < r) then { q ← └(p + r) / 2┘ MergeSort(A, p, q) MergeSort(A, q + 1, r) Merge(A, p, q, r) } } Merge(A[], p, q, r) { 정렬되어 있는 두 배열 A[p...q]와 A[q + 1...r]을 합쳐 정렬 된 하나의 배열 A[p...r]을 만든다. } 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘
-
삽입 정렬 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 5. 11:31
삽입 정렬 선택 정렬과 버블 정렬과 달리 1개짜리 배열로 시작하여 크기를 하나씩 늘려나가는 방식으로 정렬을 진행한다. 삽입 정렬 알고리즘 배열 A[1...n]에 대해 A[n] < A[i] 인 i를 찾아 A[n]과 A[i]의 자리를 바꾼다. 이 과정을 [1...n]에 대하여 반복한다. 이를 수도 코드로 나타내면 다음과 같다. 삽입 정렬 알고리즘 InsertionSort(A[], n) { for i ← 2 to n { A[1...i]의 적당한 자리에 A[n]을 삽입한다 } } ※ 삽입 정렬 알고리즘의 비교 회수는 n ~ n² 사이가 되며 시간 복잡도는 최선의 경우 Ο(n), 최악의 경우 Ο(n²)이 된다. 삽입 정렬 구현 배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다. InsertionSor..
-
알고리즘...15일지 2021. 7. 4. 17:42
삽입 정렬 구현 배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다. InsertionSort.hpp #pragma once #include "../Common.hpp" /// /// 주어진 배열을 정렬한다. /// /// 정렬을 진행할 배열 /// 배열의 길이 /// 중간 결과 출력 여부 void InsertionSort(int arr[], int n, bool printData = false) { if (printData) { Common::PrintArray(arr, n); } for (int i = 1; i = 0; j--) { if (arr[curIdx] < arr[j]) { Common::S..
-
알고리즘...14일지 2021. 7. 2. 10:13
삽입 정렬 선택 정렬과 버블 정렬과 달리 1개짜리 배열로 시작하여 크기를 하나씩 늘려나가는 방식으로 정렬을 진행한다. 삽입 정렬 알고리즘 배열 A[1...n]에 대해 A[n] < A[i] 인 i를 찾아 A[n]과 A[i]의 자리를 바꾼다. 이 과정을 [1...n]에 대하여 반복한다. 이를 수도 코드로 나타내면 다음과 같다. 삽입 정렬 알고리즘 InsertionSort(A[], n) { for i ← 2 to n { A[1...i]의 적당한 자리에 A[n]을 삽입한다 } } 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘