Sorting Basics
The simplest sorting algorithms like bubble sort, insertion sort, and selection sort have a time complexity of O(n^2). More advanced algorithms like merge sort, quick sort, and heap sort can achieve O(nlogn) time. The built-in sorted() and .sort() in Python use an optimized implementation of timsort which is a hybrid stable sorting algorithm derived from merge sort and insertion sort.
Some key functions and methods to know:
sorted(iterable)– returns a new sorted list from the items in iterablelist.sort()– sorts the items of the list in place
To sort in descending order, pass reverse=True to sorted() or .sort().
< & l t; lists > = [[5, 3, 8], [2, 4], [1, 7, 6]] sorted_lists = [sorted(sublist) for sublist in lists] print(sorted_lists) # [[3, 5, 8], [2, 4], [1, 6, 7]]
An important property of sorting algorithms is stability. Stable sorts maintain the relative order of equal elements. This can be important for keeping data in order that relies on previous order.
Time Complexity
When analyzing sorting algorithms, an important consideration is time complexity – how the running time scales as the number of items to sort increases. Some key notes on time complexity of sorting algorithms:
- Simple quadratic sorting algorithms like bubble sort, insertion sort and selection sort have O(n^2) time complexity. Doubling the number of items causes 4 times slower performance.
- More advanced algorithms like merge sort, quick sort and heap sort can achieve O(nlogn) time complexity. Doubling the input size causes only a 2 times slow down.
- The timsort algorithm used by Python’s built-in sorted() and sort() functions has worst case O(nlogn) time but faster average case performance.
So when sorting large inputs, the advanced O(nlogn) algorithms have a clear speed advantage over the simpler quadratic options. But for small inputs, the performance difference may be negligible, so simplicity and code size can outweigh raw speed.
Key Functions
Some key functions and methods to know for sorting in Python:
- sorted(iterable) – returns a new sorted list from the items in iterable
- list.sort() – sorts the items of the list in place
To sort in descending order, pass reverse=True to sorted() or .sort().
< lists > = [[5, 3, 8], [2, 4], [1, 7, 6]] sorted_lists = [sorted(sublist) for sublist in lists] print(sorted_lists) # [[3, 5, 8], [2, 4], [1, 6, 7]]
The sorted() function returns a new sorted list, leaving the original list unmodified. In contrast, list.sort() sorts the list in place, modifying the original list.
For custom sorting logic, the key parameter can be used to provide a function that transforms each element before comparing. For example, to sort by string length:
words = ["Apple", "Zebra", "banana"] sorted_words = sorted(words, key=len) print(sorted_words) # ['Apple', 'Zebra', 'banana']
Reverse Sorting
To sort items in reverse order, pass the reverse=True parameter to sorted() or .sort(). This will return or sort the elements from highest to lowest rather than the default lowest to highest order.
numbers = [5, 1, 4, 3, 2] reverse_sorted = sorted(numbers, reverse=True) print(reverse_sorted) # [5, 4, 3, 2, 1] numbers.sort(reverse=True) print(numbers) # [5, 4, 3, 2, 1]
Any sorting logic provided in the key parameter is still applied first before reversing the order. So reverse sorting can be combined with custom keys to get the desired behavior.
Some examples of using reverse sort for common cases:
- Sorting strings descending alphabetically
- Sorting by descending numerical value
- Reversing chronological order of dates or times
Reverse sorting provides flexibility to conveniently sort highest-to-lowest when the default lowest-to-highest order is not needed.
Stability
Stability is an important property for sorting algorithms. A stable sorting algorithm maintains the relative order of elements considered equal. If two elements A and B are equivalent under the sorting criterion, and A appears before B in the original list, a stable sort will keep A before B in the sorted output.
Stability is important for data that relies on original input order as part of its meaning. For example, order of student names often needs to be maintained even as groups are sorted by scores. Stable sorts preserve these relationships.
Some sorting algorithms like merge sort and insertion sort are stable by nature. Others like quicksort and heapsort are not stable. Python’s timsort used by sorted() and .sort() is designed to be stable.
Knowing sort stability can help choose the right algorithm. For example, here is code to sort a list of (score, name) tuples stably by score:
data = [(30, "Alex"), (10, "Bob"), (30, "Carol")] data.sort(key=lambda x: x[0]) print(data)
Because Python’s sort is stable, Alex and Carol remain in original order instead of being reversed.
Usage Examples
Sorting a list of numbers:
numbers = [5, 3, 8, 1, 2] sorted_numbers = sorted(numbers) print(sorted_numbers) # [1, 2, 3, 5, 8]
Sorting strings alphabetically:
names = ["Sarah", "Mark", "Sandra", "Eric"] sorted_names = sorted(names) print(sorted_names) # ['Eric', 'Mark', 'Sarah', 'Sandra']
Sorting by a key function – sorting by word length:
words = ["Apple", "Zebra", "Cat", "Lion"] sorted_words = sorted(words, key=len) print(sorted_words) # ['Cat', 'Apple', 'Lion', 'Zebra']
Stable sort maintaining order of same-score elements:
data = [(30, "Carol"), (10, "Mark"), (20, "Sarah"), (20, "John")] data.sort(key=lambda x: x[0]) print(data) # [(10, 'Mark'), (20, 'Sarah'), (20, 'John'), (30, 'Carol')]
Sorting a list in reverse numerical order:
values = [8, 3, 5, 1, 9] values.sort(reverse=True) print(values) # [9, 8, 5, 3, 1]
