Quick Sort

Quick Sort #1

def qsort(arr):
    low = 0
    high = len(arr) - 1
    _sort(arr, low, high)

    return arr

def _sort(arr, low, high):

    if low < high:
        pivot = partition(arr, low, high)
        _sort(arr, low, pivot - 1)
        _sort(arr, pivot + 1, high)

    return arr


def partition(arr, low, high):

    pivot = arr[high]
    # swap location
    i = low - 1
    # swap values less than the pivot
    for j in range(low, high):

        if arr[j] <= pivot:

            # increment the swapping location
            i += 1
            arr[j], arr[i] = arr[i], arr[j]

    # swap the pivot with the next swapping location
    i += 1
    arr[i], arr[high] = arr[high], arr[i]

    return i


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

Quick Sort #2

def qsort(arr):
    low = 0
    high = len(arr) - 1
    return _sort(arr, low, high)


def _sort(arr, low, high):

    # Run the partition and sort while the low index
    # is less than the high index
    if low < high:

        # partition array around a pivot
        # return the pivot location
        pvt = partition(arr, low, high)

        # sort the lower and upper partitions
        _sort(arr, low, pvt - 1)
        _sort(arr, pvt + 1, high)

    return arr

def partition(arr, low, high):

    # Select a pivot value
    pvt = arr[high]

    # Partition each value around pivot
    # Swap smaller values to the left
    wall = low - 1

    for spt in range(low, high):

        # Compare element with pvt
        # Increment wall spot and swap
        if arr[spt] <= pvt:
            wall += 1
            arr[spt], arr[wall] = arr[wall], arr[spt]


    # Swap pivot with next wall spot
    # Return the pivot
    wall += 1
    arr[high], arr[wall] = arr[wall], arr[high]

    return wall


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

Quick Sort #3

def qsort(arr):
    left = 0
    right = len(arr) - 1

    return _qsort(arr, left, right)


def _qsort(arr, left, right):

    if left <= right:

        pvt = partition(arr, left, right)
        _qsort(arr, left, pvt - 1)
        _qsort(arr, pvt + 1, right)

    return arr


def partition(ar, left, right):

    pivot = right
    swap_spot = left - 1

    for instance in range(left, right):

        # print_sort_status(arr, left, right, swap_spot, instance)

        if ar[instance] <= ar[pivot]:

            swap_spot += 1
            ar[instance], ar[swap_spot] = ar[swap_spot], ar[instance]

    # Swap pivot value
    swap_spot += 1
    ar[pivot], ar[swap_spot] = ar[swap_spot], ar[pivot]

    return swap_spot


def test_sort():

    a1 = [1, 5, 7, 3, 8, 2, 4, 8, 9, 10]
    print(qsort(a1))


def print_sort_status(arr, l, r, s, i):
    if arr[i] <= arr[r]:
        print(' '.join(map(str, arr)),
              '\nleft: {} ({})\nright: {} ({})\nswap spot:'
              ' {}\nindex: {}\n\n'.format(l, arr[l], r, arr[r], s, i))
    else:
        print(' '.join(map(str, arr)), ' <-- no swap'
              '\nleft: {}\nright: {}\nswap spot:'
              ' {}\nindex: {}\n\n'.format(l, r, s, i))


test_sort()

Quick Sort #4

def qsort(arr):

    # Initialize the left
    # and right side of the array
    left = 0
    right = len(arr) - 1

    # Run a private helper function
    return _qsort(arr, left, right)


def _qsort(arr, left, right):

    # base case: left side is lower than right
    if left < right:

        # Partition returns the placement of the pivot.
        # Placement of pivot splits the array into
        # higher and lower
        pivot = partition(arr, left, right)

        _qsort(arr, left, pivot - 1)
        _qsort(arr, pivot + 1, left)

    return arr


def partition(arr, left, right):

    # Pick a pivot
    pivot = right

    # initialize the swap location
    swap_spot = left - 1

    if left < right:

        # run through each element, compare to pivot
        for instance in range(left, right):

            if arr[instance] <= arr[pivot]:

                # move up the swap spot
                # switch it out with the found small elemnt
                swap_spot += 1
                arr[swap_spot], arr[instance] = arr[instance], arr[swap_spot]

        # All the spots have been compared
        # and swapped, final step is swap the pivot
        swap_spot += 1
        arr[swap_spot], arr[instance]

    return swap_spot