Saya benar-benar baru mengenal python dan saya mencoba menerapkan quicksort di dalamnya. Bisakah seseorang membantu saya melengkapi kode saya?

Saya tidak tahu bagaimana menggabungkan ketiga array dan mencetaknya.

def sort(array=[12,4,5,6,7,3,1,15]):
    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)
            sort(less)
            sort(pivot)
            sort(greater)

def sort(array=[12,4,5,6,7,3,1,15]):
    """Sort the array by using quicksort."""

    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            elif x == pivot:
                equal.append(x)
            elif x > pivot:
                greater.append(x)
        # Don't forget to return something!
        return sort(less)+equal+sort(greater)  # Just use the + operator to join lists
    # Note that you want equal ^^^^^ not pivot
    else:  # You need to handle the part at the end of the recursion - when you only have one element in your array, just return the array.
        return array

Sortir cepat tanpa memori tambahan (di tempat)

Pemakaian:

array = [97, 200, 100, 101, 211, 107]
quicksort(array)
# array -> [97, 100, 101, 107, 200, 211]

def partition(array, begin, end):
    pivot = begin
    for i in xrange(begin+1, end+1):
        if array[i] <= array[begin]:
            pivot += 1
            array[i], array[pivot] = array[pivot], array[i]
    array[pivot], array[begin] = array[begin], array[pivot]
    return pivot



def quicksort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    def _quicksort(array, begin, end):
        if begin >= end:
            return
        pivot = partition(array, begin, end)
        _quicksort(array, begin, pivot-1)
        _quicksort(array, pivot+1, end)
    return _quicksort(array, begin, end)

Ada versi lain yang ringkas dan indah

def qsort(arr): 
    if len(arr) <= 1:
        return arr
    else:
        return qsort([x for x in arr[1:] if x < arr[0]]) + \
               [arr[0]] + \
               qsort([x for x in arr[1:] if x >= arr[0]])

# this comment is just to improve readability due to horizontal scroll!!!

Izinkan saya menjelaskan kode di atas untuk detailnya

1. pilih elemen pertama dari array arr[0]sebagai pivot

   [arr[0]]

2. qsort elemen array yang kurang dari poros dengan List Comprehension

   qsort([x for x in arr[1:] if x < arr[0]])

3. qsort elemen array yang lebih besar dari pivot dengan List Comprehension

   qsort([x for x in arr[1:] if x >= arr[0]])

Jawaban ini adalah QuickSort di tempat Python 2.x. Jawaban saya adalah interpretasi dari solusi di tempat dari Rosetta Code yang berfungsi Python 3juga:

import random

def qsort(xs, fst, lst):
    '''
    Sort the range xs[fst, lst] in-place with vanilla QuickSort

    :param xs:  the list of numbers to sort
    :param fst: the first index from xs to begin sorting from,
                must be in the range [0, len(xs))
    :param lst: the last index from xs to stop sorting at
                must be in the range [fst, len(xs))
    :return:    nothing, the side effect is that xs[fst, lst] is sorted
    '''
    if fst >= lst:
        return

    i, j = fst, lst
    pivot = xs[random.randint(fst, lst)]

    while i <= j:
        while xs[i] < pivot:
            i += 1
        while xs[j] > pivot:
            j -= 1

        if i <= j:
            xs[i], xs[j] = xs[j], xs[i]
            i, j = i + 1, j - 1
    qsort(xs, fst, j)
    qsort(xs, i, lst)

Dan jika Anda ingin mengabaikan properti di tempat, berikut adalah versi lain yang lebih menggambarkan ide dasar di balik quicksort. Selain keterbacaan, keuntungan lainnya adalah stabil (elemen yang sama muncul di daftar yang diurutkan dalam urutan yang sama seperti yang dulu ada di daftar yang tidak diurutkan). Properti stabilitas ini tidak berlaku untuk implementasi di tempat yang haus memori yang disajikan di atas.

def qsort(xs):
    if not xs: return xs # empty sequence case
    pivot = xs[random.choice(range(0, len(xs)))]

    head = qsort([x for x in xs if x < pivot])
    tail = qsort([x for x in xs if x > pivot])
    return head + [x for x in xs if x == pivot] + tail

Quicksort dengan Python

Dalam kehidupan nyata, kita harus selalu menggunakan jenis bawaan yang disediakan oleh Python. Namun, memahami algoritme quicksort itu instruktif.

Tujuan saya di sini adalah untuk memecah subjek sedemikian rupa sehingga mudah dipahami dan dapat ditiru oleh pembaca tanpa harus kembali ke materi referensi.

