Ik ben helemaal nieuw in python en ik probeer quicksort erin te implementeren.
Kan iemand me alsjeblieft helpen mijn code te voltooien?

Ik weet niet hoe ik de drie arrays moet samenvoegen en afdrukken.

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)

Antwoord 1, autoriteit 100%

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

Antwoord 2, autoriteit 61%

Snel sorteren zonder extra geheugen (op zijn plaats)

Gebruik:

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

def partition(array, begin, end):
    pivot = begin
    for i in range(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)

Antwoord 3, Autoriteit 28%

Er is nog een beknopte en mooie versie

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]])

Laat me de bovenstaande codes uitleggen voor details

1. Kies het eerste element van array arr[0]ALS PIVOT

   [arr[0]]

2. qsortdie elementen van array die minder zijn dan draaien met List Comprehension

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

3. qsortDie elementen van array die groter zijn dan het draaien met List Comprehension

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

Antwoord 4, Autoriteit 16%

Dit antwoordis een in-place QuickSort voor Python 2.x. Mijn antwoord is een interpretatie van de in-place oplossing van Rosetta Codedie werkt voor Python 3ook:

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)

En als u bereid bent af te zien van de in-place eigenschap, is hieronder nog een andere versie die de basisideeën achter quicksort beter illustreert. Afgezien van de leesbaarheid, is het andere voordeel dat het stabielis (gelijke elementen verschijnen in de gesorteerde lijst in dezelfde volgorde als vroeger in de ongesorteerde lijst). Deze stabiliteitseigenschap gaat niet op bij de minder geheugenverslindende interne implementatie die hierboven is weergegeven.

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

Antwoord 5, autoriteit 12%

Quicksort met Python

In het echte leven zouden we altijd de ingebouwde sortering van Python moeten gebruiken. Het is echter leerzaam om het quicksort-algoritme te begrijpen.

Mijn doel hier is om het onderwerp zo op te splitsen dat het gemakkelijk te begrijpen en reproduceerbaar is door de lezer zonder terug te hoeven gaan naar referentiemateriaal.

Het quicksort-algoritme is in wezen het volgende:

1. Selecteer een spilgegevenspunt.
2. Verplaats alle gegevenspunten kleiner dan (onder) het draaipunt naar een positie onder het draaipunt – verplaats die punten groter dan of gelijk aan (boven) het draaipunt naar een positie erboven.
3. Pas het algoritme toe op de gebieden boven en onder het draaipunt

Als de gegevens willekeurig zijn verdeeld, is het selecteren van het eerste gegevenspunt als spil gelijk aan een willekeurige selectie.

Leesbaar voorbeeld:

Laten we eerst eens kijken naar een leesbaar voorbeeld dat opmerkingen en namen van variabelen gebruikt om naar tussenliggende waarden te verwijzen:

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

Om het hier gedemonstreerde algoritme en de code te herhalen: we verplaatsen waarden boven het draaipunt naar rechts en waarden onder het draaipunt naar links, en geven die partities vervolgens door aan dezelfde functie om verder te sorteren.

Golfen:

Dit kan worden uitgebreid tot 88 tekens:

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]])

Om te zien hoe we daar komen, neem eerst ons leesbare voorbeeld, verwijder opmerkingen en docstrings en zoek de spil op zijn plaats:

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

Zoek nu onder en boven, ter plaatse:

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

Nu we weten dat andhet vorige element retourneert indien onwaar, anders als het waar is, evalueert het en retourneert het het volgende element, we hebben:

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]]))

Aangezien lambda’s een enkele epression retourneren, en we hebben vereenvoudigd tot een enkele expressie (ook al wordt het onleesbaarder), kunnen we nu een lambda gebruiken:

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]]))

En om naar ons voorbeeld te verkorten, verkort u de functie en variabele namen op één letter en elimineer de witruimte die niet vereist is.

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]])

Merk op dat deze lambda, zoals de meeste code golfen, nogal slechte stijl is.

In-Place QuickSort, met behulp van de HOEAR Partitioning-regeling

De eerdere implementatie creëert veel onnodige extra lijsten. Als we dit in de plaats kunnen doen, vermijden we het verspillen van de ruimte.

