QuickSort tại chỗ trong Python

Question

Tôi phải triển khai thuật toán QuickSort cho bài tập về nhà bằng ngôn ngữ tôi chọn và tôi đã chọn Python.

Trong các bài giảng, chúng tôi được thông báo rằng QuickSort là bộ nhớ hiệu quả vì nó hoạt động tại chỗ; nghĩa là, nó không có thêm bản sao của các phần của mảng đầu vào để thu thập lại. Với điều này trong tâm trí, tôi đã cố gắng thực hiện thuật toán QuickSort bằng Python, nhưng ngay sau đó nhận ra rằng để viết một đoạn mã tao nhã, tôi sẽ phải chuyển các phần của mảng tới chính hàm đó trong khi đệ quy. Kể từ khi Python tạo danh sách mới mỗi lần tôi làm điều này, tôi đã thử sử dụng Python3 (vì nó hỗ trợ từ khóa không phải là từ khóa). Sau đây là mã nhận xét của tôi.

def quicksort2(array): 
# Create a local copy of array. 
arr = array 

    def sort(start, end): 
     # Base case condition 
     if not start < end: 
      return 

     # Make it known to the inner function that we will work on arr 
     # from the outer definition 
     nonlocal arr 

     i = start + 1 
     j = start + 1 

     # Choosing the pivot as the first element of the working part 
     # part of arr 
     pivot = arr[start] 

     # Start partitioning 
     while j <= end: 
      if arr[j] < pivot: 
       temp = arr[i] 
       arr[i] = arr[j] 
       arr[j] = temp 
       i += 1 
      j += 1 
     temp = arr[start] 
     arr[start] = arr[i - 1] 
     arr[i - 1] = temp 
     # End partitioning 

     # Finally recurse on both partitions 
     sort(start + 0, i - 2) 
     sort(i, end) 
    sort(0, len(array) - 1) 

Bây giờ, tôi không chắc liệu tôi đã làm tốt công việc hay tôi thiếu gì đó. Tôi đã viết một phiên bản Pythonic của QuickSort nhưng điều đó chắc chắn không hoạt động tại chỗ vì nó giữ lại các phần của mảng đầu vào và nối chúng lại.

Câu hỏi của tôi là, đây có phải là cách thực hiện nó bằng Python không? Tôi đã tìm kiếm cả Google và SO nhưng chưa tìm thấy triển khai thực hiện tại chỗ của QuickSort, vì vậy tôi nghĩ tốt nhất nên hỏi.

Answer 1

Chắc chắn không phải là cách tốt nhất, cộng với thuật toán nổi tiếng này sẽ có hàng chục triển khai hoàn hảo .. này là của tôi, khá dễ hiểu

def sub_partition(array, start, end, idx_pivot): 

    'returns the position where the pivot winds up' 

    if not (start <= idx_pivot <= end): 
     raise ValueError('idx pivot must be between start and end') 

    array[start], array[idx_pivot] = array[idx_pivot], array[start] 
    pivot = array[start] 
    i = start + 1 
    j = start + 1 

    while j <= end: 
     if array[j] <= pivot: 
      array[j], array[i] = array[i], array[j] 
      i += 1 
     j += 1 

    array[start], array[i - 1] = array[i - 1], array[start] 
    return i - 1 

def quicksort(array, start=0, end=None): 

    if end is None: 
     end = len(array) - 1 

    if end - start < 1: 
     return 

    idx_pivot = random.randint(start, end) 
    i = sub_partition(array, start, end, idx_pivot) 
    #print array, i, idx_pivot 
    quicksort(array, start, i - 1) 
    quicksort(array, i + 1, end) 

Ok đầu tiên một chức năng riêng biệt cho chương trình con phân vùng. Phải mất mảng, điểm bắt đầu và điểm đến quan tâm và chỉ mục của trục. Các chức năng này phải rõ ràng

Quicksort sau đó gọi chương trình con phân vùng lần đầu tiên trên toàn bộ mảng; sau đó gọi recursevely chính nó để sắp xếp tất cả mọi thứ lên đến trục và tất cả mọi thứ sau.