Algoritme quicksort pada dasarnya adalah sebagai berikut:

1. Pilih titik data pivot.
2. Pindahkan semua titik data yang kurang dari (di bawah) poros ke posisi di bawah poros - pindahkan yang lebih besar dari atau sama dengan (di atas) poros ke posisi di atasnya.
3. Terapkan algoritme ke area di atas dan di bawah poros

Jika data didistribusikan secara acak, memilih titik data pertama sebagai pivot sama dengan pemilihan acak.

Contoh yang bisa dibaca:

Pertama, mari kita lihat contoh yang dapat dibaca yang menggunakan komentar dan nama variabel untuk menunjuk ke nilai antara:

def quicksort(xs):
    """Given indexable and slicable iterable, return a sorted list"""
    if xs: # if given list (or tuple) with one ordered item or more: 
        pivot = xs[0]
        # below will be less than:
        below = [i for i in xs[1:] if i < pivot] 
        # above will be greater than or equal to:
        above = [i for i in xs[1:] if i >= pivot]
        return quicksort(below) + [pivot] + quicksort(above)
    else: 
        return xs # empty list

Untuk menyatakan kembali algoritme dan kode yang ditunjukkan di sini - kami memindahkan nilai di atas pivot ke kanan, dan nilai di bawah pivot ke kiri, lalu meneruskan partisi tersebut ke fungsi yang sama untuk diurutkan lebih lanjut.

Golf:

Ini bisa dimainkan hingga 88 karakter:

q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])

Untuk melihat bagaimana kami sampai di sana, pertama-tama ambil contoh kami yang dapat dibaca, hapus komentar dan dokumen, dan temukan pivot di tempat:

def quicksort(xs):
    if xs: 
        below = [i for i in xs[1:] if i < xs[0]] 
        above = [i for i in xs[1:] if i >= xs[0]]
        return quicksort(below) + [xs[0]] + quicksort(above)
    else: 
        return xs

Sekarang temukan di bawah dan di atas, di tempat:

def quicksort(xs):
    if xs: 
        return (quicksort([i for i in xs[1:] if i < xs[0]] )
                + [xs[0]] 
                + quicksort([i for i in xs[1:] if i >= xs[0]]))
    else: 
        return xs

Sekarang, mengetahui bahwa andmengembalikan elemen sebelumnya jika salah, jika tidak benar, itu mengevaluasi dan mengembalikan elemen berikut, kita memiliki:

def quicksort(xs):
    return xs and (quicksort([i for i in xs[1:] if i < xs[0]] )
                   + [xs[0]] 
                   + quicksort([i for i in xs[1:] if i >= xs[0]]))

Karena lambda mengembalikan satu epresi, dan kami telah menyederhanakan menjadi satu ekspresi (meskipun semakin tidak terbaca) sekarang kami dapat menggunakan lambda:

quicksort = lambda xs: (quicksort([i for i in xs[1:] if i < xs[0]] )
                        + [xs[0]] 
                        + quicksort([i for i in xs[1:] if i >= xs[0]]))

Dan untuk mengurangi contoh kita, persingkat nama fungsi dan variabel menjadi satu huruf, dan hilangkan spasi yang tidak diperlukan.

q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])

Perhatikan bahwa lambda ini, seperti kebanyakan kode golf, adalah gaya yang agak buruk.

Quicksort di tempat, menggunakan skema Partisi Hoare

Implementasi sebelumnya membuat banyak daftar tambahan yang tidak perlu. Jika kami dapat melakukan ini di tempat, kami akan menghindari pemborosan ruang.

Implementasi di bawah ini menggunakan skema partisi Hoare, yang dapat Anda baca lebih lanjut di wikipedia (tetapi kami tampaknya telah menghapus hingga 4 kalkulasi redundan per partition()panggilan dengan menggunakan semantik while-loop alih-alih do-while dan memindahkan langkah-langkah penyempitan ke akhir loop sementara luar.).

def quicksort(a_list):
    """Hoare partition scheme, see https://en.wikipedia.org/wiki/Quicksort"""
    def _quicksort(a_list, low, high):
        # must run partition on sections with 2 elements or more
        if low < high: 
            p = partition(a_list, low, high)
            _quicksort(a_list, low, p)
            _quicksort(a_list, p+1, high)
    def partition(a_list, low, high):
        pivot = a_list[low]
        while True:
            while a_list[low] < pivot:
                low += 1
            while a_list[high] > pivot:
                high -= 1
            if low >= high:
                return high
            a_list[low], a_list[high] = a_list[high], a_list[low]
            low += 1
            high -= 1
    _quicksort(a_list, 0, len(a_list)-1)
    return a_list

