반응형 CS/자료구조11 [자료구조] 기수정렬(Radix Sort) 기수정렬이란 - 데이터들의 값을 비교연산을 하지 않는 알고리즘이다. - 데이터를 구성하는 기본요소, 즉 기수를 이용하여 정렬을 진행하는 방식이다. - 낮은 자리부터 정렬하는 LSD, 높은자리부터 정렬하는 MSD가 있다. - MSD는 추가적인 연산을 필요로 하기때문에 LSD를 선호한다. 단점 - 자릿수가 없는 것은 정렬할 수 없다.(부동 소숫점) - 중간 결과를 저장할 bucket 공간이 필요하다. - 시간복잡도 : O(n) void countSort(int arr[], int n, int exp) { int buffer[n]; int i, count[10] = {0}; // exp의 자릿수에 해당하는 count 증가 for (i = 0; i < n; i++){ count[(arr[i] / exp) % 1.. 2024. 1. 15. [자료구조] 퀵 정렬(Quick Sort) 퀵 정렬이란 - 분할 정복 방법을 통해 주어진 배열을 정렬한다.(분할, 정복, 결합) 과정 1. 배열 가운데서 하나의 원소를 골라 피벗(pivot)이라고 정한다. 2. 피벗 앞에는 피벗보다 우선순위가 높은 원소들이 오고, 피벗 뒤에는 우선순위가 낮은 원소들이 오도록 분할 한다. 3. 이렇게 두구역으로 나눈뒤 해당 구역에서의 피벗을 정하여 이과정을 재귀적으로 반복한다. - 이미 정렬되어있는 리스트에서 가장 최악의 시간복잡도를 갖게된다. O(n^2) - 평균적인 시간복잡도 : O(nlog2n) # include # define MAX_SIZE 9 # define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) ) // 1. 피벗을 기준으로 2개의 부분 리스트로 나눈.. 2024. 1. 15. [자료구조] 병합 정렬(Merge Sort) 병합 정렬이란 - 합병 정렬이라고도 부른다. - 분할 정복 방법을 통해 구현된다.(분할, 정복, 결합) -.연결리스트가 아닌 배열일 경우 임시 메모리가 필요하다는 단점이 있다. - 하나의 리스트를 반으로 쪼개고, 쪼개고, 쪼개서 1개의 값들로 나눈다음 나눈값들을 합치면서 정렬을 한다. - 시간 복잡도 : O(nlog2n) # include # define MAX_SIZE 8 int sorted[MAX_SIZE] // 추가적인 공간이 필요 // i: 정렬된 왼쪽 리스트에 대한 인덱스 // j: 정렬된 오른쪽 리스트에 대한 인덱스 // k: 정렬될 리스트에 대한 인덱스 /* 2개의 인접한 배열 list[left...mid]와 list[mid+1...right]의 합병 과정 */ /* (실제로 숫자들이 정렬되.. 2024. 1. 15. [자료구조] 힙 정렬(Heap Sort) 먼저, 힙이란 - 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 이 힙을 사용하여 정렬하는 알고리즘이 힙 정렬이다. - 힙의 루트노드에 저장된 값이 가장 커야한다. - 힙의 루트 노드에 저장된 값이 정렬 순서상 가장 앞선다. - 마지막 노드의 값을 부모와 비교하여 자식 노드의 값이 우선순위가 더 높다면 부모노드와 자리를 바꾸는 방식으로 정렬을 진행한다. - 삽입 : 새로운 노드를 힙의 마지막 노드에 삽입한 후 부모 노드들과 비교하여 정렬한다. - 삭제 : 힙의 최대값인 루트노드가 삭제되고 마지막 노드가 루트노드로 옮겨진다. 이후 루트노드를 자식노드와 비교하며 정렬한다. - 시간 복잡도 : O(nlog2n) private void solve() { int[] array = { 230.. 2024. 1. 15. 이전 1 2 3 다음 반응형