Sorting Algorithms in Python
Introduction to Sorting Algorithms in Python
Sorting Algorithms in Python stands as a fundamental cornerstone of computer science, holding a crucial position in the realm of efficient data organization. With a focus on Python implementations, you’ll gain profound insights into their mechanics and applications, regardless of your skill level
What is Sorting Algorithms in Python?
Sorting algorithms are a set of well-defined procedures or techniques used to arrange elements in a specific order within a collection, usually in an ascending or descending order based on their values.
Stability of Sorting Algorithm in Python
The stability of a sorting algorithm in Python refers to its ability to preserve the relative order of equal elements in the sorted output as they were in the original unsorted input. In other words, if two elements have the same value, a stable sorting algorithm ensures that their order in the sorted array remains the same as their order in the initial array.
For example: In the given array there is one element ‘4’ present two times. For unstable algorithm, the position of the same element will be of two possibilities.
But for a stable algorithm, there is only one possibility for the position of elements in the given array.
Learn DSA
Prime Course Trailer
Types of Sorting Algorithms
Sorting algorithms in Python can differ in terms of their efficiency, stability, and the specific strategies they employ to rearrange elements. Some of the commonly used sorting algorithms include:
- Bubble Sort
- Insertion Sort
- Selection Sort
- Merge Sort
- Quick Sort
- Heap Sort
Bubble Sort in Python
Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the entire list is sorted.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
# Last i elements are already in place, no need to check them
for j in range(0, n - i - 1):
# Swap if the element found is greater than the next element
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
# Example usage
numbers = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(numbers)
print("Sorted array:", numbers)
Output :
Sorted array: [11, 12, 22, 25, 34, 64, 90]
Insertion Sort in Python
Insertion Sort builds the final sorted array one item at a time. It takes elements from the unsorted part of the array and inserts them into the correct position within the sorted part. It’s more efficient than Bubble Sort for small datasets or nearly sorted data.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# Example usage
numbers = [12, 11, 13, 5, 6]
insertion_sort(numbers)
print("Sorted array:", numbers)
Output :
Sorted array: [5, 6, 11, 12, 13]
Selection Sort in Python
Selection Sort repeatedly finds the minimum (or maximum) element from the unsorted part of the array and puts it at the beginning (or end) of the sorted part. It’s not very efficient for large datasets due to its quadratic time complexity.
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
# Example usage
numbers = [64, 25, 12, 22, 11]
selection_sort(numbers)
print("Sorted array:", numbers)
Output :
Sorted array: [11, 12, 22, 25, 64]
Merge Sort in Python
Merge Sort is a divide-and-conquer algorithm that divides the array into smaller sub-arrays, sorts them, and then merges them back together in a sorted manner.
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
# Example usage
numbers = [38, 27, 43, 3, 9, 82, 10]
merge_sort(numbers)
print("Sorted array:", numbers)
Output :
Sorted array: [3, 9, 10, 27, 38, 43, 82]
Quick Sort in Python
Quick Sort is another divide-and-conquer algorithm that selects a ‘pivot’ element and partitions the array into two sub-arrays such that elements less than the pivot are on its left and elements greater are on its right.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# Example usage
numbers = [6, 8, 3, 1, 9, 2, 5, 7]
sorted_numbers = quick_sort(numbers)
print("Sorted array:", sorted_numbers)
Output :
Sorted array: [1, 2, 3, 5, 6, 7, 8, 9]
Heap Sort in Python
Heap Sort uses a binary heap data structure to build a heap from the input array and then repeatedly extracts the maximum element from the heap and places it in the sorted part of the array.
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# Build a max heap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements from the heap one by one
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # Swap root and last element
heapify(arr, i, 0)
# Example usage
numbers = [12, 11, 13, 5, 6, 7]
heap_sort(numbers)
print("Sorted array:", numbers)
Output :
Sorted array: [5, 6, 7, 11, 12, 13]
Comparison of Sorting Algorithm
| Sorting Algorithm | Best Case Time Complexity | Average Case Time Complexity | Worst Case Time Complexity | Space Complexity | Stability |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n^2) | O(log n) | No |
| Heap Sort | O(log n) | O(log n) | O(log n) | O(1) | No |
How to Choose the Right Sorting Algorithm in Python
When sorting data in Python, the best and most practical option is to use the built-in sorted() function or .sort() method. These use Timsort, which is fast, stable, and handles real-world data efficiently.
However, if you’re implementing your own algorithm, the right choice depends on:
- Data size: Use simple sorts for small data, efficient ones for large.
- Stability needs: Choose a stable sort if equal items must retain their order.
- Memory limits: Use in-place algorithms when memory is tight.
- Performance needs: Pick based on whether average or worst-case matters.
To Wrap up with:
Sorting Algorithms in Python has unraveled the intricacies of various algorithms, from the elementary to the sophisticated, enabling efficient data organization. Whether it’s the simplicity of Bubble Sort or the efficiency of Merge Sort, each technique brings its unique value. The notion of stability has been explored, ensuring order preservation of equal elements.
FAQs
Sorting algorithms play a pivotal role in organizing and processing data efficiently. They’re crucial for tasks like retrieving information from databases, maintaining ordered lists, and optimizing search operations.
The choice of sorting algorithm depends on various factors, including the size of the dataset, the initial order of elements, and memory constraints. Merge Sort and Quick Sort are often favored for their efficiency, but the context matters.
Stability ensures that equal elements maintain their original order in the sorted output. This is vital in scenarios where the initial sequence of elements carries meaning or context.
For small datasets, simple sorting algorithms like Insertion Sort or Selection Sort can be efficient due to their lower overhead.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
30+ Companies are Hiring
Get Hiring Updates right in your inbox from PrepInsta
Login/Signup to comment