Tidak yakin apakah saya mengujinya dengan cukup teliti:

def main():
    assert quicksort([1]) == [1]
    assert quicksort([1,2]) == [1,2]
    assert quicksort([1,2,3]) == [1,2,3]
    assert quicksort([1,2,3,4]) == [1,2,3,4]
    assert quicksort([2,1,3,4]) == [1,2,3,4]
    assert quicksort([1,3,2,4]) == [1,2,3,4]
    assert quicksort([1,2,4,3]) == [1,2,3,4]
    assert quicksort([2,1,1,1]) == [1,1,1,2]
    assert quicksort([1,2,1,1]) == [1,1,1,2]
    assert quicksort([1,1,2,1]) == [1,1,1,2]
    assert quicksort([1,1,1,2]) == [1,1,1,2]

Kesimpulan

Algoritma ini sering diajarkan dalam kursus ilmu komputer dan diminta untuk wawancara kerja. Ini membantu kita memikirkan tentang rekursi dan bagi-dan-taklukkan.

Quicksort tidak terlalu praktis dengan Python karena algoritme timsort bawaan kami cukup efisien, dan kami memiliki batas rekursi. Kami berharap untuk mengurutkan daftar di tempat dengan list.sortatau membuat daftar baru yang diurutkan dengan sorted- keduanya mengambil argumen keydan reverse.

Ada banyak jawaban untuk ini, tapi menurut saya pendekatan ini adalah implementasi yang paling bersih:

def quicksort(arr):
    """ Quicksort a list

    :type arr: list
    :param arr: List to sort
    :returns: list -- Sorted list
    """
    if not arr:
        return []

    pivots = [x for x in arr if x == arr[0]]
    lesser = quicksort([x for x in arr if x < arr[0]])
    greater = quicksort([x for x in arr if x > arr[0]])

    return lesser + pivots + greater

Anda tentu saja dapat melewati penyimpanan semuanya dalam variabel dan langsung mengembalikannya seperti ini:

def quicksort(arr):
    """ Quicksort a list

    :type arr: list
    :param arr: List to sort
    :returns: list -- Sorted list
    """
    if not arr:
        return []

    return quicksort([x for x in arr if x < arr[0]]) \
        + [x for x in arr if x == arr[0]] \
        + quicksort([x for x in arr if x > arr[0]])

pendekatan fungsional:

def qsort(list):
    if len(list) < 2:
        return list

    pivot = list.pop()
    left = filter(lambda x: x <= pivot, list)
    right = filter(lambda x: x > pivot, list)

    return qsort(left) + [pivot] + qsort(right)

pendekatan pemrograman fungsional

smaller = lambda xs, y: filter(lambda x: x <= y, xs)
larger = lambda xs, y: filter(lambda x: x > y, xs)
qsort = lambda xs: qsort(smaller(xs[1:],xs[0])) + [xs[0]] + qsort(larger(xs[1:],xs[0])) if xs != [] else []

print qsort([3,1,4,2,5]) == [1,2,3,4,5]

Implementasi yang mudah dari algoritma grokking

