itu.algs4.sorting package

Submodules

itu.algs4.sorting.heap module

itu.algs4.sorting.heap.main()

Reads in a sequence of strings from stdin heapsorts them, and prints the result in ascending order.

itu.algs4.sorting.heap.sort(pq)

Rearranges the array in ascending order, using the natural order.

Parameters:pq – the array to be sorted

itu.algs4.sorting.index_min_pq module

class itu.algs4.sorting.index_min_pq.IndexMinPQ(max_n)

Bases: object

The IndexMinPQ class represents an indexed priority queue of generic keys. It supports the usual insert and delete-the-minimum operations, along with delete and change-the-key methods. In order to let the client refer to the keys on the priority queue,

an integer between 0 and maxN - 1 is associated with each key-the client uses this integer to specify which key to delete or change. It also supports methods for peeking at the minimum key, testing if the priority queue is empty, and iterating through the keys. This implementation uses a binary heap along with an array to associate keys with integers, in the given range. The insert, delete-the-minimum, delete, change-key, decrease-key, and increase-key operations take logarithmic time. The is-empty, size, min-index, min-key, and key-of operations take constant time. Construction takes time proportional to the specified capacity.

change_key(i, key)

Change the key associated with index i to the specified value.

Parameters:
  • i – the index of the key to change
  • key – change the key associated with index i to this key
Raises:
contains(i)

Is i an index on this priority queue?

Parameters:i – an index
Returns:True if i is an index on this priority queue False otherwise
Return type:bool
Raises:IllegalArgumentException – unless 0 <= i < max_n
decrease_key(i, key)

Decrease the key associated with index i to the specified value.

Parameters:
  • i – the index of the key to decrease
  • key – decrease the key associated with index i to this key
Raises:
del_min()

Removes a minimum key and returns its associated index. :return: an index associated with a minimum key :raises NoSuchElementException: if this priority queue is empty :rtype: int

delete(i)

Remove the key associated with index i.

Parameters:

i – the index of the key to remove
Raises:
increase_key(i, key)

Increase the key associated with index i to the specified value.

Parameters:
  • i – the index of the key to increase
  • key – increase the key associated with index i to this key
Raises:
insert(i, key)

Associates key with index i.

Parameters:
  • i – an index
  • key – the key to associate with index i
Raises:
is_empty()

Returns True if this priority queue is empty.

Returns:True if this priority queue is empty False otherwise
Return type:bool
key_of(i)

Returns the key associated with index i.

Parameters:

i – the index of the key to return
Returns:

the key associated with index i
Raises:
min_index()

Returns an index associated with a minimum key. :return: an index associated with a minimum key :rtype: int :raises NoSuchElementException: if this priority queue is empty

min_key()

Returns a minimum key. :return: a minimum key :raises NoSuchElementException: if this priority queue is empty

size()

Returns the number of keys on this priority queue.

Returns:the number of keys on this priority queue
Return type:int
itu.algs4.sorting.index_min_pq.main()

Inserts a bunch of strings to an indexed priority queue, deletes and prints them, inserts them again, and prints them using an iterator.

itu.algs4.sorting.insertion_sort module

The Insertion module provides static methods for sorting an array using insertion sort.

This implementation makes ~ 1/2 n^2 compares and exchanges in the worst case, so it is not suitable for sorting large arbitrary arrays. More precisely, the number of exchanges is exactly equal to the number of inversions. So, for example, it sorts a partially-sorted array in linear time. The sorting algorithm is stable and uses O(1) extra memory.

itu.algs4.sorting.insertion_sort.is_sorted(a: List[T])

Returns true if a is sorted.

Parameters:a – the array to be checked.
Returns:True if a is sorted.
itu.algs4.sorting.insertion_sort.main()

Reads in a sequence of strings from standard input; Shellsorts them; and prints them to standard output in ascending order.

itu.algs4.sorting.insertion_sort.sort(a: List[T])

Rearranges the array in ascending order, using the natural order.

Parameters:a – the array to be sorted.

itu.algs4.sorting.max_pq module

class itu.algs4.sorting.max_pq.MaxPQ(_max: int = 1)

Bases: typing.Generic

The MaxPQ class represents a priority queue of generic keys.

It supports the usual insert and delete-the-maximum operations, along with methods for peeking at the maximum key, testing if the priority queue is empty, and iterating through the keys. This implementation uses a binary heap. The insert and delete-the-maximum operations take logarithmic amortized time. The max, size and is_empty operations take constant time. Construction takes time proportional to the specified capacity.

del_max() → Key

Removes and returns a largest key on this priority queue. :return: a largest key on this priority queue :raises NoSuchElementException: if this priority queue is empty

insert(x: Key) → None

Adds a new key to this priority queue.

Parameters:x – the new key to add to this priority queue
is_empty() → bool

