Sorting Algorithms
Sorting algorithms arrange data in a particular order, typically ascending or descending. Common sorting algorithms include:
Bubble Sort
Bubble sort is a simple comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
def bubble_sort(arr):
n = len(arr)
# Traverse through all elements in the list
for i in range(n):
# Last i elements are already sorted
for j in range(0, n-i-1):
# Traverse the list from 0 to 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
example_array = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(example_array)
print("Sorted array is:", example_array)
Code Explanation
1. Function Definition: We define a function bubble_sort that takes a list arr as its parameter.
2. Length Calculation: We calculate the length of the list n.
3. Outer Loop: We run a loop from 0 to n-1. This loop ensures that we make n passes over the list.
4. Inner Loop: Inside the outer loop, we run another loop from 0 to n-i-1. This loop handles the comparison and swapping of adjacent elements.
5. Comparison and Swap: If the current element arr[j] is greater than the next element arr[j+1], we swap them.
6. Example Usage: We create an example list, sort it using bubble_sort, and print the sorted list.
Selection Sort
Selection sort divides the input list into two parts: the sorted part and the unsorted part. It repeatedly selects the smallest (or largest) element from the unsorted part and moves it to the sorted part.
def selection_sort(arr):
n = len(arr)
# Traverse through all array elements
for i in range(n):
# Find the minimum element in remaining unsorted array
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# Swap the found minimum element with the first element
arr[i], arr[min_idx] = arr[min_idx], arr[i]
# Example usage
example_array = [64, 25, 12, 22, 11]
selection_sort(example_array)
print("Sorted array is:", example_array)
Code Explanation
1. Function Definition: We define a function selection_sort that takes a list arr as its parameter.
2. Length Calculation: We calculate the length of the list n.
3. Outer Loop: We run a loop from 0 to n-1. This loop represents the boundary between the sorted and unsorted parts of the list.
4. Inner Loop: Inside the outer loop, we find the minimum element in the unsorted part of the list.
5. Find Minimum: We initialize the minimum index min_idx to the current index i. Then, we traverse the unsorted part of the list to find the minimum element.
6. Swap: We swap the found minimum element with the first element of the unsorted part of the list.
7. Example Usage: We create an example list, sort it using selection_sort, and print the sorted list.
Insertion Sort
Insertion sort builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
def insertion_sort(arr):
# Traverse through 1 to len(arr)
for i in range(1, len(arr)):
key = arr[i]
# Move elements of arr[0..i-1], that are greater than key,
# to one position ahead of their current position
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# Example usage
example_array = [12, 11, 13, 5, 6]
insertion_sort(example_array)
print("Sorted array is:", example_array)
Code Explanation
1. Function Definition: We define a function insertion_sort that takes a list arr as its parameter.
2. Outer Loop: We run a loop from 1 to len(arr)-1. This loop represents the current element to be inserted into the sorted part of the list.
3. Key Element: We store the current element in a variable called key.
4. Inner Loop: Inside the outer loop, we run a while loop to move elements of arr[0..i-1] that are greater than the key to one position ahead of their current position.
5. Shift Elements: We shift elements to the right until we find the correct position for the key.
6. Insert Key: We insert the key at its correct position in the sorted part of the list.
7. Example Usage: We create an example list, sort it using insertion_sort, and print the sorted list.
Merge Sort
Merge sort is an efficient, stable, comparison-based, divide-and-conquer sorting algorithm. Most implementations produce a stable sort, meaning that the order of equal elements is the same in the input and output.
def merge_sort(arr):
if len(arr) > 1:
# Finding the middle of the array
mid = len(arr) // 2
# Dividing the array elements into 2 halves
left_half = arr[:mid]
right_half = arr[mid:]
# Sorting the first half
merge_sort(left_half)
# Sorting the second half
merge_sort(right_half)
i = j = k = 0
# Copy data to temp arrays L[] and R[]
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
# Checking if any element was left
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
example_array = [12, 11, 13, 5, 6, 7]
merge_sort(example_array)
print("Sorted array is:", example_array)
Code Explanation
1. Function Definition: We define a function merge_sort that takes a list arr as its parameter.
2. Base Case: If the length of the list is greater than 1, we proceed with the sorting. If not, the list is already sorted.
3. Divide: We find the middle of the list and divide it into two halves: left_half and right_half.
4. Recursive Sorting: We recursively call merge_sort on both halves to sort them.
5. Merge: We merge the two halves back together:
6. Comparing Elements: We compare elements from the two halves and copy the smaller element into the original list arr.
7. Remaining Elements: We check if there are any remaining elements in either half and copy them into the original list arr.
8. Example Usage: We create an example list, sort it using merge_sort, and print the sorted list.
Quick Sort
Quick sort is an efficient sorting algorithm, serving as a systematic method for placing the elements of a random access file or an array in order. It is still a commonly used algorithm for sorting.
def partition(arr, low, high):
i = (low-1) # index of smaller element
pivot = arr[high] # pivot
for j in range(low, high):
# If current element is smaller than or
# equal to pivot
if arr[j] <= pivot:
i = i+1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return (i+1)
# The main function that implements QuickSort
def quick_sort(arr, low, high):
if low < high:
# pi is partitioning index, arr[p] is now
# at right place
pi = partition(arr, low, high)
# Separately sort elements before
# partition and after partition
quick_sort(arr, low, pi-1)
quick_sort(arr, pi+1, high)
# Example usage
example_array = [10, 7, 8, 9, 1, 5]
n = len(example_array)
quick_sort(example_array, 0, n-1)
print("Sorted array is:", example_array)
Code Explanation
1. Partition Function: We define a function partition that takes the list arr, the starting index low, and the ending index high as its parameters.
2. Pivot Element: We choose the last element as the pivot.
3. Partitioning: We rearrange the elements so that all elements smaller than the pivot are on the left side and all elements greater than the pivot are on the right side.
4. Recursive Sorting: We recursively apply the quick sort on the left and right partitions.
5. Quick Sort Function: We define the main function quick_sort that takes the list arr, the starting index low, and the ending index high as its parameters.
6. Base Case: If low is less than high, we proceed with the sorting. If not, the list is already sorted.
7. Example Usage: We create an example list, sort it using quick_sort, and print the sorted list.
Leave a Reply