def quicksort(arr):
    if len(arr) < 2:
        return arr #base case
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot] 
        more = [i for i in arr[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(more)

Saya pikir kedua jawaban di sini berfungsi dengan baik untuk daftar yang disediakan (yang menjawab pertanyaan asli), tetapi akan rusak jika larik yang berisi nilai-nilai tidak unik dilewatkan. Jadi untuk kelengkapan, saya hanya akan menunjukkan kesalahan kecil di masing-masing dan menjelaskan cara memperbaikinya.

Misalnya mencoba mengurutkan array berikut [12,4,5,6,7,3,1,15,1] (Perhatikan bahwa 1 muncul dua kali) dengan algoritma Brionius .. di beberapa titik akan berakhir dengan lebih sedikit array kosong dan larik yang sama dengan sepasang nilai (1,1) yang tidak dapat dipisahkan pada iterasi berikutnya dan len ()> 1 ... maka Anda akan berakhir dengan pengulangan tak hingga

Anda dapat memperbaikinya dengan mengembalikan array jika kurang kosong atau lebih baik dengan tidak memanggil sortir dalam array yang sama, seperti dalam jawaban zangw

def sort(array=[12,4,5,6,7,3,1,15]):
    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)

        # Don't forget to return something!
        return sort(less)+ equal +sort(greater)  # Just use the + operator to join lists
    # Note that you want equal ^^^^^ not pivot
    else:  # You need to hande the part at the end of the recursion - when you only have one element in your array, just return the array.
        return array

Solusi yang lebih bagus juga rusak, tetapi karena alasan yang berbeda, tidak ada pengembaliannya klausa tidak ada di baris rekursi, yang pada suatu saat akan mengembalikan Tidak Ada dan mencoba menambahkannya ke daftar ....

Untuk memperbaikinya tambahkan saja kembali ke baris itu

def qsort(arr): 
   if len(arr) <= 1:
      return arr
   else:
      return qsort([x for x in arr[1:] if x<arr[0]]) + [arr[0]] + qsort([x for x in arr[1:] if x>=arr[0]])

Ini adalah versi quicksort yang menggunakan skema partisi Hoare dan dengan lebih sedikit swap dan variabel lokal

def quicksort(array):
    qsort(array, 0, len(array)-1)

def qsort(A, lo, hi):
    if lo < hi:
        p = partition(A, lo, hi)
        qsort(A, lo, p)
        qsort(A, p + 1, hi)

def partition(A, lo, hi):
    pivot = A[lo]
    i, j = lo-1, hi+1
    while True:
      i += 1
      j -= 1
      while(A[i] < pivot): i+= 1
      while(A[j] > pivot ): j-= 1

      if i >= j: 
          return j

      A[i], A[j] = A[j], A[i]


test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
print quicksort(test)

Partisi - Pisahkan array dengan pivot sehingga elemen yang lebih kecil pindah ke kiri dan elemet yang lebih besar pindah ke kanan atau sebaliknya. Pivot bisa menjadi elemen acak dari array. Untuk membuat algoritma ini kita perlu mengetahui apa itu indeks awal dan akhir sebuah larik dan dimana pivotnya. Kemudian atur dua penunjuk bantu L, R.

Jadi kami memiliki pengguna array [..., mulai, ..., akhir, ...]

Posisi awal penunjuk L dan R
[..., mulai, selanjutnya, ..., akhir, ...]
     R L

sedangkan L <end
  1. Jika pengguna [pivot]> pengguna [L] lalu pindahkan R per satu dan tukar pengguna [R] dengan pengguna [L]
  2. pindahkan L per satu

Setelah sementara tukar pengguna [R] dengan pengguna [pivot]

Pengurutan cepat - Gunakan algoritme partisi hingga setiap bagian berikutnya dari pemisahan oleh pivot akan memiliki indeks awal lebih besar atau sama dengan indeks akhir.

def qsort(user, begin, end):

    if begin >= end:
        return

    # partition
    # pivot = begin
    L = begin+1
    R = begin
    while L < end:
        if user[begin] > user[L]:
            R+=1
            user[R], user[L] = user[L], user[R]
        L+= 1
    user[R], user[begin] = user[begin], user[R]

    qsort(user, 0, R)
    qsort(user, R+1, end)

tests = [
    {'sample':[1],'answer':[1]},
    {'sample':[3,9],'answer':[3,9]},
    {'sample':[1,8,1],'answer':[1,1,8]},
    {'sample':[7,5,5,1],'answer':[1,5,5,7]},
    {'sample':[4,10,5,9,3],'answer':[3,4,5,9,10]},
    {'sample':[6,6,3,8,7,7],'answer':[3,6,6,7,7,8]},
    {'sample':[3,6,7,2,4,5,4],'answer':[2,3,4,4,5,6,7]},
    {'sample':[1,5,6,1,9,0,7,4],'answer':[0,1,1,4,5,6,7,9]},
    {'sample':[0,9,5,2,2,5,8,3,8],'answer':[0,2,2,3,5,5,8,8,9]},
    {'sample':[2,5,3,3,2,0,9,0,0,7],'answer':[0,0,0,2,2,3,3,5,7,9]}
]

for test in tests:

    sample = test['sample'][:]
    answer = test['answer']

    qsort(sample,0,len(sample))

    print(sample == answer)

Atau jika Anda lebih suka satu baris yang juga mengilustrasikan persamaan Python dari C / C ++ varags, ekspresi lambda, dan ekspresi if:

qsort = lambda x=None, *xs: [] if x is None else qsort(*[a for a in xs if a<x]) + [x] + qsort(*[a for a in xs if a>=x])

def quick_sort(self, nums):
    def helper(arr):
        if len(arr) <= 1: return arr
        #lwall is the index of the first element euqal to pivot
        #rwall is the index of the first element greater than pivot
        #so arr[lwall:rwall] is exactly the middle part equal to pivot after one round
        lwall, rwall, pivot = 0, 0, 0
        #choose rightmost as pivot
        pivot = arr[-1]
        for i, e in enumerate(arr):
            if e < pivot:
                #when element is less than pivot, shift the whole middle part to the right by 1
                arr[i], arr[lwall] = arr[lwall], arr[i]
                lwall += 1
                arr[i], arr[rwall] = arr[rwall], arr[i]
                rwall += 1
            elif e == pivot:
                #when element equals to pivot, middle part should increase by 1
                arr[i], arr[rwall] = arr[rwall], arr[i]
                rwall += 1
            elif e > pivot: continue
        return helper(arr[:lwall]) + arr[lwall:rwall] + helper(arr[rwall:])
    return helper(nums)

Saya tahu banyak orang telah menjawab pertanyaan ini dengan benar dan saya senang membacanya. Jawaban saya hampir sama dengan zangw tetapi saya pikir kontributor sebelumnya tidak melakukan pekerjaan yang baik dalam menjelaskan secara visual bagaimana sebenarnya sesuatu bekerja ... jadi inilah upaya saya untuk membantu orang lain yang mungkin mengunjungi pertanyaan / jawaban ini di masa mendatang tentang a solusi sederhana untuk implementasi quicksort.

Bagaimana cara kerjanya ?

1. Kami pada dasarnya memilih item pertama sebagai poros kami dari daftar kami dan kemudian kami membuat dua sub daftar.
2. Sublist pertama kami berisi item yang kurang dari pivot
3. Sublist kedua kami berisi item kami yang lebih besar dari atau sama dengan pivot
4. Kami kemudian dengan cepat mengurutkan masing-masing dan kami menggabungkannya dengan grup pertama + pivot + grup kedua untuk mendapatkan hasil akhir.

Berikut adalah contoh bersama dengan visual yang menyertainya ... (pivot) 9,11,2,0

rata-rata: n log dari n

kasus yang lebih buruk: n ^ 2

Kode:

def quicksort(data):
if (len(data) < 2):
    return data
else:
    pivot = data[0]  # pivot
    #starting from element 1 to the end
    rest = data[1:]
    low = [each for each in rest if each < pivot]
    high = [each for each in rest if each >= pivot]
    return quicksort(low) + [pivot] + quicksort(high)

item = [9,11,2,0] cetak (quicksort (item))

Algoritme berisi dua batas, satu memiliki elemen kurang dari poros (dilacak oleh indeks "j") dan yang lainnya memiliki elemen lebih besar dari poros (dilacak dengan indeks "i").

Dalam setiap iterasi, elemen baru diproses dengan menambahkan j.

Varian: -

1. semua elemen antara pivot dan i lebih kecil dari pivot, dan
2. semua elemen antara i dan j lebih besar dari poros.

Jika invarian dilanggar, elemen ke-i dan ke-j ditukar, dan i bertambah.

Setelah semua elemen diproses, dan semua setelah pivot dipartisi, elemen pivot ditukar dengan elemen terakhir yang lebih kecil darinya.

Elemen pivot sekarang akan berada di tempat yang benar dalam urutan. Unsur-unsur sebelumnya akan lebih sedikit dari itu dan yang sesudahnya akan lebih besar dari itu, dan mereka tidak akan disortir.

def quicksort(sequence, low, high):
    if low < high:    
        pivot = partition(sequence, low, high)
        quicksort(sequence, low, pivot - 1)
        quicksort(sequence, pivot + 1, high)

def partition(sequence, low, high):
    pivot = sequence[low]
    i = low + 1
    for j in range(low + 1, high + 1):
        if sequence[j] < pivot:
            sequence[j], sequence[i] = sequence[i], sequence[j]
            i += 1
    sequence[i-1], sequence[low] = sequence[low], sequence[i-1]
    return i - 1

def main(sequence):
    quicksort(sequence, 0, len(sequence) - 1)
    return sequence

if __name__ == '__main__':
    sequence = [-2, 0, 32, 1, 56, 99, -4]
    print(main(sequence))

Memilih poros

Pivot yang "baik" akan menghasilkan dua sub-urutan dengan ukuran yang kurang lebih sama. Secara deterministik, elemen pivot dapat dipilih dengan cara yang naif atau dengan menghitung median urutan.

Implementasi naif dalam memilih pivot akan menjadi elemen pertama atau terakhir. Kasus terburuk runtime dalam hal ini adalah ketika urutan masukan sudah diurutkan atau diurutkan terbalik, karena salah satu urutan akan kosong yang hanya akan menyebabkan satu elemen dihapus per panggilan rekursif.

Pembagian yang seimbang sempurna dicapai jika pivot adalah elemen median dari urutan. Ada jumlah elemen yang sama lebih besar dari itu dan lebih sedikit dari itu. Pendekatan ini menjamin waktu pengoperasian keseluruhan yang lebih baik, tetapi jauh lebih memakan waktu.

Cara non-deterministik / acak untuk memilih poros adalah dengan memilih elemen secara seragam secara acak. Ini adalah pendekatan sederhana dan ringan yang akan meminimalkan skenario terburuk dan juga mengarah pada pemisahan yang kira-kira seimbang. Ini juga akan memberikan keseimbangan antara pendekatan naif dan pendekatan median dalam memilih poros.

def quicksort(array):
 if len(array) < 2:
  return array
 else:
  pivot = array[0]

 less = [i for i in array[1:] if i <= pivot]
 greater = [i for i in array[1:] if i > pivot]
 return quicksort(less) + [pivot] + quicksort(greater)

def quick_sort(array):
    return quick_sort([x for x in array[1:] if x < array[0]]) + [array[0]] \
        + quick_sort([x for x in array[1:] if x >= array[0]]) if array else []

def Partition(A,p,q):
    i=p
    x=A[i]
    for j in range(p+1,q+1):
        if A[j]<=x:
            i=i+1
            tmp=A[j]
            A[j]=A[i]
            A[i]=tmp
    l=A[p]
    A[p]=A[i]
    A[i]=l
    return i

def quickSort(A,p,q):
    if p<q:
        r=Partition(A,p,q)
        quickSort(A,p,r-1)
        quickSort(A,r+1,q)
    return A

Penerapan di tempat yang "benar" [Algoritme 8.9, 8.11 dari Buku Desain dan Aplikasi Algoritme oleh Michael T. Goodrich dan Roberto Tamassia]:

from random import randint

def partition (A, a, b):
    p = randint(a,b)
    # or mid point
    # p = (a + b) / 2

    piv = A[p]

    # swap the pivot with the end of the array
    A[p] = A[b]
    A[b] = piv

    i = a     # left index (right movement ->)
    j = b - 1 # right index (left movement <-)

    while i <= j:
        # move right if smaller/eq than/to piv
        while A[i] <= piv and i <= j:
            i += 1
        # move left if greater/eq than/to piv
        while A[j] >= piv and j >= i:
            j -= 1

        # indices stopped moving:
        if i < j:
            # swap
            t = A[i]
            A[i] = A[j]
            A[j] = t
    # place pivot back in the right place
    # all values < pivot are to its left and 
    # all values > pivot are to its right
    A[b] = A[i]
    A[i] = piv

    return i

def IpQuickSort (A, a, b):

    while a < b:
        p = partition(A, a, b) # p is pivot's location

        #sort the smaller partition
        if p - a < b - p:
            IpQuickSort(A,a,p-1)
            a = p + 1 # partition less than p is sorted
        else:
            IpQuickSort(A,p+1,b)
            b = p - 1 # partition greater than p is sorted


def main():
    A =  [12,3,5,4,7,3,1,3]
    print A
    IpQuickSort(A,0,len(A)-1)
    print A

if __name__ == "__main__": main()

Algoritme memiliki 4 langkah sederhana:

1. Bagilah larik menjadi 3 bagian berbeda: kiri, poros, dan kanan, di mana pivot hanya akan memiliki satu elemen. Mari kita pilih elemen pivot ini sebagai elemen pertama dari array
2. Tambahkan elemen ke masing-masing bagian dengan membandingkannya dengan elemen pivot. (penjelasan di komentar)
3. Gunakan kembali algoritme ini hingga semua elemen dalam larik telah diurutkan
4. Terakhir, gabungkan bagian kiri + pivot + kanan

Kode untuk algoritma di python:

def my_sort(A):

      p=A[0]                                       #determine pivot element. 
      left=[]                                      #create left array
      right=[]                                     #create right array
      for i in range(1,len(A)):
        #if cur elem is less than pivot, add elem in left array
        if A[i]< p:
          left.append(A[i])         
          #the recurssion will occur only if the left array is atleast half the size of original array
          if len(left)>1 and len(left)>=len(A)//2:          
              left=my_sort(left)                            #recursive call
        elif A[i]>p: 
          right.append(A[i])                                #if elem is greater than pivot, append it to right array
          if len(right)>1 and len(right)>=len(A)//2:        # recurssion will occur only if length of right array is atleast the size of original array
              right=my_sort(right)
     A=left+[p]+right                                        #append all three part of the array into one and return it
     return A

my_sort([12,4,5,6,7,3,1,15])

Lanjutkan dengan algoritma ini secara rekursif dengan bagian kiri dan kanan.

Implementasi quicksort lainnya:

# A = Array 
# s = start index
# e = end index
# p = pivot index
# g = greater than pivot boundary index

def swap(A,i1,i2):
  A[i1], A[i2] = A[i2], A[i1]

def partition(A,g,p):
    # O(n) - just one for loop that visits each element once
    for j in range(g,p):
      if A[j] <= A[p]:
        swap(A,j,g)
        g += 1

    swap(A,p,g)
    return g

def _quicksort(A,s,e):
    # Base case - we are sorting an array of size 1
    if s >= e:
      return

    # Partition current array
    p = partition(A,s,e)
    _quicksort(A,s,p-1) # Left side of pivot
    _quicksort(A,p+1,e) # Right side of pivot

# Wrapper function for the recursive one
def quicksort(A):
    _quicksort(A,0,len(A)-1)

A = [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,-1]

print(A)
quicksort(A)
print(A)

Untuk Versi Python 3.x : operatormodul penggunaan bergaya fungsional , terutama untuk meningkatkan keterbacaan.

from operator import ge as greater, lt as lesser

def qsort(L): 
    if len(L) <= 1: return L
    pivot   = L[0]
    sublist = lambda op: [*filter(lambda num: op(num, pivot), L[1:])]

    return qsort(sublist(lesser))+ [pivot] + qsort(sublist(greater))

dan diuji sebagai

print (qsort([3,1,4,2,5]) == [1,2,3,4,5])

Berikut implementasi yang mudah: -

def quicksort(array):
            if len(array) < 2:
                  return array
            else:
                  pivot= array[0]
                  less = [i for i in array[1:] if i <= pivot]

                  greater = [i for i in array[1:] if i > pivot]

                  return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))

