알고리즘/정렬2 정렬 생각 흐름 Arrays.sort() 시도안되면 Collections.sort() 시도퀵 정렬 시도 정렬 방식시간 복잡도Arrays.sort()DualPivotQuicksort평균 : O(nlog(n)) / 최악 : O(n^2)Collections.sort()TimeSort (삽입정렬과 합병정렬을 결합한 정렬)평균, 최악 : O(nlog(n)) 2024. 5. 20. 퀵 정렬(Quick Sort) 퀵 정렬의 메커니즘은 크게 다음과 같다.하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 방법이다.이 부분에서 만약 알고리즘에 대해 잘 알고있다면 '분할 정복(Divide and Conquer)'을 떠올릴 것이다. 병합정렬과의 차이점병합정렬: 하나의 리스트 절반으로 나누어 분할 정복퀵 정렬: 피벗의 따라 나누기 때문에 부분리스트 크기가 다를 수도 있음 퀵 정렬 특징비교 정렬 : 구체적으로 알아보기에 앞서 미리 언급하자면 퀵 정렬은 데이터를 '비교한다.제자리 정렬(in-place sort) : 추가적인 공간을 필요로 하.. 2024. 5. 20. 이전 1 다음