알고리즘/Sort
-
Merge / Quick / Heap Sort (Medium)알고리즘/Sort 2021. 1. 5. 16:22
출처(위키피디아/GeeksforGeeks) 1. Merge Sort(병합 정렬) - 분할 정복 알고리즘. - 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할한다. (원소가 하나인 리스트는 정렬된 것과 같으므로) - 부분 리스트가 하나만 남을때까지 반복해서 병합하며 정렬된 부분리스트를 생성한다. - 마지막 남은 부분리스트가 정렬된 리스트이다. - Stable / Not in place 최악 시간복잡도 Θ( n log n ) 최선 시간복잡도 Θ( n log n ) 평균 시간복잡도 Θ( n log n ) 공간 복잡도 Θ( n ) void merge(int arr[], int l, int m, int r){ int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n..
-
Selection / Bubble / Insertion Sort (Easy)알고리즘/Sort 2021. 1. 4. 23:19
출처(위키피디아/GeeksforGeeks) 1. Selection Sort(선택 정렬) - 주어진 리스중에 최소값을 찾는다. - 그 값은 맨 앞에 위치한 값과 교체한다. - 맨 처음을 제외한 나머지 리스트를 같은 방법으로 교체한다. - Unstable / In-place 최악 시간복잡도 Θ( n ^2 ) 최선 시간복잡도 Θ( n ^2 ) 평균 시간복잡도 Θ( n ^2 ) 공간 복잡도 Θ( 1 ) void selectionSort(int arr[], int n){ int i, j, indexMin, temp; for(i=0; i