1. Pertama kita mendeklarasikan nilai pertama dalam array menjadi pivot_value dan kita juga mengatur tanda kiri dan kanan
2. Kami membuat loop while pertama, sementara loop ada di sana untuk memberi tahu proses partisi agar berjalan kembali jika tidak memenuhi kondisi yang diperlukan
3. kemudian kami menerapkan proses partisi
4. setelah kedua proses partisi berjalan, kami memeriksa apakah itu memenuhi kondisi yang tepat. Jika ya, kami menandainya sebagai selesai, jika tidak kami mengganti nilai kiri dan kanan dan menerapkannya lagi
5. Setelah selesai, ganti nilai kiri dan kanan dan kembalikan split_point

Saya melampirkan kode di bawah ini! Quicksort ini adalah alat pembelajaran yang hebat karena Lokasi dari nilai pivot . Karena berada di tempat yang konstan, Anda dapat berjalan melewatinya beberapa kali dan benar-benar memahami cara kerjanya. Dalam praktiknya, yang terbaik adalah mengacak pivot untuk menghindari runtime O (N ^ 2).

def quicksort10(alist):
    quicksort_helper10(alist, 0, len(alist)-1)

def quicksort_helper10(alist, first, last):
    """  """
    if first < last:
        split_point = partition10(alist, first, last)
        quicksort_helper10(alist, first, split_point - 1)
        quicksort_helper10(alist, split_point + 1, last)

