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.
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.
Example :
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.
Example :
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.
Example :
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.
Example :
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.
Example :
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.
Example :
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 |
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.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Question 1.
Why are sorting algorithms important in programming?
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.
Question 2.
What is the best sorting algorithm to use?
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.
Question 3.
What is the significance of stability in sorting algorithms?
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.
Question 4.
Which sorting algorithm is best for small datasets?
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
Login/Signup to comment