De onderstaande implementatie maakt gebruik van het HOEAR-partitioneringsschema, dat u Meer lezen over op wikipedia (maar we hebben blijkbaar tot 4 overtollige berekeningen per partition()bellen door met behulp van while-lus-semantiek in plaats van do-while en het verplaatsen van de vernauwingstappen naar het einde van de buitenste lus.) .

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

Ik weet niet zeker of ik het grondig genoeg heb getest:

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]

Conclusie

Dit algoritme wordt vaak onderwezen in cursussen informatica en gevraagd tijdens sollicitatiegesprekken. Het helpt ons na te denken over recursie en verdeel-en-heers.

Quicksort is niet erg praktisch in Python, aangezien ons ingebouwde timsort-algoritme behoorlijk efficiënt is, en we recursielimieten hebben. We verwachten dat lijsten ter plekke worden gesorteerd met list.sortof maak nieuwe gesorteerde lijsten met sorted– beide hebben een keyen reverseargument.

Antwoord 6, autoriteit 7%

Er zijn hier al veel antwoorden op, maar ik denk dat deze aanpak de meest zuivere implementatie is:

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

Je kunt natuurlijk alles in variabelen opslaan en ze meteen als volgt teruggeven:

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]])

Antwoord 7, autoriteit 3%

functionele aanpak:

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)

Antwoord 8, autoriteit 2%

Eenvoudige implementatie van grokking-algoritmen

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)

Antwoord 9

functionele programmeerbenadering

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]

Antwoord 10

Dit is een versie van de quicksort die gebruik maakt van het Hoare-partitieschema en met minder swaps en lokale variabelen

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)

Antwoord 11

Partitie– Splits een array door een spil zodat kleinere elementen naar links worden verplaatst en grotere elementen naar rechts of vice versa. Een pivot kan een willekeurig element uit een array zijn. Om dit algoritme te maken, moeten we weten wat de begin- en eindindex van een array is en waar een spil is. Stel vervolgens twee hulpwijzers L, R in.

We hebben dus een arraygebruiker[…,begin,…,end,…]

De startpositie van L- en R-aanwijzers
[…,begin,volgende,…,eind,…]
     R       L

terwijl L < einde
  1. Als een gebruiker[pivot] > gebruiker[L] verplaats vervolgens R één en verwissel gebruiker[R] met gebruiker[L]
  2. verplaats L met één

Na while wissel gebruiker[R] met gebruiker[pivot]

Snel sorteren– Gebruik het partitie-algoritme totdat elk volgend deel van de splitsing door een spil een beginindex heeft die groter of gelijk is aan de eindindex.

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)

Antwoord 12

Ik denk dat beide antwoorden hier goed werken voor de verstrekte lijst (die de oorspronkelijke vraag beantwoordt), maar zou breken als een array met niet-unieke waarden wordt doorgegeven. Dus voor de volledigheid wil ik alleen wijzen op de kleine fout in elk en uitleggen hoe je ze kunt oplossen.

Probeer bijvoorbeeld de volgende array [12,4,5,6,7,3,1,15,1] te sorteren (merk op dat 1 twee keer voorkomt) met Brionius-algoritme .. zal op een gegeven moment eindigen met de minderarray leeg en de equalarray met een paar waarden (1,1) die niet kan worden gescheiden in de volgende iteratie en de len() > 1…daarom krijg je een oneindige lus

Je kunt het oplossen door een array terug te geven als lessleeg is of beter door nietsort aan te roepen in je gelijke array, zoals in zangwantwoord

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)
            elif x == pivot:
                equal.append(x)
            else: # 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

De liefhebber-oplossing breekt ook, maar om een andere reden ontbreekt de return-clausule in de recursieregel, waardoor op een gegeven moment None wordt geretourneerd en wordt geprobeerd deze aan een lijst toe te voegen ….

Om het op te lossen, voegt u gewoon een return toe aan die regel

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]])

Antwoord 13

Of als u de voorkeur geeft aan een one-liner die ook het Python-equivalent van C/C++ varags, lambda-expressies en if-expressies illustreert:

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])

Antwoord 14

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)

Antwoord 15