def partition10(alist, first, last):
    done = False
    pivot_value = alist[first]
    leftmark = first + 1
    rightmark = last
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivot_value:
            leftmark = leftmark + 1
        while leftmark <= rightmark and alist[rightmark] >= pivot_value:
            rightmark = rightmark - 1

        if leftmark > rightmark:
            done = True
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp
    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp
    return rightmark

def quick_sort(l):
    if len(l) == 0:
        return l
    pivot = l[0]
    pivots = [x for x in l if x == pivot]
    smaller = quick_sort([x for x in l if x < pivot])
    larger = quick_sort([x for x in l if x > pivot])
    return smaller + pivots + larger

Contoh lengkap dengan variabel yang dicetak pada langkah partisi:

def partition(data, p, right):
    print("\n==> Enter partition: p={}, right={}".format(p, right))
    pivot = data[right]
    print("pivot = data[{}] = {}".format(right, pivot))

    i = p - 1  # this is a dangerous line

    for j in range(p, right):
        print("j: {}".format(j))
        if data[j] <= pivot:
            i = i + 1
            print("new i: {}".format(i))
            print("swap: {} <-> {}".format(data[i], data[j]))
            data[i], data[j] = data[j], data[i]

    print("swap2: {} <-> {}".format(data[i + 1], data[right]))
    data[i + 1], data[right] = data[right], data[i + 1]
    return i + 1


