[Sorting] Fast Sorting Algorithms & Sorting in Python

A fast sorting algorithm is a sorting algorithm that has an average runtime complexity of O(n ⁢l⁢o⁢g⁢ n) or better.

The table below shows average runtime complexities for several sorting algorithms.

 

 

---

Comparison sorting

An element comparison sorting algorithm is a sorting algorithm that operates on an array of elements that can be compared to each other.

Ex: An array of strings can be sorted with a comparison sorting algorithm, since two strings can be compared to determine if the one string is less than, equal to, or greater than another string.

 

Selection sort, insertion sort, shell sort, quicksort, merge sort, and heap sort are all comparison sorting algorithms.

Radix sort, in contrast, subdivides each array element into integer digits and is not a comparison sorting algorithm.

 

 

 

The fastest average runtime complexity of a comparison sorting algorithm is O(n log n).

 

These are the best, average, and worst case runtime complexity of the 4 fast sorging algorithms.

 

 

---

Sorting in Python

 

Python offers a built in sorted() function that takes one list argument, sorts the list's argument in ascending order using the less than (<) operator, and returns a new list with sorted elements. 

 

Python list objects also have a .sort() method to do an in-place sorting of list elements in ascending order, meaning the list is modified and another list is NOT returned.

 

# Using sorted() function
num_list = [3, 7, 2, 8, 12, 4, 9, 5]
sorted_num_list = sorted(num_list)
print('UNSORTED:', num_list)		# UNSORTED: [3, 7, 2, 8, 12, 4, 9, 5]
print('SORTED:', sorted_num_list)	# SORTED: [2, 3, 4, 5, 7, 8, 9, 12]
print()

# Using sort() method
fruit_list = ["grape", "banana", "apple", "strawberry", "blueberry"]
print('UNSORTED:', fruit_list)		# UNSORTED: ["grape", "banana", "apple", "strawberry", "blueberry"]
fruit_list.sort()
print('SORTED:', fruit_list)		# SORTED: ['apple', 'banana', 'blueberry', 'grape', 'strawberry']

 

Sorting in Descending Order

You can add an optional argument reverse=True to both of the functions to perform a sorting in descending order. 

ex) sorted_num_list_desc = sorted(num_list, reverse = True)

 

 

Key Argument

Also, in those functions, we can use an optional key argument.

For example, say that we want to sort a list of fruits, where the elements can be in lowercase or uppercase. 

But, we want our sorted list to be case insensitive, meaning that the uppercase fruits shouldn't be sorted to be at the indexes before all of the lowercase letters. (i.e. sort as if all letters were lowercase)

 

In that case, we can use key = str.lower argument without parenthesis to both of the functions. 

fruit_list = ["grape", "Banana", "apple", "Strawberry", "blueberry"]
case_sensitive = sorted(fruit_list)
case_insensitive = sorted(fruit_list, key=str.lower)

print("Case Sensitive:", case_sensitive)
print("Case Insensitive:", case_insensitive)


# Case Sensitive: ['Banana', 'Strawberry', 'apple', 'blueberry', 'grape']
# Case Insensitive: ['apple', 'Banana', 'blueberry', 'grape', 'Strawberry']

 

 

We can also use custom key functions!

Say that we have a situation where each element forms a tuple. 

Then which element in each tuple should we be sorting based on?

 

We can define a function and use it as the key function argument in the sorting function/method to state which element we'll be sorting for. 

Looking at the code would be easier to understand:

def key_is_name(element):
    return element[0]


def key_is_id(element):
    return element[1]


class_list = [
    ("Robert", 135216),
    ("Amir", 612901),
    ("Jennifer", 194821),
    ("Ravi", 631104),
]

name_result = sorted(class_list, key=key_is_name)
id_result = sorted(class_list, key=key_is_id)

print("Sort by name:", name_result)
print("Sort by id:", id_result)

# Sort by name: [('Amir', 612901), ('Jennifer', 194821), ('Ravi', 631104), ('Robert', 135216)]
# Sort by id: [('Robert', 135216), ('Jennifer', 194821), ('Amir', 612901), ('Ravi', 631104)]

 

Custom key functions must be defined with only one parameter, a single list element.

 

Another example for custom key functions that can do exactly same thing with key = str.lower in more tedious way is:

def custom_key(word):
    return word.lower()

myList = ["grape", "Banana", "apple", "Strawberry", "blueberry"]

print("Sort 1:", sorted(myList, key=str.lower))
print("Sort 2:", sorted(myList, key=custom_key))

# Sort 1: ['apple', 'Banana', 'blueberry', 'grape', 'Strawberry']
# Sort 2: ['apple', 'Banana', 'blueberry', 'grape', 'Strawberry']

 

 

Now, the previous example's key_is_name() and key_is_id() functions can be replace with a special function itemgetter() defined in Python's operator module. 

import operator
class_list = [("Robert", 135216), ("Amir", 612901), ("Jennifer", 194821), ("Ravi", 631104)]
name_result = sorted(class_list, key = operator.itemgetter(0))
id_result = sorted(class_list, key = operator.itemgetter(1))
print('Sort by name:', name_result)
print('Sort by id:', id_result)