Ik weet dat veel mensen deze vraag correct hebben beantwoord en ik heb ze met plezier gelezen. Mijn antwoord is bijna hetzelfde als zangw, maar ik denk dat de vorige bijdragers er niet goed in zijn geslaagd om visueel uit te leggen hoe dingen echt werken… dus hier is mijn poging om anderen te helpen die deze vraag/antwoorden in de toekomst zouden kunnen bezoeken over een eenvoudige oplossing voor quicksort-implementatie.

Hoe werkt het?

1. We selecteren in feite het eerste item als onze spil uit onze lijst en dan maken we twee sublijsten.
2. Onze eerste sublijst bevat de items die kleiner zijn dan pivot
3. Onze tweede sublijst bevat onze items die groter zijn dan of gelijk zijn aan pivot
4. We sorteren ze dan snel en combineren ze de eerste groep + pivot + de tweede groep om het eindresultaat te krijgen.

Hier is een voorbeeld samen met een bijbehorende visuele …
(draaipunt)9,11,2,0

gemiddelde: n log van n

slechter geval: n^2

De code:

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)

items=[9,11,2,0]
print(quicksort(items))

Antwoord 16

Het algoritme bevat twee grenzen, één met elementen die kleiner zijn dan de spil (bijgehouden door index ‘j’) en de andere met elementen die groter zijn dan de spil (bijgehouden door index ‘i’).

In elke iteratie wordt een nieuw element verwerkt door j te verhogen.

Invariant:-

1. alle elementen tussen pivot en i zijn kleiner dan de pivot, en
2. alle elementen tussen i en j zijn groter dan de spil.

Als de invariant wordt geschonden, worden de elementen ith en jth verwisseld, en i
wordt verhoogd.

Nadat alle elementen zijn verwerkt en alles na de spil
is gepartitioneerd, wordt het pivot-element verwisseld met het laatste element
kleiner dan het.

Het pivot-element staat nu op de juiste plaats in de reeks. De
elementen ervoor zullen minder zijn dan het en degenen erna zullen zijn
groter dan dit, en ze zullen ongesorteerd zijn.

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))

Een spil selecteren

Een “goede” pivot resulteert in twee subreeksen van ongeveer hetzelfde
maat. Deterministisch kan een spilelement worden geselecteerd in a
naïeve manier of door de mediaan van de reeks te berekenen.

Een naïeve implementatie van het selecteren van een spil zal de eerste of laatste zijn
element. De runtime in het slechtste geval is in dit geval wanneer de invoer
reeks is al gesorteerd of omgekeerd gesorteerd, als een van de subreeksen
zal leeg zijn, waardoor er slechts één element per . wordt verwijderd
recursieve oproep.

Een perfect uitgebalanceerde splitsing wordt bereikt wanneer de spil de mediaan is
element van de reeks. Er zijn een gelijk aantal elementen groter
dan het en minder dan het. Deze aanpak garandeert een betere overall
looptijd, maar kost veel meer tijd.

Een niet-deterministische/willekeurige manier om de spil te selecteren zou zijn om te kiezen
een element uniform willekeurig. Dit is een eenvoudig en lichtgewicht
aanpak die het worstcasescenario minimaliseert en ook leidt tot een
ongeveer evenwichtige verdeling. Dit zorgt ook voor een balans tussen de naïeve benadering en de mediane benadering van het selecteren van de spil.

Antwoord 17

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)

Antwoord 18

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 []

Antwoord 19

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

Antwoord 20

Een “TRUE”–implementatie [Algoritmen 8.9, 8.11 van het Algoritme Design en Toepassingen Boek van Michael T. Goodrich en 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()

Antwoord 21

Het algoritme heeft 4 eenvoudige stappen:

1. Verdeel de array in 3 verschillende delen: links, draaipunt en rechts, waar draaipunt slechts één element heeft. Laten we dit draaipuntelement kiezen als het eerste element van array
2. Voeg elementen toe aan het betreffende onderdeel door ze te vergelijken met het draaielement. (uitleg in opmerkingen)
3. Herhaal dit algoritme totdat alle elementen in de array zijn gesorteerd
4. Tot slot, voeg de linker+pivot+rechter delen samen

Code voor het algoritme in 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])

Ga door met dit algoritme recursief met het linker- en rechtergedeelte.

