Quicksort

Data Structures and Algorithms in Python

Miriam Antona

Software engineer

Quicksort

  • Follows divide and conquer principle
  • Implemented by many programming languages
  • Partition technique
    • Pivot
    • items smaller than the pivot -> left
    • items greater than the pivot -> right
  • Elements to the left will be sorted recursively
  • Elements to the right will be sorted recursively
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers.

Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first element is colored in blue.

  • Hoare's partition
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first element is colored in blue. There are two pointers. The left pointer points to the second element and the right pointer points to the last element.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first element is colored in blue. There are two pointers. The left pointer points to the third element and the right pointer points to the last element.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first element is colored in blue. There are two pointers. The left pointer points to the third element and the right pointer points to the fifth element.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first element is colored in blue. There are two pointers. The left pointer points to the third element and the right pointer points to the fifth element. The are two arrows that represent that the third and the fifth elements will be swapped.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first element is colored in blue. There are two pointers. The left pointer points to the third element and the right pointer points to the fifth element. The third and the fifth elements have been swapped.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first element is colored in blue. There are two pointers. The left pointer points to the forth element and the right pointer points to the fifth element.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first element is colored in blue. There are two pointers. The left pointer points to the forth element and the right pointer points to the forth element.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first element is colored in blue. There are two pointers. The left pointer points to the forth element and the right pointer points to the third element.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first element is colored in blue. There are two pointers. The left pointer points to the forth element and the right pointer points to the third element. There are two arrows that represent that the first and the third elements will be swapped.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The third element is colored in blue. The first and the third elements have been swapped.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The third element is colored in green.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The third element is colored in green and the first two elements in orange, representing the left part of the list.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first element is colored in blue, the second element in orange, and the third element in green. The left and right pointers point to the second element.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first element is colored in blue, the second element in orange, and the third element in green. The left and right pointers point to the second element. There are two rows that represent that the first and the second elements will be swapped.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first element is colored in blue, the second element in orange, and the third element in green. The left and right pointers point to the second element. The first and the second elements have been swapped.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first element is colored in orange, and the second and third elements in green.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first, second, and third elements are colored in green.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first, second, and third elements are colored in green. The right part of the list is colored in orange.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first, second, and third elements are colored in green. The first element of the right part is colored in blue. The left pointer points to second element of the right part and the right pointer to the last element of the right part.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first, second, and third elements are colored in green. The first element of the right part is colored in blue. The left and right pointers point to second element of the right part of the list.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first, second, and third elements are colored in green. The first element of the right part is colored in blue. The left pointer points to first element of the right part and the right pointer to the second element of the right part.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first, second, third, and forth elements are colored in green, and the fifth and sixth elements in orange.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first, second, third, and forth elements are colored in green. The element is colored in blue. The left and right pointers point to the last element.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first, second, third, and forth elements are colored in green. The element is colored in blue. The left and right pointers point to the last element. There are two arrows that represent that the fifth and sixth elements will be swapped.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. The first, second, third, and forth elements are colored in green. The element is colored in blue. The left and right pointers point to the last element. The fifth and sixth elements have been swapped.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - in action

A schematic representation of a list with unordered numbers. All the elements are colored in green because they are sorted.

  • Hoare's partition
    • Move left pointer until a value greater than pivot is found
    • Move right pointer until a value lower than pivot is found
Data Structures and Algorithms in Python

Quicksort - implementation

def quicksort(my_list, first_index, last_index):

    if first_index < last_index:

        partition_index = partition(my_list, first_index, last_index)

        quicksort(my_list, first_index, partition_index)

        quicksort(my_list, partition_index + 1, last_index)
Data Structures and Algorithms in Python

Quicksort - implementation

def partition(my_list, first_index, last_index):

    pivot = my_list[first_index]
    left_pointer = first_index + 1
    right_pointer = last_index

    while True: 
        while my_list[left_pointer] < pivot and left_pointer < last_index:
            left_pointer += 1

        while my_list[right_pointer] > pivot and right_pointer >= first_index:
            right_pointer -= 1

        if left_pointer >= right_pointer:
            break

        my_list[left_pointer], my_list[right_pointer] = my_list[right_pointer], my_list[left_pointer]

    my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]

    return right_pointer
Data Structures and Algorithms in Python

Quicksort - implementation

my_list = [6, 2, 9, 7, 4, 8] 
quicksort(my_list, 0, len(my_list) - 1)
print(my_list)

[2, 4, 6, 7, 8, 9]
Data Structures and Algorithms in Python

Quicksort - complexity

  • Worst case: $O(n^2)$
  • Very efficient!
    • Average case: $\Theta(n\log{}n)$
    • Best case: $\Omega(n\log{}n)$
  • Space complexity: $O(n\log{}n)$
Data Structures and Algorithms in Python

Let's practice!

Data Structures and Algorithms in Python

Preparing Video For Download...