본문 바로가기
반응형

전체 글109

[자료구조] 병합 정렬(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.
[자료구조] 삽입정렬(Insertion Sort) 삽입정렬이란 - 선택 정렬과 유사하지만, 좀 더 효율적인 정렬 알고리즘이다. - 2번째 원소부터 시작하여 그앞에있는 원소들과 비교해서 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하는 정렬 알고리즘이다. - 손안의 카드를 정렬하는 방법과 유사하다. - 시간 복잡도 : O(n^2) # include # define MAX_SIZE 5 // 삽입 정렬 void insertion_sort(int list[], int n){ int i, j, key; // 인텍스 0은 이미 정렬된 것으로 볼 수 있다. for(i=1; i=0 && list[j]>key; j--){ list[j+1] = list[j]; // 레코드의 오른쪽으로 이동 } list[j+1] = key; } } void ma.. 2024. 1. 15.
[자료구조] 선택정렬(Selection Sort) 선택정렬이란 - 버블정렬과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. - 첫번째 자료를 두번째 자료부터 마지막 자료까지 차례대로 비교해가면서 가장 우선순위가 높은 값을 찾아 배열 첫번째에 위치 시키고 원래 해당 자리에 있던 원소와 자리를 바꾼다. - 시간 복잡도 : O(n^2) # include # define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) ) # define MAX_SIZE 5 // 선택 정렬 void selection_sort(int list[], int n){ int i, j, least, temp; // 마지막 숫자는 자동으로 정렬되기 때문에 (숫자 개수-1) 만큼.. 2024. 1. 15.
반응형

티스토리툴바