목록Random number generator (1)

THIS IS ELLIE

퀵소트 개선 방법

스위프트 데이터 구조와 알고리즘 책을 읽으며 알게 된 사실. 흔히 아는 퀵 정렬. 스위프트에서도 정렬 함수에 퀵 정렬이 사용된다. 그만큼 강력한 정렬이고 장점이 많다. 평균 시간복잡도는 O(nlogn)이다. 하지만 피봇 값에 따라 편향되게 분할될 가능성도 있어 최악의 경우 시간복잡도는 O(n^2)이다. 예를 들어 이미 정렬할 데이터가 정렬되어 있거나 역으로 정렬되어 있는 경우 피봇이 한쪽으로 치우쳐 N개의 원소를 피봇 기준으로 나누는 작업을 N번 실행하기 때문에 최악의 경우는 O(n^2)의 시간 복잡도를 가지기도 한다. 퀵 소트가 좋다고는 하지만 최악의 경우는 높은 성능을 기대하기도 어렵다. 이를 해결하기 위해서 개선된 방식으로는 피봇을 정하는 인덱스를 처음과 끝으로 고정시키지 않는다는 것이다. 그럼 이..
낑낑 2019. 9. 24. 17:40
이전 Prev 1 Next 다음