Quicksort with Python

Quicksort with Python

def sort(array):
    """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

Quicksorting a given list in Python, while printing each step

Your instructor has made an invalid assumption: that you will implement the quicksort as an in-place sort, rather than the divide-and-conquer that you used. That in-place assumption does have merit, in that it performs much less data movement: your routine creates three new lists on every call, rather than merely swapping list elements as needed. However, here's a partial attempt to mollify your instructor, highlighting your method:

def quick_sort(lst):
    if lst == []:   return []
    pivot = lst[0]
    left = [x for x in lst[1:] if x < pivot]
    right = [x for x in lst[1:] if x > pivot]
    print(lst, pivot, "is pivot", left, "and", right, "should be sorted")
    new_list = quick_sort(left) + [pivot] + quick_sort(right)
    print("NEW", new_list)
    return new_list

quick_sort([4, 1, 5, 3, 2])

3 way Quick Sort in Python

Welcome to StackOverflow. The problem seems to be here:

k = random.randint(l, r)
a[l], a[k] = a[k], a[l]

You are getting a random index k and using it to swap two elements a[l] and a[k] randomly. Removing the two lines should give the correct output only looks right in certain circumstances.

I'm assuming you're looking to create a random pivot point, in which case you should use the random index as a pivot inside the partition3 function.

Edit: The problem was not processing/skipping the new element at a[i] after swapping inside a[i] > pivot:. It should be:

elif a[i] > pivot:
  a[i], a[iterable_length] = a[iterable_length], a[i]
  iterable_length -= 1
  # don't forget to process new element at a[i]
  i -= 1 

Python- How to implement quick sort when middle element is the pivot?

Using Hoare partition scheme is better suited to using the middle value as pivot, and Hoare partition scheme is typically faster than the Lomuto partition scheme used in the question.

def qsort(a, lo, hi):
    if(lo >= hi):
        return
    p = a[(lo + hi) // 2]       # pivot, any a[] except a[hi]
    i = lo - 1
    j = hi + 1
    while(1):
        while(1):               # while(a[++i] < p)
            i += 1
            if(a[i] >= p):
                break
        while(1):               # while(a[--j] < p)
            j -= 1
            if(a[j] <= p):
                break
        if(i >= j):
            break
        a[i],a[j] = a[j],a[i]
    qsort(a, lo, j)
    qsort(a, j+1, hi)

As commented above, if you still want to use Lomuto partition scheme, swap the middle element with the last element and use your code with the last element.

How to quick sort list of objects by different attributes using the same method?

You can achieve this by defining another method inside your class:

class Metric:
    b_date = "birth_date"
    h_date = "hire_date"
    zip_code = "zip_code"
    name = "name"

class Member:
    def __init__(self, name, zip, hire_date, birth_date):
        self.id = id
        self.name = name
        self.zip = zip
        self.hire_date = hire_date
        self.birth_date = birth_date

    def get_name(self):
        return self.name

    def get_birth_date(self):
        return self.birth_date

    def get_hire_date(self):
        return self.hire_date

    def get_zip_code(self):
        return self.zip

    def get_metric_value(self, metric):
        if metric == Metric.b_date:
            return self.get_birth_date()
        elif metric == Metric.h_date:
            return self.get_hire_date()
        elif metric == Metric.zip_code:
            return self.get_zip_code()
        elif metric == Metric.name:
            return self.get_name()

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

def quicksort(array, metric, 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, metric)
        _quicksort(array, begin, pivot-1)
        _quicksort(array, pivot+1, end)
    return _quicksort(array, begin, end)

quicksort(array, Metric.zip_code)  # or any other metric ...

Python: Quicksort with median of three

Let us first implement the median-of-three for three numbers, so an independent function. We can do that by sorting the list of three elements, and then return the second element, like:

def median_of_three(a, b, c):
    return sorted([a, b, c])[1]

Now for a range low .. high (with low included, and high excluded), we should determine what the elements are for which we should construct the median of three:

1. the first element: L[low],
2. the last element L[high-1], and
3. the middle element (in case there are two such, take the first) L[(low+high-1)//2].

So now we only need to patch the partitioning function to:

def Partition(L, low, high, ascending = True):
    print('Quicksort, Parameter L:')
    print(L)
    result = 0 
    pivot = median_of_three(L[low], L[(low+high-1)//2], L[high-1])
    i = low + 1  
    for j in range(low + 1, high, 1): 
        result += 1
        if (ascending and L[j] < pivot) or (not ascending and L[j] > pivot):
            L[i], L[j] = L[j], L[i]  
            i += 1  
    L[low], L[i-1] = L[i-1], L[low] 
    return i - 1, result

EDIT: determining the median of three elements.

The median of three elements is the element that is in the middle of the two other values. So in case a <= b <= c, then b is the median.

So we need to determine in what order the elements are, such that we can determine the element in the middle. Like:

def median_of_three(a, b, c):
    if a <= b and b <= c:
        return b
    if c <= b and b <= a:
        return b
    if a <= c and c <= b:
        return c
    if b <= c and c <= a:
        return c
    return a

So now we have defined the median of three with four if cases.

EDIT2: There is still a problem with this. After you perform a pivot, you swap the element L[i-1] with L[low] in your original code (the location of the pivot). But this of course does not work anymore: since the pivot now can be located at any of the three dimensions. Therfore we need to make the median_of_three(..) smarter: not only should it return the pivot element, but the location of that pivot as well:

def median_of_three(L, low, high):
    mid = (low+high-1)//2
    a = L[low]
    b = L[mid]
    c = L[high-1]
    if a <= b <= c:
        return b, mid
    if c <= b <= a:
        return b, mid
    if a <= c <= b:
        return c, high-1
    if b <= c <= a:
        return c, high-1
    return a, low

Now we can solve this problem with:

def Partition(L, low, high, ascending = True):
    print('Quicksort, Parameter L:')
    print(L)
    result = 0 
    pivot, pidx = median_of_three(L, low, high)
    i = low + (low == pidx)
    for j in range(low, high, 1):
        if j == pidx:
            continue
        result += 1
        if (ascending and L[j] < pivot) or (not ascending and L[j] > pivot):
            L[i], L[j] = L[j], L[i]  
            i += 1 + (i+1 == pidx)
    L[pidx], L[i-1] = L[i-1], L[pidx] 
    return i - 1, result

EDIT3: cleaning it up.

Although the above seems to work, it is quite complicated: we need to let i and j "skip" the location of the pivot.

It is probably simpler if we first move the pivot to the front of the sublist (so to the low index):

def Partition(L, low, high, ascending = True):
    print('Quicksort, Parameter L:')
    print(L)
    result = 0 
    pivot, pidx = median_of_three(L, low, high)
    L[low], L[pidx] = L[pidx], L[low]
    i = low + 1
    for j in range(low+1, high, 1):
        result += 1
        if (ascending and L[j] < pivot) or (not ascending and L[j] > pivot):
            L[i], L[j] = L[j], L[i]  
            i += 1
    L[low], L[i-1] = L[i-1], L[low] 
    return i - 1, result

---

Related Topics