Returns True if this priority queue is empty.

Returns:True if this priority queue is empty otherwise False
Return type:bool
max() → Key

Returns a largest key on this priority queue. :return: a largest key on the priority queue :raises NoSuchElementException: if this priority queue is empty

size() → int

Returns the number of keys on this priority queue.

Returns:the number of keys on this priority queue
Return type:int
itu.algs4.sorting.max_pq.main()

Reads strings from stdin and adds them to a priority queue.

When reading a ‘-‘ it removes a maximum item on the priority queue and prints it to stdout. Prints the amount of items left on the priority queue

itu.algs4.sorting.merge module

itu.algs4.sorting.merge.sort(a: List[T])

Rearranges the array in ascending order, using the natural order.

Parameters:a – the array to be sorted

itu.algs4.sorting.merge_bu module

This module provides functions for sorting an array using bottom-up mergesort.

For additional documentation, see Section 2.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

itu.algs4.sorting.merge_bu.sort(a)

Rearranges the array in ascending order, using the natural order.

Parameters:a – the array to be sorted

itu.algs4.sorting.min_pq module

class itu.algs4.sorting.min_pq.MinPQ(_max: int = 1)

Bases: typing.Generic

The MinPQ class represents a priority queue of generic keys.

It supports the usual insert and delete-the-minimum operations, along with methods for peeking at the minimum key, testing if the priority queue is empty, and iterating through the keys. This implementation uses a binary heap. The insert and delete-the-minimum operations take logarithmic amortized time. The min, size and is- empty operations take constant time. Construction takes time proportional to the specified capacity.

del_min() → Key

Removes and returns a smallest key on this priority queue. :return: a smallest key on this priority queue :raises NoSuchElementException: if this priority queue is empty

insert(x: Key) → None

Adds a new key to this priority queue.

Parameters:x – the new key to add to this priority queue
is_empty() → bool

Returns True if this priority queue is empty.

Returns:True if this priority queue is empty otherwise False
Return type:bool
min() → Key

Returns a smallest key on this priority queue. :return: a smallest key on the priority queue :raises NoSuchElementException: if this priority queue is empty

size() → int

Returns the number of keys on this priority queue.

Returns:the number of keys on this priority queue
Return type:int
itu.algs4.sorting.min_pq.main()

Reads strings from stdin and adds them to a minimum priority queue.

When reading a ‘-‘ it removes the minimum element and prints it to stdout.

itu.algs4.sorting.quick3way module

The Quick3Way module provides static methods for sorting an array using quicksort with 3-way partitioning.

itu.algs4.sorting.quick3way.is_sorted(a)

Returns true if a is sorted.

Parameters:a – the array to be checked.
Returns:True if a is sorted.
itu.algs4.sorting.quick3way.main()

Reads in a sequence of strings from standard input; Shellsorts them; and prints them to standard output in ascending order.

itu.algs4.sorting.quick3way.sort(a)

Rearranges the array in ascending order using the natural order.

Parameters:a – the array to be sorted.

itu.algs4.sorting.quicksort module

The quicksort module provides methods for sorting an array and selecting the ith smallest element in an array using quicksort.

For additional documentation, see Section 2.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

original author:
 Robert Sedgewick and Kevin Wayne
original java code:
 https://algs4.cs.princeton.edu/23quicksort/Quick.java.html
itu.algs4.sorting.quicksort.is_sorted(array)
itu.algs4.sorting.quicksort.select(array, k)

Rearranges the array so that array[k] contains the kth smalles key; array[0] through array[k-1] are less than (or equal to) array[k]; and array[k+1] through array[n-1] are greather than (or equal to) array[k]

Parameters:
  • array – the array
  • k – the rank of the key
Returns:

the key of rank k
itu.algs4.sorting.quicksort.show(array)
itu.algs4.sorting.quicksort.sort(array)

Rearranges the array in ascending order, using the natural order.

itu.algs4.sorting.selection module

itu.algs4.sorting.selection.main()

Reads strings from stdin, sorts them, and prints the result to stdout.

itu.algs4.sorting.selection.sort(a)

Rearranges the array in ascending order, using the natural order.

Parameters:a – the array to be sorted

itu.algs4.sorting.shellsort module

The Shellsort module provides static methods for sorting an array using shellsort with Knuth’s increment sequence (1, 4, 13, 40, …).

itu.algs4.sorting.shellsort.is_sorted(a)

Returns true if a is sorted.

Parameters:a – the array to be checked.
Returns:True if a is sorted.
itu.algs4.sorting.shellsort.main()

Reads in a sequence of strings from standard input; Shellsorts them; and prints them to standard output in ascending order.

itu.algs4.sorting.shellsort.sort(a)

Rearranges the array in ascending order using the natural order.

Parameters:a – the array to be sorted.

Module contents