정렬

QuickSort? - 말 그대로 빠른 정렬이다. - 퀵 소트는 평균적인 시간복잡도는 O(NlogN), 최악의 경우 O(N^2) 이다. - 따로 메모리를 저장하여 정렬하지 않아서 공간복잡도는 O(1)이다! - 이러한 불규칙적 성질 때문에 불안정 정렬이라 한다. - 일단 이론이 굉장히 어려우므로 바로 설명을 가보도록 하자 과정 1. 리스트 안에 있는 한 요소(pivot)를 고르자! 2. pivot을 기준으로 큰 값은 오른쪽, 작은 값은 왼쪽으로 정렬하자~! 3. pivot의 왼쪽 부분과 오른쪽 부분을 다시 재귀로 정렬하자! 4. 단 리스트의 크기가 0, 혹은 pivot 자신만 있을 때 (1) 이면 하지 않는다! Quick 정렬에 대한 고찰 - 파티션을 나누는 과정이 MergeSort와 동일하게 2분할이다...

MergeSort? - 대표적인 분할정복 정렬 알고리즘 중의 하나 cf> 분할정복(Divide And Conquer) ? : 문제를 작은 2개의 문제로 분리하여, 해결하고 결과를 합치는 전략이다. - 메모리를 잡아먹는 특징 때문에, 안정성이 많이 보장되는 정렬 알고리즘이다. - 시간복잡도는 O(NlogN), 공간복잡도는 O(N) 이다. ++ 배열을 1개로 될 때까지 각각을 n/2로 줄이니 당연히 logN 이다. ++ 합칠 때는 총 N번의 비교연산이 들어가므로 N*logN 이 되는 시간복잡도이다! - 보통 정렬의 공간복잡도는 O(1)인데, 병합정렬의 경우 복사할 배열이 새로 필요하다! 언제 써야될까? 1. 많은 데이터를 정렬할 때, 여분의 메모리가 충분할 때! 2. 반대로, 많은 데이터를 정렬하고 싶은데 ..