quicksort1 퀵정렬 (QuickSort) 피봇을 정하여 해당 피봇보다 작은 값을 왼쪽에서부터 찾기 시작.큰 값을 오른쪽에서부터 찾기 시작.양쪽에서 진행 중 찾아지는 값들을 서로 위치 변경.반복 중에 양쪽에서 비교하던 인덱스가 만나면 그 위치와 피봇 값을 교환. 이 과정에서 중간지점으로 이동된 피봇을 중심으로 양쪽에 부분집합이 생긴다.각 부분집합마다 피봇을 다시 정하여 위의 과정을 반복한다. 자료가 균일하게 분포되어 있으면 log2(n)의 연산 횟수가 필요하다.매번 정렬시마다 n만큼 비교하므로 O(nlog(n))의 평균 효율을 보인다.데이터 이동 연산은 비교보다 적게 발생한다. 데이터가 불균형하게 분포되어 있으면 최악의 경우 n(2)의 효율성을 지닌다. 기존 피봇을 재사용하지 않고, 먼 곳에 있는 값을 교환하므로 효율이 우수하다.최악의 경우 효율.. 2018. 12. 19. 이전 1 다음