3
\$\begingroup\$

QuickSort is a Divide and Conquer algorithm, which picks an element as "pivot" and partitions a given list around the pivot. There are many different versions of Quick Sort, as to how to pick a pivot in different ways:

  • Always pick first element as pivot (implemented below)
  • Always pick last element as pivot
  • Pick a random element as pivot
  • Pick median as pivot

Just for practicing, I've implemented the quick sort algorithm, and if you'd like to review it and provide any change/improvement recommendations, please do so, and I appreciate that.

Code

import random
from typing import TypeVar, List
from scipy import stats

T = TypeVar('T')


def quick_sort(input_list: List[T]) -> List[T]:
    """"
    Returns an ascendingly sorted list;
    Input variable is an integer or float array;
    Theoretical Complexity: O(N*Log N) Time and O(N) Memory
    """

    sort(input_list, 0, len(input_list) - 1)
    return input_list


def sort(input_list: List[T], start_index: int, end_index: int) -> None:
    """Recursively sorts the two pivot-divided sublists;"""
    if start_index >= end_index:
        return
    pivot_index = partition(input_list, start_index, end_index)
    sort(input_list, start_index, pivot_index - 1)
    sort(input_list, pivot_index + 1, end_index)


def partition(input_list: List[T], start_index: int, end_index: int) -> int:
    """
    Returns the end index; Partitions a list into two sublists;
    """
    pivot = input_list[start_index]

    i, j = start_index + 1, end_index

    while i <= j:
        while input_list[i] < pivot and i < end_index:
            i += 1
        while input_list[j] > pivot:
            j -= 1

        if i < j:
            temp = input_list[i]
            input_list[i] = input_list[j]
            input_list[j] = temp
            i += 1
            j -= 1
        else:
            break

    input_list[start_index] = input_list[j]
    input_list[j] = pivot

    return j


if __name__ == "__main__":

    # Creates a dash line string and a new line for in between the tests.
    delimiter = "-" * 70 + "\n"

    # Generates a random integer list.
    test_list_integer = random.sample(range(-100, 100), 15) * 3
    print(f"""The unsorted integer array is:
        {test_list_integer}""")
    print(delimiter)

    # Generates a random float list.
    test_list_float = stats.uniform(0, 100).rvs(45)
    print(f"""The unsorted float array is:
        {test_list_float}""")
    print(delimiter)

    # Sample float/integer test list for input.
    integer_float_input = list(test_list_integer + test_list_float)

    # Sample float/integer test list for output.
    integer_float_output = sorted(integer_float_input)

    sorting_algorithms = [
        ("Quick Sort", quick_sort)
    ]

    # Testing
    for description, func in sorting_algorithms:
        if (func(integer_float_input.copy()) == integer_float_output):
            print(f"{description} Test was Successful.")
        else:
            print(f"{description} Test was not Successful.")
        print(f"""{description} (Integer):
            {func(test_list_integer.copy())}""")
        print(f"""{description} (Float):
            {func(test_list_float.copy())}""")
        print(delimiter)

Reference

\$\endgroup\$
3
\$\begingroup\$

I'm all for providing docstrings.
I doubt the docstrings presented are helpful as can be for someone not familiar with the quicksort algorithm:

There are several things not quite pythonic in the code presented

I prefer

if not <condition>:
    <get out of here>
<operate>

over

if <condition>:
    <operate>
else:
    <get out of here>
\$\endgroup\$
  • \$\begingroup\$ I'd stress the first point even more by saying that a return value imply a new object, since modifying it in place does not invalidate the reference held by the caller. But here, the input is modified in place AND returned, which is confusing at best if not error prone. \$\endgroup\$ – 409_Conflict Sep 28 at 12:34
  • \$\begingroup\$ Concatenating immutable sequences always results in a new object This also applies to lists, which is the case here. \$\endgroup\$ – GZ0 Sep 28 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.