def quick_sort(data, left, right):
    if left < right:
        pivot = partition(data, left, right)
        quick_sort(data, left, pivot - 1)
        quick_sort(data, pivot + 1, right)

data = [2, 8, 7, 1, 3, 5, 6, 4]

print("Input array: {}".format(data))
quick_sort(data, 0, len(data) - 1)
print("Output array: {}".format(data))

def is_sorted(arr): #check if array is sorted
    for i in range(len(arr) - 2):
        if arr[i] > arr[i + 1]:
            return False
    return True

def qsort_in_place(arr, left, right): #arr - given array, #left - first element index, #right - last element index
    if right - left < 1: #if we have empty or one element array - nothing to do
        return
    else:
        left_point = left #set left pointer that points on element that is candidate to swap with element under right pointer or pivot element
        right_point = right - 1 #set right pointer that is candidate to swap with element under left pointer

        while left_point <= right_point: #while we have not checked all elements in the given array
            swap_left = arr[left_point] >= arr[right] #True if we have to move that element after pivot
            swap_right = arr[right_point] < arr[right] #True if we have to move that element before pivot

            if swap_left and swap_right: #if both True we can swap elements under left and right pointers
                arr[right_point], arr[left_point] = arr[left_point], arr[right_point]
                left_point += 1
                right_point -= 1
            else: #if only one True we don`t have place for to swap it
                if not swap_left: #if we dont need to swap it we move to next element
                    left_point += 1
                if not swap_right: #if we dont need to swap it we move to prev element
                    right_point -= 1

        arr[left_point], arr[right] = arr[right], arr[left_point] #swap left element with pivot

        qsort_in_place(arr, left, left_point - 1) #execute qsort for left part of array (elements less than pivot)
        qsort_in_place(arr, left_point + 1, right) #execute qsort for right part of array (elements most than pivot)