hỏi nếu bạn không hiểu điều gì đó

Answer 2

Tôi đã bắt đầu học python gần đây và sau đây là nỗ lực của tôi lúc thực hiện quicksort sử dụng python. Hy vọng nó là hữu ích. Phản hồi được hoan nghênh :)

#!/usr/bin/python 

Array = [ 3,7,2,8,1,6,8,9,6,9] 

def partition(a, left, right): 

    pivot = left + (right - left)/2 
    a[left],a[pivot] = a[pivot], a[left] # swap 
    pivot = left 
    left += 1 

    while right >= left : 
     while left <= right and a[left] <= a[pivot] : 
      left += 1 
     while left <= right and a[right] > a[pivot] : 
      right -= 1 

     if left <= right: 
      a[left] , a[right] = a[right], a[left] # swap 
      left += 1 
      right -= 1 
     else: 
      break 

    a[pivot], a[right] = a[right] , a[pivot] 

    return right 


def quicksort(array , left,right): 
    if left >= right: 
     return 
    if right - left == 1: 
     if array[right] < array[left]: 
      array[right], array[left] = array[left] , array[right] 
      return   

    pivot = partition(array, left, right) 

    quicksort(array, left, pivot -1) 
    quicksort(array, pivot+1,right)   

def main(): 
    quicksort(Array, 0 , len(Array) -1) 
    print Array 

main() 

Answer 3

Đây là những gì tôi nghĩ ra. Thuật toán được đặt tại chỗ, trông đẹp và có tính đệ quy.

# `a` is the subarray we're working on 
# `p` is the start point in the subarray we're working on 
# `r` is the index of the last element of the subarray we're working on 

def part(a,p,r): 
    k=a[r] #pivot 
    j,q=p,p 
    if p<r: # if the length of the subarray is greater than 0 
     for i in range(p,r+1): 
      if a[i]<=k: 
       t=a[q] 
       a[q]=a[j] 
       a[j]=t 
       if i!=r: 
        q+=1 
       j+=1 
      else: 
       j+=1 
     part(a,p,q-1) # sort the subarray to the left of the pivot 
     part(a,q+1,r) # sort the subarray to the right of the pivot 
    return a 
def quicksort(a): 
    if len(a)>1: 
     return part(a,0,len(a)-1) 
    else: 
     return a 

Answer 4

Dưới đây là một thực hiện:

def quicksort(alist): 
    if len(alist) <= 1: 
     return alist 
    return part(alist,0,len(alist)-1) 

def part(alist,start,end): 
    pivot = alist[end] 
    border = start 
    if start < end: 
     for i in range(start,end+1): 
      if alist[i] <= pivot: 
       alist[border], alist[i] = alist[i], alist[border] 
       if i != end: 
        border += 1 
     part(alist,start,border-1) 
     part(alist,border+1,end) 
    return alist 

Answer 5

Giải thích: Pivot luôn là yếu tố cuối cùng trong mảng nhất định. Trong cách tiếp cận của tôi, tôi theo dõi 'biên giới' giữa các số nhỏ hơn và lớn hơn trục xoay. Đường viền là chỉ mục số đầu tiên trong nhóm 'lớn hơn'. Vào cuối mỗi lần lặp, chúng tôi hoán đổi số dưới 'border' với số pivot.

Và mã:

def qs(ar, start, end): 
    if (end-start < 1): 
     return 
    if (end-start == 1): 
     if(ar[start] > ar[end]): 
      tmp = ar[start] 
      ar[start] = ar[end] 
      ar[end] = tmp 
     return 
    pivot = ar[end - 1] 
    border_index = start 
    i = start 
    while(i <= end - 1): 
     if (ar[i] < pivot): 
      if i > border_index: 
       tmp = ar[i] 
       ar[i] = ar[border_index] 
       ar[border_index] = tmp 
      border_index += 1 
     i+=1 
    ar[end-1] = ar[border_index] 
    ar[border_index] = pivot 
    qs(ar, start, border_index) 
    qs(ar, border_index + 1, end) 

qs(ar, 0, n)