개발/Algorithm
-
[Sort]Radix sort(기수 정렬)개발/Algorithm 2022. 6. 30. 17:47
설명 자리수를 비교해서 정렬하는 방식 자리수가 없는 자료형에 대해서는 정렬이 불가능 합니다. 추가적인 메모리가 필요합니다. Conunting Sort와 마찬가지로 비교를 수행하지 않는 알고리즘 입니다. 예제 MSD (Most Significant Digit) : 가장 큰 자릿 수를 의미 LSD (Least Significant Digit : 가장 작은 자릿 수를 의미 방법 1 MSD → LSD 이 방법은 정렬을 수행하기 위해 그룹을 만들어야 한다는 단점이 있습니다. 만약 그룹을 만들지 않고 2번째 자리수를 비교하게 된다면 앞에서 정렬한 자료들의 순서가 엉망이 될 것입니다. 이러한 단점을 극복하고자 다음 방법이 주로 사용됩니다. 방법 2 LSD → MSD 이 방법은 따로 그룹을 만들지 않더라도 정렬이 가능..
-
[Sort]Counting Sort(계수 정렬)개발/Algorithm 2022. 6. 30. 17:23
설명 비교를 하지 않는 알고리즘 Stable Sort(안정 정렬)입니다. 단 정렬하고자 하는 배열의 최댓값이 작을 때 그리고 원소들 간의 차이가 크지 않을 때만 사용 가능합니다. 예제 앞에서부터 배열을 Scan하면서 원소들의 갯수를 파악해 배열에 저장하면 다음 그림과 같게 됩니다. 이를 바탕으로 배열 A를 정렬하면 아래 그림과 같게 됩니다. 그런데 이를 더욱 효율적으로 수행하기 위해 C 배열을 다음과 같이 바꾸어줍니다. C′[i]=∑i0C[i] 그러면 아래와 같은 결과를 얻을 수 있습니다. 마지막 원소는 원소의 총 갯수가 됨을 알 수 있습니다. 이를 이용해 정렬을 하는 방법은 아래와 같습니다. Stable 정렬을 수행하기 위해 맨 뒤에서부터 원소를 탐색합니다. 첫번째 원소는 8..
-
[Sort] Quick Sort(퀵 정렬)개발/Algorithm 2022. 6. 29. 16:46
설명 일반적으로 매우 빠르다고 알려져있는 정렬방법 Divide and Conquer(분할 정복) 방법 Pivot 을 정해 pivot 보다 작은 원소들은 pivot 왼쪽으로 pivot보다 큰 원소들은 pivot 오른쪽으로 정렬합니다. 예제 pivot 이 6으로 선정되어 Quick Sort를 진행하는 예제입니다. i 와 j는 각각 정렬을 수행할 Index를 나타냅니다. i는 증가하는 방향으로 j는 감소하는 방향으로 이동하여 pivot과 비교를 합니다. i에는 pivot보다 작은 원소들이 j에는 pivot보다 큰 원소들이 있도록 합니다. 위 그림을 보면 i에는 pivot보다 큰 8이 j에는 pivot보다 작은 2가 있습니다. 이런 경우에는 i와 j를 스왑(그림 오른쪽)하여 계속 정렬을 진행합니다. 만약 i의 ..
-
[Sort]HeapSort(힙 정렬)개발/Algorithm 2022. 6. 28. 16:12
설명 최소(최대) 힙을 이용해 원소들을 추출하며 정렬을 하는 방법 내림차순 정렬을 위해서는 최대 힙, 오름차순 정렬을 위해서는 최소 힙 힙은 다음 글에 정리 되어 있습니다. → [자료구조]힙(Heap) 예제 결과 Psuedo Code HEAPSORT(A) BUILD_MAX_HEAP(A) for i = A.length downto 2 exchange A[1] with A[i] A.heap_size = A.heap_size - 1 MAX_HEAPIFY(A, 1) BUILD_MAX_HEAP(A) A.heap_size = A.length for i = floor(A.length/2) downto 1 MAX_HEAPIFY(A, i) MAX_HEAPIFY(A, i) if left_child >= right_chil..
-
[Sort]Merge Sort(합병 정렬)개발/Algorithm 2022. 6. 21. 19:17
설명 두개의 정렬된 리스트가 주어졌을 때 두 개의 리스트를 합치면서 정렬하는 방법 Divide and Conquer (분할정복) 알고리즘의 방법이다. 예제 Psuedo Code MERGE_SORT(A, p, r) // A는 정렬할 List p,r은 처음과 끝 index if p < r q = [(p + r) / 2] // 중간값을 찾아 divide and conquer MERGE_SORT(A, p, q) // List의 왼쪽 부분을 정렬 MERGE_SORT(A, q+1, r) // List의 오른쪽 부분을 정렬 MERGE(A, p, q, r) // 왼쪽과 오른쪽을 합치면서 정렬 MERGE(A, p, q, r) //A는 정렬할 List p는 처음 index, r은 마지막 index, q는 중간 index ..
-
[Sort]Insertion Sort(삽입 정렬)개발/Algorithm 2022. 6. 20. 17:27
설명 주어진 키를 정렬된 리스트 중 자신의 위치에 삽입(Insertion)하면서 정렬하는 알고리즘 손 안에 카드를 정렬 하는 것과 유사하다. 예제 Pseudo Code INSERTIONN-SORT(A) for j = 2 to A.length //첫번째 원소는 이미 정렬된 리스트라고 생각해 2번째 원소부터 정렬한다. key = A[j] // 정렬을 수행할 원소 i = j - 1 // 오름차순 정렬 while i > 0 and A[i] > key // j - 1 부터 1 번째 index로 가면서 삽입 될 위치를 찾는다. A[i+1] = A[i] i = i - 1 A[i + 1] = key 시간 복잡도 1. Best Case 7행에 있는 while 문이 실행되지 않는다 → O(N) 2. Worst Ca..