def main():
    import random
    arr = random.sample(range(1, 4000), 10) #generate random array
    print(arr)
    print(is_sorted(arr))
    qsort_in_place(arr, 0, len(arr) - 1)
    print(arr)
    print(is_sorted(arr))

if __name__ == "__main__":
    main()

Algoritma ini tidak menggunakan fungsi rekursif.

Membiarkan Nmenjadi daftar nomor dengan len(N) > 0. SetK = [N] dan jalankan program berikut.

Catatan: Ini adalah algoritme pengurutan yang stabil .

def BinaryRip2Singletons(K, S):
    K_L = []
    K_P = [ [K[0][0]] ] 
    K_R = []
    for i in range(1, len(K[0])):
        if   K[0][i] < K[0][0]:
            K_L.append(K[0][i])
        elif K[0][i] > K[0][0]:
            K_R.append(K[0][i])
        else:
            K_P.append( [K[0][i]] )
    K_new = [K_L]*bool(len(K_L)) + K_P + [K_R]*bool(len(K_R)) + K[1:]
    while len(K_new) > 0:
        if len(K_new[0]) == 1:
            S.append(K_new[0][0])
            K_new = K_new[1:]
        else: 
            break
    return K_new, S

N = [16, 19, 11, 15, 16, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1]
K = [ N ]
S = []

print('K =', K, 'S =', S)
while len(K) > 0:
    K, S = BinaryRip2Singletons(K, S)
    print('K =', K, 'S =', S)

OUTPUT PROGRAM:

K = [[16, 19, 11, 15, 16, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1]] S = []
K = [[11, 15, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1], [16], [16], [19]] S = []
K = [[10, 4, 10, 5, 2, 3, 4, 7, 1], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[4, 5, 2, 3, 4, 7, 1], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[2, 3, 1], [4], [4], [5, 7], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[5, 7], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = [1, 2, 3, 4, 4]
K = [[15, 12, 14], [16], [16], [19]] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11]
K = [[12, 14], [15], [16], [16], [19]] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11]
K = [] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11, 12, 14, 15, 16, 16, 19]

Mungkin hanya hal preferensi, tetapi saya ingin menambahkan validasi ke bagian atas fungsi saya.

def quicksort(arr):
  if len(arr) <= 1:
    return arr

  left  = []
  right = []
  equal = []
  pivot = arr[-1]
  for num in arr:
    if num < pivot:
      left.append(num)
    elif num == pivot:
      equal.append(num)
    else:
      right.append(num)

  return quicksort(left) + equal + quicksort(right)