알고리즘
-
버블 정렬 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 1. 21:16
버블 정렬 선택 정렬과 비슷하게 가장 큰 원소를 가장 끝의 자리로 옮기는 정렬이다. 다만, 이동시키는 방식이 바로 오른쪽 값과 비교하여 교체해주는 것으로 선택 정렬과 차이를 갖는다. 버블 정렬 알고리즘 배열 A[1...n]에 대해 A[1] > A[2] 인 경우 A[1]과 A[2]의 자리를 바꾼다. 이 과정을 [1...n]에 대하여 반복한다. 이를 수도 코드로 나타내면 다음과 같다. 버블 정렬 알고리즘 BubbleSort(A[], n) { for last ← n downto 2 { for i ← 1 to last - 1 { if (A[i] > A[i+1]) then { A[i] ↔ A[i+1] } } } } ※ 버블 정렬 알고리즘의 비교 회수는 n(n-1)/2 이며 시간 복잡도는 Ο(n²)이다. 버블 정렬..
-
알고리즘...13일지 2021. 6. 30. 19:41
버블 정렬 구현 배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다. BubbleSort.hpp #pragma once #include "../Common.hpp" /// /// 주어진 배열을 정렬한다. /// /// 정렬을 진행할 배열 /// 배열의 길이 /// 중간 결과 출력 여부 void BubbleSort(int arr[], int n, bool printData = false) { if (printData) { Common::PrintArray(arr, n); } for (int i = 1; i arr[j + 1]) { Common::Swap(arr, j, j + 1); } } i..
-
알고리즘...12일지 2021. 6. 28. 14:40
버블 정렬 선택 정렬과 비슷하게 가장 큰 원소를 가장 끝의 자리로 옮기는 정렬이다. 다만, 이동시키는 방식이 바로 오른쪽 값과 비교하여 교체해주는 것으로 선택 정렬과 차이를 갖는다. 버블 정렬 알고리즘 배열 A[1...n]에 대해 A[1] > A[2] 인 경우 A[1]과 A[2]의 자리를 바꾼다. 이 과정을 [1...n]에 대하여 반복한다. 이를 수도 코드로 나타내면 다음과 같다. 버블 정렬 알고리즘 BubbleSort(A[], n) { for last ← n downto 2 { for i ← 1 to last - 1 { if (A[i] > A[i+1]) then { A[i] ↔ A[i+1] } } } } 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘
-
선택 정렬 구현 및 테스트프로그래밍 기초/알고리즘 2021. 6. 25. 14:43
선택 정렬 여러 정렬 알고리즘 중 가장 간단한 알고리즘 중 하나이다. 선택 정렬 알고리즘 배열 A [1... n]에서 가장 큰 원소를 찾아 A [n]과 자리를 바꾼다. 이 과정을 [1... n-1]에 대해 반복한다. 이를 수도 코드로 나타내면 다음과 같다. 선택 정렬 알고리즘 SelectionSort(A[], n) { for last ← n downto 2 { A[1...last] 중 가장 큰 수 A[k]를 찾는다. A[k] ↔ A[last] } } ※ 선택 정렬 알고리즘의 비교 회수는 n(n-1)/2 이며 시간 복잡도는 Ο(n²)이다. 선택 정렬 구현 배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다. SelectionSort.hpp #pragma once #include "../Commo..
-
정렬 알고리즘 개요프로그래밍 기초/알고리즘 2021. 6. 23. 08:26
정렬 알고리즘 정렬이란? n개의 원소를 순서대로 배열하는 것으로 실생활에 다양하게 사용되는 알고리즘이다. 가령 학생을 키 순서대로 줄을 세운다거나 세무서에서 고지서를 날리기 위해 주민등록 번호순으로 정렬하는 것 등을 예로 들 수 있다. 정렬의 종류 정렬에는 여러 종류가 있으며 대표적으로 다음과 같은 정렬이 존재한다. 선택 정렬 가장 큰 원소 또는 가장 작은 원소를 찾아 첫 위치 또는 마지막 위치와 자리를 바꾸는 정렬, 평균 Ο(n²) 버블 정렬 두 개의 원소를 비교하여 정렬 방향에 따라 서로 자리를 바꾸는 연산을 반복하는 정렬, 평균 Ο(n²) 병합 정렬 원소를 두 구역으로 나누는 것을 반복한 뒤 병합하며 자리를 바꾸는 연산을 반복하는 정렬, 평균 Ο(nlogn) 퀵 정렬 특정 값을 기준으로 영역을 나누..
-
알고리즘...11일지 2021. 6. 22. 21:40
테스트용 난수 생성 및 시간 체크 함수 구현 알고리즘의 효율성 테스트를 위해 1,000,000 개의 난수를 생성하여 텍스트 파일로 저장 및 불러오기 함수 구현 common.hpp #pragma once #include #include #include #define MAKE_RANDOM_NUMBERS #ifdef MAKE_RANDOM_NUMBERS #include #include #endif namespace Common { #ifdef MAKE_RANDOM_NUMBERS int* GenerateRandomNumber(int n = 100'000) { std::default_random_engine randomEngine; std::uniform_int_distribution distribution(0, ..
-
알고리즘...10일지 2021. 6. 16. 10:44
선택 정렬_계속 위 알고리즘을 실제 구현하고 과정을 살펴보면 다음과 같다. SelectionSort.hpp #pragma once #include "../Common.hpp" void SelectionSort(int arr[], int n) { Common::PrintArray(arr, n); for (int i = 1; i < n; i++) { int biggest{ n - i }; for (int j = 0; j < n - i; j++) { if (arr[biggest] < arr[j]) { biggest = j; } } Common::Swap(arr, biggest, n - i); Common::PrintArray(arr, n); } } main.cpp #include "Sort/SelectionS..
-
알고리즘...9일지 2021. 6. 14. 12:38
선택 정렬 모든 정렬 알고리즘 중 가장 간단한 알고리즘으로 배열 A [1... n]에서 가장 큰 원소를 찾아 A [n]과 자리를 바꾸고 [1... n-1]에 대해 이전 과정을 반복하여 정렬을 마무리한다. 선택 정렬 알고리즘 SelectionSort(A[], n) { for last ← n downto 2 { A[1...last] 중 가장 큰 수 A[k]를 찾는다. A[k] ↔ A[last] } } 이 알고리즘의 수행 시간은 for 루프에 비례하는데 이 루프는 n ~ 2까지 반복하므로 총 비교 회수는 n(n-1)/2 이므로 Θ(n²)이 된다. 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