Python 빠른 정렬

이 포스팅에서 Python 빠른 정렬 프로그램과 알고리즘을 얻을 수 있습니다.

퀵 정렬은 분할 정복(divide and conquer) 기술을 기반으로 합니다. 더 작은 배열을 얻을 때까지 배열을 하위 배열로 나누고 해당 하위 배열을 다른 하위 배열로 나누는 식으로 계속합니다. 큰 배열에 비해 작은 배열을 푸는 것이 쉽기 때문입니다.

더 작은 배열을 정렬하면 전체 배열이 정렬됩니다.

Python 빠른 정렬

Quick Sort를 이해하기 위해 예를 들어보겠습니다.

예
배열이 있습니다 [48,44,19,59,72,80,42,65,82,8,95,68]

우선 첫 번째 요소를 선택하여 적절한 위치에 배치합니다. 우리는 이 요소를 Pivot 요소라고 부릅니다.

참고:  어떤 요소든 피벗 요소 로 사용할 수 있지만 편의상 첫 번째 요소를 피벗으로 사용합니다.

Pivot을 적절한 위치에 배치하기 위해서는 두 가지 조건이 있습니다 .

Pivot 요소 왼쪽의 모든 요소는 다음보다 작아야 합니다.

피벗 요소 오른쪽에 있는 모든 요소는 다음보다 커야 합니다.

주어진 배열에서 첫 번째 요소를 48인 Pivot 요소 로 사용합니다. 이제 처음 두 조건에 따라 적절한 위치에 배치합니다.

Python 빠른 정렬

여기서 왼쪽의 모든 요소는 피벗보다 작고 오른쪽의 요소는 더 큽니다.

Pivot을 적절한 위치에 배치하는 방법을 혼동하셨다면 나중에 파티션 알고리즘 에서 논의하겠습니다 .

자, 이제 Pivot 요소(48) 의 왼쪽과 오른쪽에 두 개의 하위 목록/하위 배열을 가져옵니다 . 하위 목록은 다음과 같습니다.

[42,44,19,8] 및 [80,72,65,82,59,95,68]

또한 두 요소 모두에서 첫 번째 요소를 Pivot 요소로 사용하고 파티션 알고리즘을 사용하여 Pivot 요소를 적절한 위치에  배치합니다 . 이 단계 후에 각 하위 목록은 두 부분으로 나누어지고, 새로운 하위 목록은 다른 두 부분으로 나누어지는 식으로 끝까지 도달할 때까지 계속됩니다.

그것이 어떻게 보일지 봅시다.

Python 빠른 정렬

 

녹색으로 표현되는 Pivot 요소입니다.

이 절차에 대한 재귀 함수를 작성할 수 있습니다. 두 가지 종료 조건이 있습니다. 하위 리스트에 요소가 1개만 있거나 하위 리스트가 구성되지 않은 경우. low 값이 up 과 같으면 하위 목록에는 요소가 하나만 있고 low 값이  up을 초과 하면 하위 목록이 형성되지 않습니다. 그래서 우리의 알고리즘은 다음과 같습니다.

연산
빠르게[배열, 낮음, 위로]

여기서 low 와 up  은 배열의 하한과 상한입니다.

1단계:    낮음>=높으면 반환

2단계 : piv_loc 설정 = 파티션 호출(array,low,up)

                   [피벗 위치를 찾기 위해 파티션 호출]

3단계:    Quick(array,low,piv_loc-1) 호출

                        [왼쪽 하위 목록에 대해 Quick 호출 중]

4단계:    Quick(array,piv_loc+1, up) 호출

                        [오른쪽 하위 목록에 대해 Quick 호출 중]

파티션 [배열, 낮음, 위쪽]

이 알고리즘은 피벗 요소의 위치를 ​​찾아서 반환하는 것입니다.

1단계:  i = 낮음+1로 설정

j = 위로 설정

피벗 설정 = 배열[낮음]

2단계:  while(i <= j)

{

While(( 배열[i] < 피벗 ) 및 ( i < 위로 ))

i를 1만큼 늘립니다.

동안( 배열[j] > 피벗 )

j를 1만큼 감소

(i < j )인 경우

{

array[i]의 값을 array[j]로 바꿉니다.

i를 1만큼 늘립니다.

j를 1만큼 감소

}

또 다른

i를 1만큼 늘립니다.

}

3단계:     배열[낮음] = 배열[j] 설정

배열[j] = 피벗 설정

j를 반환

시간 복잡도
최선의 경우: O(n log 2 n)

평균 사례: O(n log n)

최악의 경우: O (n 2 )

Python의 빠른 정렬 프로그램

Array = [48,44,19,59,72,80,42,65,82,8,95,68]

low = 0

up = len(Array) - 1

 

def partition(Array,low,up):

i = low+1

j = up

pivot = Array[low]

while(i<=j):

while(Array[i]<pivot and i<up):

i = i+1

while(Array[j]>pivot):

j = j-1

if(i<j):

Array[i],Array[j] = Array[j],Array[i]

i = i+1

j = j-1

else:

i = i+1

Array[low] = Array[j]

Array[j] = pivot

return j

 

def quick(Array,low,up):

if(low>=up):

return

piv_loc = partition(Array,low,up)

quick(Array,low,piv_loc-1)

quick(Array,piv_loc+1,up)

 

quick(Array,low,up)

 

for i in Array:

print i,

산출

8 19 42 44 48 59 65 68 72 80 82 95