Python build in Sorting Algorithms

Python provides two primary methods for sorting: the built-in sorted() function and the sort() method of list objects. Both are essential tools for organizing data and are designed to be efficient, flexible, and easy to use.

sorted() Function

The sorted() function is a built-in function that returns a new sorted list from the elements of any iterable. It does not modify the original iterable.

Syntax

sorted(iterable, key=None, reverse=False)

• iterable: The collection of items to be sorted (e.g., list, tuple, string, dictionary, set).
• key: (Optional) A function that serves as a key for the sort comparison. It is applied to each element before making comparisons.
• reverse: (Optional) A boolean value. If True, the sorted list is reversed (or sorted in descending order).

Example Usage

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5]
sorted_numbers = sorted(numbers)
print("Sorted numbers:", sorted_numbers)  # Output: [1, 1, 2, 3, 4, 5, 5, 6, 9]

# Sorting in reverse order
sorted_numbers_desc = sorted(numbers, reverse=True)
print("Sorted numbers (desc):", sorted_numbers_desc)  # Output: [9, 6, 5, 5, 4, 3, 2, 1, 1]

# Sorting with a key function
words = ["banana", "apple", "cherry"]
sorted_words = sorted(words, key=len)
print("Sorted words by length:", sorted_words)  # Output: ['apple', 'banana', 'cherry']

list.sort() Function

The sort() function is a function of list objects that sorts the list in place, meaning it modifies the original list and does not return a new list.

Syntax

list.sort(key=None, reverse=False)

• key: (Optional) A function that serves as a key for the sort comparison. It is applied to each element before making comparisons.
• reverse: (Optional) A boolean value. If True, the list is sorted in reverse order.

Example Usage

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5]
numbers.sort()
print("Sorted numbers:", numbers)  # Output: [1, 1, 2, 3, 4, 5, 5, 6, 9]

# Sorting in reverse order
numbers.sort(reverse=True)
print("Sorted numbers (desc):", numbers)  # Output: [9, 6, 5, 5, 4, 3, 2, 1, 1]

# Sorting with a key function
words = ["banana", "apple", "cherry"]
words.sort(key=len)
print("Sorted words by length:", words)  # Output: ['apple', 'banana', 'cherry']

Differences Between sorted() and list.sort()

1. Return Type:
   • sorted(): Returns a new sorted list from the elements of any iterable.
   • list.sort(): Modifies the list in place and returns None.
2. Original Data:
   • sorted(): Does not modify the original iterable.
   • list.sort(): Modifies the original list.
3. Usability:
   • sorted(): Can be used on any iterable, including tuples, strings, dictionaries, and sets.
   • list.sort(): Can only be used on lists.

Key Parameter

Both sorted() and list.sort() accept a key parameter, which allows custom sorting logic. The key parameter should be a function that takes an element from the iterable and returns a value to be used for sorting purposes.

Example: Sorting by Absolute Value

numbers = [-4, -1, 2, 3, -5]
sorted_numbers = sorted(numbers, key=abs)
print("Sorted by absolute value:", sorted_numbers)  # Output: [-1, 2, 3, -4, -5]

numbers.sort(key=abs)
print("Sorted by absolute value (in place):", numbers)  # Output: [-1, 2, 3, -4, -5]

Reverse Parameter

The reverse parameter, when set to True, sorts the data in descending order.

Example: Sorting in Descending Order

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5]
sorted_numbers_desc = sorted(numbers, reverse=True)
print("Sorted numbers (desc):", sorted_numbers_desc)  # Output: [9, 6, 5, 5, 4, 3, 2, 1, 1]

numbers.sort(reverse=True)
print("Sorted numbers (desc, in place):", numbers)  # Output: [9, 6, 5, 5, 4, 3, 2, 1, 1]

Stability

Both sorted() and list.sort() are stable sorts, meaning they maintain the relative order of records with equal keys.

Example: Stability

pairs = [(1, 'one'), (2, 'two'), (1, 'uno'), (2, 'dos')]
sorted_pairs = sorted(pairs, key=lambda x: x[0])
print("Sorted pairs:", sorted_pairs)
# Output: [(1, 'one'), (1, 'uno'), (2, 'two'), (2, 'dos')]

Summary

• sorted() is a versatile function that can sort any iterable and returns a new sorted list, leaving the original iterable unchanged.
• list.sort() is a method specific to lists that sorts the list in place, modifying the original list.
• Both functions accept key and reverse parameters for custom sorting logic and descending order sorting.
• Both sorting methods are stable, preserving the relative order of equal elements.