'Computer/알고리즘'에 해당되는 글 26건

  1. 2007.04.05 Sorting에 대한 짧은 정리(NlogN, Quick정렬)
반응형

C. Hoare가 고안, 가장 인기 있는 Sorting으로 일반적으로 속도가 매우 빠르다. 어떤 키 값을 중심으로 (a[i]) 왼쪽으로 부터는 키 값보다 큰 값을, 오른쪽으로 부터는 키 값보다 작은 값을 찾아서 교환하는 방법이다.

1. 기준값(Pivot)을 하나 선택하여

2. 그 기준값보다 작은 항목들은 모두 배열의 왼쪽으로

3. 그 기준값보다 큰 항목들은 모두 배열의 오른쪽으로

4. 왼쪽 부분 배열에 퀵정렬을 재귀적으로 적용

5. 오른쪽의 부분 배열에 퀵 정렬을 재귀적으로 이용

다음 그림은 1,2,3에 대해서 수행하는 그림이다

사용자 삽입 이미지

문제는 Pivot에 따라서 이 알고리즘으 수행 속도가 영향을 받는다, Pivot이 정 중앙 값일 수록 빨라지며, 최악의 경우 O(N^2)까지도 속도가 나올수 있다. Pivot을 구하는 가장 유명한 방법으로는 3중앙(median-of-three) 알고리즘으로 첫번쨰, 중간, 마지막 색인의 값중 가운데 값을 기준값으로 사용하는 것이다.

평균적으로 O(NlogN)의 알고리즘이다.

반응형
Posted by alias
,