정렬
-
특수 정렬 알고리즘프로그래밍 기초/알고리즘 2021. 7. 21. 14:56
특수 정렬 알고리즘 두 원소를 비교하여 정렬하는 경우엔 수행 시간인 Ο(nlogn) 보다 빨라질 수 없다. 그러나 입력 값이 특수한 성질을 만족하는 경우 이러한 한계를 넘을 수 있는 알고리즘이 존재한다. 기수 정렬 입력이 모두 k 이하의 자릿수를 가진 자연수인 경우 사용할 수 있는 정렬 방법으로 Θ(n) 이 소요되는 알고리즘이다. 기수 정렬 알고리즘 RadixSort(A[], n, k) { for i ← 1 to k { i 번째 자리수에 대해 A[1...n]을 안정성을 유지하면서 정렬한다. } } ※ 안정성을 유지한다는 것은 비교한 결과가 같으면 자리가 유지되어야 한다는 의미이다. 계수 정렬 입력의 값이 모두 Ο(n)을 넘지 않는 경우 사용할 수 있는 정렬 방법으로 Θ(n) 이 소요되는 알고리즘이다. 계..
-
힙 정렬 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 18. 11:25
힙 정렬 루트에 항상 가장 큰 값(혹은 가장 작은 값)이 오도록 정렬되는 힙을 사용하는 정렬 방식이다. 힙 만들기 입력되는 배열을 완전 이진트리로 가정하여 힙을 생성한다. 힙 생성 알고리즘 BuildHeap(A[], n) { for i ← └n / 2┘ downto 1 { Heapify(A, i, n); } } Heapfipy(A[], k, n) { left ← 2k; right ← 2k + 1; // 작은 자식 고르기 if (right ≤ n) then { if (A[left] < A[right]) then { smaller ← left; } else { smaller ← right; } } // 왼쪽 자식만 있는 경우 else if (left ≤ n) then { smaller ← left; } //..
-
퀵 정렬 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 14. 12:29
퀵 정렬 가장 끝 원소를 기준으로 그보다 작은 원소를 왼쪽에 큰 원소를 오른쪽으로 옮겨 정렬한다. 퀵 정렬 알고리즘 끝 원소를 기준으로 작은 원소를 좌측에 큰 원소를 우측으로 옮기고 좌측 배열과 우측 배열에 대해 같은 과정을 반복한다. 퀵 정렬 알고리즘 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]이 자리한 위치를 리턴한다. } ※ 퀵 정렬의 시간 복잡도는 모든 원소들이 한쪽으로 몰리는 최악의 경우 Ο(n²), 평균적으로 Ο(nl..
-
병합 정렬 구현 및 테스트프로그래밍 기초/알고리즘 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, 배열을 다시..
-
삽입 정렬 구현 및 테스트프로그래밍 기초/알고리즘 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..
-
버블 정렬 구현 및 테스트프로그래밍 기초/알고리즘 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²)이다. 버블 정렬..
-
선택 정렬 구현 및 테스트프로그래밍 기초/알고리즘 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) 퀵 정렬 특정 값을 기준으로 영역을 나누..