컴퓨터 사이언스/자료구조와 알고리즘
2021. 4. 12. 18:40
[정렬] Quick Sort Algorithm depend on Pivot Selecting
Quick Sort Algorithm의 pivot 선택 방식에 대한 알고리즘 비교 1. 분석 목표 및 조건 Quick Sort Algorithm은 average-case time complexity Q(nlgn)을 가지는 알고리즘으로 알려져있다. 이에 대해 검증해보고, pivot selecting에 따른 Quick Sort Algorithm의 효율에 대해 분석해보겠다. Quick Sort Algorithm을 분석하기 전, 먼저 든 고민은 배열안의 수의 범위를 어디까지 한정해야하는 가였다. 배열의 수의 범위가 적다면 배열안에 중복의 숫자가 나올 확률이 늘어날 것이고, 이는 분명히 알고리즘의 효율에 영향을 끼칠 것이다. 또한, 수의 범위를 특정 숫자, 예를 들어 1~100이라고 가정한다면, 배열의 크기가 1..
