Sorting arrays is an elementary task in computer science, and Python provides several options to sort array elements. In this article, we’ll be covering the basics of sorting using the sorted() function, as well as the implementation of MergeSort and QuickSort algorithms.
Using sorted() on Python iterable objects:
Python provides a built-in function, sorted(), to sort any iterable object that follows Timsort (a sorting algorithm based on MergeSort, but with several optimizations). Timsort assumes that elements are mostly sorted, which is typical for real-world data sets.
sorted() takes an iterable object (list, tuple, string, etc.) and returns a new sorted list. Here’s an example:
“`python
# A sample Python list to be sorted using sorted()
numbers = [3, 1, 4, 2, 7, 6, 8, 5]
# Using sorted() function to sort the list
sorted_numbers = sorted(numbers)
print(‘Original list: ‘, numbers)
print(‘Sorted list: ‘, sorted_numbers)
“`
Output:
“`
Original list: [3, 1, 4, 2, 7, 6, 8, 5]
Sorted list: [1, 2, 3, 4, 5, 6, 7, 8]
“`
Notice that sorted() returns a new list containing the sorted elements.
It does not sort the original list in place. We can sort a list in reverse order by passing reverse=True to the sorted() function.
“`python
# Sorting the list in reverse order
reverse_sorted_numbers = sorted(numbers, reverse=True)
print(‘Original list: ‘, numbers)
print(‘Sorted in reverse order: ‘, reverse_sorted_numbers)
“`
Output:
“`
Original list: [3, 1, 4, 2, 7, 6, 8, 5]
Sorted in reverse order: [8, 7, 6, 5, 4, 3, 2, 1]
“`
Implementing MergeSort and QuickSort:
MergeSort and QuickSort are popular sorting algorithms that follow the Divide and Conquer approach. They split the original list into smaller sublists and sort them recursively, before merging them back to obtain the sorted list.
Both algorithms have O(n log n) time complexity (best-case, average-case, and worst-case). Let’s start with MergeSort.
MergeSort Algorithm:
MergeSort divides the original list into sublists of one or zero elements. These are already sorted, by definition.
Then, it merges adjacent sorted subarrays to produce new sorted subarrays until there is only one sublist remaining. This sublist is the sorted list.
Here’s how MergeSort works:
1. Divide the list into two halves or sublists, L and R.
2. Sort L and R recursively.
3. Merge sorted L and R to produce a new sorted list.
Code implementation:
Let’s start by looking at the helper function, mergesort_helper(). This function takes in the list to be sorted and recursively sorts it using MergeSort.
“`python
# Function to apply MergeSort recursively on a list
def mergesort_helper(arr):
# Base case: stop recursing when the list only has one element
if len(arr) <= 1:
return arr
# Divide the list into two halves
mid = len(arr) // 2
left_arr = arr[:mid]
right_arr = arr[mid:]
# Sort the left and right halves
left_arr = mergesort_helper(left_arr)
right_arr = mergesort_helper(right_arr)
# Merge the sorted halves and return the result
return perform_merge(left_arr, right_arr)
“`
Next, let’s look at the perform_merge() function. This function takes in two sorted subarrays and merges them into a new sorted array.
“`python
# Function to merge two sorted arrays
def perform_merge(left_arr, right_arr):
result = []
i, j = 0, 0
# Compare elements in both arrays and add the smaller element to the result array
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] < right_arr[j]:
result.append(left_arr[i])
i += 1
else:
result.append(right_arr[j])
j += 1
# Add any leftover elements to the result array
result += left_arr[i:]
result += right_arr[j:]
return result
“`
Finally, we just need to call the mergesort_helper() function with our list to be sorted. “`python
# Sample list to be sorted using MergeSort
arr = [38, 27, 43, 3, 9, 82, 10]
# Sort the list using MergeSort
sorted_arr = mergesort_helper(arr)
print(‘Original list: ‘, arr)
print(‘Sorted list: ‘, sorted_arr)
“`
Output:
“`
Original list: [38, 27, 43, 3, 9, 82, 10]
Sorted list: [3, 9, 10, 27, 38, 43, 82]
“`
QuickSort Algorithm:
QuickSort works by choosing a pivot element (usually the last element), and partitioning the remaining elements into two subarrays one with elements smaller than the pivot, and the other with elements greater than the pivot.
It then recursively sorts the two subarrays, following the Divide and Conquer approach. Here’s how QuickSort works:
1.
Choose a pivot element (the last element in our implementation). 2.
Partition the list into two subarrays: elements smaller than the pivot, and elements greater than the pivot. 3.
Recursively sort the two subarrays. Code implementation:
Let’s first look at the partition() function.
This function takes in the list and pivot element as inputs and partitions the list into two subarrays. “`python
# Function to partition the list and return the pivot index
def partition(arr, low, high):
pivot = arr[high]
i = low – 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
“`
Next, let’s look at the quicksort_helper() function, which takes in the list to be sorted and applies QuickSort recursively.
“`python
# Function to apply QuickSort recursively
def quicksort_helper(arr, low, high):
if low < high:
# Partition the list
pivot_index = partition(arr, low, high)
# Recurse on the two subarrays
quicksort_helper(arr, low, pivot_index – 1)
quicksort_helper(arr, pivot_index + 1, high)
“`
Finally, we just need to call quicksort_helper() with the list we want to sort. “`python
# Sample list to be sorted using QuickSort
arr = [4, 2, 3, 6, 1, 7, 8, 5]
# Sort the list using QuickSort
quicksort_helper(arr, 0, len(arr) – 1)
print(‘Original list: ‘, arr)
“`
Output:
“`
Original list: [1, 2, 3, 4, 5, 6, 7, 8]
“`
In conclusion, Python provides a sorted() function for basic sorting needs, while MergeSort and QuickSort provide more powerful, but slightly more complex, sorting capabilities.
Knowing the strengths and limitations of each algorithm is essential for building efficient and optimized solutions. QuickSort Algorithm:
QuickSort is another popular sorting algorithm that works by dividing the input list into smaller sublists, sorting them recursively, and then merging them to obtain the final sorted list.
QuickSort follows the Divide and Conquer approach and is usually faster than MergeSort on average, but slower in the worst-case scenario. QuickSort has an average-case time complexity of O(n log n), but its worst-case time complexity is O(n^2).
Performance and working of the algorithm:
QuickSort works by choosing a pivot element from the input list and partitioning the remaining elements into two sublists one with elements smaller than the pivot and the other with elements greater than the pivot. The pivot element is placed at its final position in the sorted list.
The process is repeated recursively for the two sublists until the entire list is sorted. Here’s how QuickSort works:
1.
Choose a pivot element (randomly or as the last element in our implementation). 2.
Partition the list into two sublists: one of elements smaller than the pivot, and one of elements greater than the pivot. 3.
Place the pivot element in its final position in the sorted list. 4.
Recursively sort the two subarrays. Code implementation:
To implement the QuickSort algorithm, we need to define a helper function that takes in the list, starting point, and endpoint, and sorts it recursively.
We’ll call this function quicksort_helper(). “`python
# Function to apply QuickSort recursively
def quicksort_helper(arr, low, high):
if low < high:
# Partition the list
pivot_index = do_partition(arr, low, high)
# Recurse on the two subarrays
quicksort_helper(arr, low, pivot_index – 1)
quicksort_helper(arr, pivot_index + 1, high)
“`
The pivot element can be selected randomly, but for simplicity, we’ll select the last element of the list to be the pivot.
Next, let’s define the function for partitioning the list into two sublists. We’ll call this function do_partition().
This function takes the list, starting point, and endpoint as parameters and returns the pivot index. “`python
# Function to partition the list and return the pivot index
def do_partition(arr, low, high):
pivot = arr[high]
i = low – 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
“`
The do_partition() function stores the pivot value, sets the left pointer to one element before the start index (i.e, low-1), and loops through the array from the low index to high-1.
We compare each element of the array with the pivot element and swap them if an element is smaller than the pivot element. This results in all elements smaller than the pivot going to the left of the pivot.
We then place the pivot element in its final sorted position by swapping it with the (i+1)th element. The (i+1)th index represents the point up to which all elements to the left of the array are smaller than the pivot.
Now that we understand how each of the functions works, let’s call quicksort_helper() with our input list. “`python
# Sample list to be sorted using QuickSort
arr = [54, 26, 93, 17, 77, 31, 44, 55, 20]
# Call the quicksort_helper() function
quicksort_helper(arr, 0, len(arr) – 1)
print(‘Original list:’, arr)
“`
The output should be:
“`
Original list: [17, 20, 26, 31, 44, 54, 55, 77, 93]
“`
You can see that the input list has been sorted in ascending order.
QuickSort is an efficient algorithm that uses less memory than MergeSort, and is widely used in practice for its average-case performance efficiency. Conclusion:
Sorting algorithms are fundamental in computer science and are used in a wide range of applications.
Python provides simple, built-in functions like sorted() that are easy to use; however, when performance is critical, more advanced algorithms like MergeSort and QuickSort are better suited. MergeSort and QuickSort use the Divide and Conquer approach to sort lists by dividing the list into smaller, more manageable sublists.
QuickSort is a faster algorithm than MergeSort on average but has a higher worst-case complexity. Python provides flexibility in implementing sorting algorithms and understanding the capabilities and limitations of different algorithms can help programmers write efficient and optimized code.
In conclusion, sorting algorithms are an essential part of computer science and are used in various applications. Python has built-in functions like sorted() for basic sorting requirements, but when performance is a concern, MergeSort and QuickSort are better options.
Both algorithms follow the Divide and Conquer approach and are efficient in sorting large data sets. MergeSort is a stable sorting algorithm with better worst-case performance, while QuickSort is faster on average.
However, QuickSort has a higher worst-case complexity. Understanding the strengths and limitations of each algorithm can help programmers write optimized and efficient code.
It is crucial to choose the appropriate sorting algorithm for the given requirements to achieve the desired performance.