Sorting numbers in ascending order is one of the most basic operations in programming, often achieved using built-in functions like Python’s sort() or sorted(). However, solving this problem without using these helper functions can significantly improve your understanding of algorithms and how sorting actually works under the hood.
In this blog, we will explore how to implement an ascending order sorting algorithm in Python without using the sort() function. We’ll discuss various methods, including popular sorting algorithms like bubble sort, selection sort, and insertion sort. We’ll also delve into the time complexities and strengths of these algorithms, followed by a step-by-step explanation of how to implement them in Python.
Why Avoid the Sort Function?
While Python’s built-in sorting function is powerful and optimized, it’s important to understand the mechanics behind sorting algorithms for several reasons:
- Learning Purpose: Understanding how sorting algorithms work is fundamental to improving your algorithmic thinking and problem-solving skills.
- Customization: You might want to sort data based on specific criteria that the built-in sort can’t handle directly.
- Algorithm Optimization: In some cases, you might want to use a different algorithm based on time complexity and space requirements.
Now, let’s get into various methods to achieve sorting in ascending order without using Python’s built-in sort() function.
1. Bubble Sort Algorithm
Bubble sort is one of the simplest sorting algorithms. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This pass through the list is repeated until the list is sorted.
How Bubble Sort Works:
- In each pass, adjacent elements are compared.
- If the current element is greater than the next one, they are swapped.
- The largest element “bubbles up” to its correct position at the end of the list after each pass.
Time Complexity:
- Best case (already sorted): O(n)
- Worst case: O(n²)
Implementation in Python:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
# Flag to check if the list is already sorted
swapped = False
# Traverse the array from 0 to n-i-1
# Last i elements are already sorted
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]
swapped = True
# If no two elements were swapped in the inner loop, break
if not swapped:
break
return arrExample
array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = bubble_sort(array)
print(f"Sorted array: {sorted_array}")Output:
Sorted array: [11, 12, 22, 25, 34, 64, 90]In this algorithm, we iterate through the list, compare pairs, and swap them if necessary. After each pass, the largest unsorted element moves to the end of the list. The algorithm stops early if no swaps are made during a pass, indicating that the list is already sorted.
2. Selection Sort Algorithm
Selection sort works by selecting the smallest (or largest, depending on sorting order) element from the unsorted portion of the list and swapping it with the first unsorted element. The process is repeated until the entire list is sorted.
How Selection Sort Works:
- Traverse the list and find the minimum element.
- Swap it with the first element.
- Move to the next element and repeat the process for the remaining unsorted portion.
Time Complexity:
- Best case: O(n²)
- Worst case: O(n²)
Implementation in Python:
def selection_sort(arr):
n = len(arr)
for i in range(n):
# Assume the first element is the minimum
min_idx = i
# Traverse the rest of the array to find the minimum element
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# Swap the found minimum element with the first unsorted element
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
Example
array = [29, 10, 14, 37, 14]
sorted_array = selection_sort(array)
print(f"Sorted array: {sorted_array}")Output:
Sorted array: [10, 14, 14, 29, 37]Selection sort is easy to understand and implement but isn’t very efficient for large lists due to its O(n²) time complexity. It performs well on small datasets but is rarely used in production.
3. Insertion Sort Algorithm
Insertion sort builds the sorted list one element at a time. It picks each element and inserts it into its correct position relative to the already sorted portion of the list.
How Insertion Sort Works:
- Start from the second element, assuming the first element is sorted.
- Compare the current element with the elements in the sorted portion.
- Shift all the larger elements in the sorted portion one position to the right.
- Insert the current element in its correct position.
Time Complexity:
- Best case (already sorted): O(n)
- Worst case: O(n²)
Implementation in Python:
def insertion_sort(arr):
# Traverse from the second element (index 1) to the end
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
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
# Place key at its correct position
arr[j + 1] = key
return arrExample
array = [12, 11, 13, 5, 6]
sorted_array = insertion_sort(array)
print(f"Sorted array: {sorted_array}")Output:
Sorted array: [5, 6, 11, 12, 13]Insertion sort is more efficient than bubble sort and selection sort for small datasets or nearly sorted data. It works well when the list is almost sorted, as it minimizes the number of shifts.
4. Merge Sort Algorithm
Merge sort is a divide-and-conquer algorithm that recursively divides the list into two halves until each half has one element, and then merges the halves back together in sorted order.
How Merge Sort Works:
- Recursively split the list into halves.
- Sort each half.
- Merge the two sorted halves.
Time Complexity:
- Best and worst case: O(n log n)
Implementation in Python:
def merge_sort(arr):
if len(arr) > 1:
# Find the middle of the array
mid = len(arr) // 2
# Split the array into two halves
left_half = arr[:mid]
right_half = arr[mid:]
# Recursively sort both halves
merge_sort(left_half)
merge_sort(right_half)
# Merge the sorted halves
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
# Copy the remaining elements of left_half
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
# Copy the remaining elements of right_half
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
return arr
Example
array = [38, 27, 43, 3, 9, 82, 10]
sorted_array = merge_sort(array)
print(f"Sorted array: {sorted_array}")Output:
Sorted array: [3, 9, 10, 27, 38, 43, 82]Merge sort has a better time complexity than bubble, selection, and insertion sorts. It is often used in situations where stability (preserving the order of equal elements) is important, but it requires additional memory space for merging, which makes it less space-efficient than other algorithms like quicksort.
5. Quick Sort Algorithm
Quick sort is another divide-and-conquer algorithm. It works by selecting a “pivot” element from the list and partitioning the other elements into two sublists—those less than the pivot and those greater than the pivot. The sublists are then recursively sorted.
How Quick Sort Works:
- Pick a pivot element.
- Partition the list into two sublists: elements less than the pivot and elements greater than the pivot.
- Recursively apply the same process to the sublists.
Time Complexity:
- Best case: O(n log n)
- Worst case (poor pivot selection): O(n²)
Implementation in Python:
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
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
array = [3, 6, 8, 10, 1, 2, 1]
sorted_array = quick_sort(array)
print(f"Sorted array: {sorted_array}")Output:
Sorted array: [1, 1, 2, 3, 6, 8, 10]Quick sort is one of the most efficient sorting algorithms in practice, with average time complexity of O(n log n). However, it can degrade to O(n²) in the worst case when the pivot selection is poor.
Conclusion
Sorting a list in ascending order without using Python’s built-in sort() function helps you understand the different sorting algorithms and their nuances. Each algorithm has its strengths and weaknesses, which are primarily determined by the dataset size and characteristics. For small datasets, bubble, insertion, or selection sorts might suffice, while for larger datasets, merge sort and quicksort are better suited.
Understanding these algorithms allows you to make informed choices when working with different types of data and teaches you how to write efficient code. By implementing these algorithms in Python, you also gain a deeper appreciation for the built-in sort() function and its underlying efficiency.
3.0 per unit
7.5 per unit
2.5/unit
3.0/unit
5.0/unit
375
{total_bill:.2f}"
![\[C = 2 \pi r\]](https://thescience360.com/wp-content/ql-cache/quicklatex.com-17f315be06c785a70751dab743e961a8_l3.png "Rendered by QuickLaTeX.com")