그럴 것 같지 않다 병합 정렬 , QuickSort는 분할 정복 알고리즘 . 요소를 피벗으로 선택하고 선택한 피벗 주위에 지정된 배열을 분할합니다.

서로 다른 방식으로 피벗을 선택하는 다양한 버전의 QuickSort가 있습니다.

1. 항상 첫 번째 요소를 피벗으로 선택합니다.
2. 항상 마지막 요소를 피벗으로 선택합니다.
3. 임의의 요소를 피벗으로 선택
4. 중앙값을 피벗으로 선택

여기서는 마지막 요소를 피벗으로 선택하겠습니다. QuickSort의 핵심 프로세스는 partition()입니다. 파티션의 대상은 배열과 배열의 요소 'x'를 피벗으로 지정하고 x를 정렬된 배열의 올바른 위치에 놓고 모든 작은 요소(x보다 작은)를 x 앞에 놓고 더 큰 요소(더 큰 요소)를 모두 넣는 것입니다. x보다) x 이후. 이 모든 작업은 선형 시간 내에 수행되어야 합니다.

파이썬 재귀적 QuickSort 기능

// low -->시작 인덱스, // high --> 끝 인덱스 QuickSort(arr[], low, high) { // 시작 인덱스가 끝 인덱스보다 작을 때까지 if (low // pi는 분할 인덱스, // arr[p]는 이제 올바른 위치에서 pi = partition(arr, low, high); // pi 전 QuickSort(arr, low, pi - 1) // pi 후 QuickSort(arr, pi + 1, high);   
파이썬3 
     
 
  
     
   
  
     
  
     
     
     
  
 
  
  
  
  
  # Python program for implementation of Quicksort Sort>   # This implementation utilizes pivot as the last element in the nums list>   # It has a pointer to keep track of the elements smaller than the pivot>   # At the very end of partition() function, the pointer is swapped with the pivot>   # to come up with a 'sorted' nums relative to the pivot>   # Function to find the partition position>   def>   partition(array, low, high):>   >  # choose the rightmost element as pivot>   >  pivot>  =>   array[high]>   >  # pointer for greater element>   >  i>  =>   low>  ->   1>   >  # traverse through all elements>   >  # compare each element with pivot>   >  for>   j>  in>   range>  (low, high):>   >  if>   array[j]  <>  =>   pivot:>   >  # If element smaller than pivot is found>   >  # swap it with the greater element pointed by i>   >  i>  =>   i>  +>   1>   >  # Swapping element at i with element at j>   >  (array[i], array[j])>  =>   (array[j], array[i])>   >  # Swap the pivot element with the greater element specified by i>   >  (array[i>  +>   1>  ], array[high])>  =>   (array[high], array[i>  +>   1>  ])>   >  # Return the position from where partition is done>   >  return>   i>  +>   1>   # function to perform quicksort>   def>   quickSort(array, low, high):>   >  if>   low   # Find pivot element such that  # element smaller than pivot are on the left  # element greater than pivot are on the right  pi = partition(array, low, high)  # Recursive call on the left of pivot  quickSort(array, low, pi - 1)  # Recursive call on the right of pivot  quickSort(array, pi + 1, high) data = [1, 7, 4, 1, 10, 9, -2] print('Unsorted Array') print(data) size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data)>  
  
  
  
  
 
     
 
     
 
   
 
  산출   
 
  
Unsorted Array [1, 7, 4, 1, 10, 9, -2] Sorted Array in Ascending Order: [-2, 1, 1, 4, 7, 9, 10] 
  
    시간 복잡도:     최악의 경우 시간 복잡도는 O(N   2   )이고 평균 사례 시간 복잡도는 O(N log N)입니다.   
    보조 공간:     오(1)  
  
    Python Quicksort를 사용하여         목록 이해       
  
 목록 이해를 사용하는 Quicksort는 요소 배열을 정렬하는 재귀 알고리즘입니다. 피벗 요소를 선택하고 피벗 주위의 배열을 분할하여 작동합니다. 즉, 피벗보다 작은 모든 요소는 왼쪽으로 이동하고 피벗보다 큰 모든 요소는 오른쪽으로 이동합니다. 그런 다음 전체 배열이 정렬될 때까지 왼쪽 및 오른쪽 하위 배열에 동일한 프로세스를 반복적으로 적용합니다.  
  
    연산:     
  
 1. 입력 배열의 길이가 0 또는 1인 경우 이미 정렬된 배열을 반환합니다.   
 2. 배열의 첫 번째 요소를 피벗 요소로 선택합니다.   
 3. 왼쪽과 오른쪽에 두 개의 빈 목록을 만듭니다.   
 4.피벗을 제외한 배열의 각 요소에 대해 다음을 수행합니다.   
 ㅏ. 요소가 피벗보다 작으면 왼쪽 목록에 추가합니다.   
 비. 요소가 피벗보다 크거나 같으면 오른쪽 목록에 추가합니다.   
 5.왼쪽 및 오른쪽 목록에서 퀵소트를 반복적으로 호출합니다.   
 6. 정렬된 왼쪽 목록, 피벗 요소 및 정렬된 오른쪽 목록을 연결합니다.   
 7.연결된 목록을 반환합니다.  
  
파이썬3 
     
 
  
     
   
  
     
  
     
     
     
  
 
  
  
  
  
  # Approach 2: Quicksort using list comprehension>   def>   quicksort(arr):>   >  if>   len>  (arr)  <>  =>   1>  :>   >  return>   arr>   >  else>  :>   >  pivot>  =>   arr[>  0>  ]>   >  left>  =>   [x>  for>   x>  in>   arr[>  1>  :]>  if>   x   right = [x for x in arr[1:] if x>= 피벗] return Quicksort(왼쪽) + [pivot] + Quicksort(오른쪽) # 사용 예 arr = [1, 7, 4, 1, 10, 9, -2] sorted_arr = Quicksort(arr) print('Sorted Array 오름차순:') print(sorted_arr)>  
  
  
  
  
 
     
 
   
 
     
 
   
 
  산출   
 
  
Sorted Array in Ascending Order: [-2, 1, 1, 4, 7, 9, 10] 
  
 시간 복잡도는 O(n log n)입니다.  
  
 알고리즘의 공간 복잡도는 O(n)입니다.