Antwoord 22

Nog een quicksort-implementatie:

# 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)

Antwoord 23

voor versie Python 3.x : een functionele stijl met operatorModule, voornamelijk om de leesbaarheid te verbeteren.

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))

en wordt getest als

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

Antwoord 24

Hier is een eenvoudige implementatie: –

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]))

Antwoord 25

Mijn antwoord lijkt erg op dat van @alisianoi. Ik geloofechter dat er een lichte inefficiëntie in zijn code zit (zie mijn commentaar), die ik heb verwijderd. Bovendien heb ik meer uitleg toegevoegd en was ik wat specifieker over het probleem van dubbele (draai)waarden.

def quicksort(nums, begin=0, end=None):
    # Only at the beginning end=None. In this case set to len(nums)-1
    if end is None: end = len(nums) - 1
    # If list part is invalid or has only 1 element, do nothing
    if begin>=end: return
    # Pick random pivot
    pivot = nums[random.randint(begin, end)]
    # Initialize left and right pointers
    left, right = begin, end
    while left < right:
        # Find first "wrong" value from left hand side, i.e. first value >= pivot
        # Find first "wrong" value from right hand side, i.e. first value <= pivot
        # Note: In the LAST while loop, both left and right will point to pivot!
        while nums[left] < pivot: left += 1
        while nums[right] > pivot: right -= 1
        # Swap the "wrong" values
        if left != right:
            nums[left], nums[right] = nums[right], nums[left]
            # Problem:  loop can get stuck if pivot value exists more than once. Simply solve with...
            if nums[left] == nums[right]:
                assert nums[left]==pivot
                left += 1
    # Now, left and right both point to a pivot value.
    # All values to its left are smaller (or equal in case of duplicate pivot values)
    # All values to its right are larger.
    assert left == right and nums[left] == pivot
    quicksort(nums, begin, left - 1)
    quicksort(nums, left + 1, end)
    return

Zonder recursie:

def quicksort(nums, ranges=None):
    if ranges is None:
        ranges = [[0, len(nums) - 1]]
    while ranges != []:
        [start, end] = ranges[0]
        ranges = ranges[1:]
        if start >= end:
            continue
        pivot = nums[randint(start, end)]
        left = start
        right = end
        while left < right:
            while nums[left] < pivot:
                left += 1
            while nums[right] > pivot:
                right -= 1
            if left != right:
                nums[left], nums[right] = nums[right], nums[left]
                if nums[left] == nums[right]:
                    left += 1
        ranges = [[start, left - 1], [left + 1, end]] + ranges

Antwoord 26

1. Eerst declareren we de eerste waarde in de array als de
   pivot_value en we stellen ook de linker- en rechtermarkeringen in
2. We maken de eerste while-lus, deze while-lus is er om te vertellen
   het partitieproces opnieuw uitvoeren als het niet voldoet aan de
   noodzakelijke voorwaarde
3. dan passen we het partitieproces toe
4. nadat beide partitieprocessen zijn uitgevoerd, controleren we of het
   voldoet aan de juiste staat. Als dit het geval is, markeren we het als voltooid,
   zo niet, dan wisselen we de linker- en rechterwaarden en passen we deze opnieuw toe
5. Zodra het klaar is, schakelt u de linker- en rechterwaarden om en retourneert u de
   split_point

Ik voeg de onderstaande code toe! Deze quicksort is een geweldig leermiddel vanwege de Locatie van de spilwaarde. Omdat het zich op een constante plaats bevindt, kun je er meerdere keren doorheen lopen en echt onder de knie krijgen hoe het allemaal werkt. In de praktijk is het het beste om de spil willekeurig te verdelen om O(N^2) runtime te vermijden.

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

Antwoord 27

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

Antwoord 28

Volledig voorbeeld met afgedrukte variabelen bij partitiestap:

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))

Antwoord 29

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()

Antwoord 30

Dit algoritme gebruikt geen recursieve functies.

Laat Neen willekeurige lijst met getallen zijn met len(N) > 0. Stel K = [N]in en voer het volgende programma uit.

Opmerking: dit is een stabielsorteeralgoritme.

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)

PROGRAMMA-UITVOER:

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]