깡뇽

- Quick Sort : 빠른 정렬 => Merge Sort처럼 분할 - 정복 - 합병의 분할정복법을 이용함. Ex) 정렬할 배열이 주어졌을 때, 마지막 수를 기준(pivot)으로 삼음 -> 기준보다 작은 수는 기준의 왼쪽에 나머지는 기준의 오른쪽에 오도록 재배치(분할:partition)를 함. -> 기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬함. => 정렬 완료 - 최악의 경우 항상 한 쪽은 0개, 다른 쪽은 n-1개로 분할되는 경우 이미 정렬된 입력 데이터 ( 마지막 원소를 기준으로 선택하는 경우 ) - 최선의 경우 항상 절반으로 분할 되는 경우 => 분할이 얼마나 되어 있는지에 따라 Quick Sort는 영향을 받음. - 평균시간복잡도 최악의 경우는 매우 극단적인 예이며 대체적인 경우가 존재 - ..

- 분할정복법 : 분할, 정복, 합병을 거치는 방법 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 정복 : 각각의 문제를 순환적으로 해결 합병 : 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함 - Merge Sort : 합병정렬 1. 분할 -> 데이터가 저장된 배열을 절반으로 나눔. (divide) 2. 정렬 -> 각각을 순환적으로 정렬함. (recursively sort) 3. 합병 -> 정렬된 두 개의 배열을 합쳐 전체를 정렬함. (merge) => 합병 과정이 실질적으로 중요함. Ex) A | G | L | O | R 과 H | I | M | S | T 의 정렬된 두 배열이 있을 때, A와 H는 각 배열에서 가장 작은 값이며 두 배열을 하나의 배열로 합병할 때..

- 정렬 Bubble sort, Insertion sort, Selection sort => 상대적으로 단순하고 느림. Quick sort, Merge sort, Heap sort => 상대적으로 빠름. Radix sort - Selection Sort 1. 데이터 중에서 가장 큰 값을 찾고 마지막 자리의 값과 위치를 바꿈. => 가장 큰 값이 마지막 위치를 갖게 됨. 2. 가장 큰 값을 제외하고 남아 있는 데이터 중에서 가장 큰 값을 찾고 마지막 자리의 값과 위치를 바꿈. 이때, 정렬하고자 하는 데이터 중에 가장 큰 값이 마지막 자리에 있는 경우 그 위치에 그대로 둠. 3. 2번을 반복함. 2개의 데이터가 남을 때까지 반복한 후 그 둘 중 큰 값을 뒷자리로 보냄. 정렬은 완료됨. Ex) 배열 A[1....