Wondering How to sort a list in ascending order in Python without sort()?
Python offers various methods and functions for sorting elements in ascending order.
However, what if you need to arrange a list in ascending order without using the built-in sort function?
In this blog post, we will explore several approaches to achieve this task using different algorithms and techniques.
By understanding these methods, you can gain valuable insights into the underlying principles of sorting algorithms and enhance your Python programming skills.
Method 1
Bubble Sort
Bubble Sort compares adjacent elements in the list and swaps them if they are in the wrong order.
This process repeats until the entire list is sorted.
The algorithm iterates through the list multiple times, with each pass placing the largest element in its correct position at the end of the list.
How to sort a list in ascending order in Python without sort()?
def bubble_sort(arr):
n = len(arr)
# Traverse through all array elements
for i in range(n):
# Last i elements are already in place
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
arr = [5, 2, 1, 6, 9, 7]
print("Original List;", arr)
bubble_sort(arr)
print("Sorted List:", arr)Click on this code and it will be copied automatically.
Then you can run it on our free Online Python Compiler.
Output
Original List; [5, 2, 1, 6, 9, 7]
Sorted List: [1, 2, 5, 6, 7, 9]
Advantages: Sorting a list ascending order in Python without sort
- Bubble Sort is easy to understand and implement, making it a good choice for educational purposes or small projects.
- It has a simple logic flow and requires minimal code.
Disadvantages: Sorting a list ascending order in Python without sort
- The time complexity of Bubble Sort is O(n^2), making it inefficient for large lists.
- It performs unnecessary swaps even when the list is already sorted, resulting in a higher number of operations.
Method 2
Insertion Sort
Insertion Sort builds the final sorted array one element at a time by repeatedly inserting an element into its correct position in the sorted portion of the list.
It starts with the assumption that the first element is already sorted and then compares each subsequent element with the elements in the sorted portion, shifting them if necessary.
How to sort a list in ascending order in Python without sort()?
def insertion_sort(arr):
n = len(arr)
# Traverse through 1 to n-1 elements
for i in range(1, n):
key = arr[i]
j = i - 1
# Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# Example usage
arr = [5, 2, 1, 6, 9, 7]
print("Original List;", arr)
insertion_sort(arr)
print("Sorted List:", arr)Click on this code and it will be copied automatically.
Then you can run it on our free Online Python Compiler.
Output
Original List; [5, 2, 1, 6, 9, 7]
Sorted List: [1, 2, 5, 6, 7, 9]
Advantages: Sorting a list ascending order in Python without sort
- Insertion Sort performs well on small lists and is efficient for partially sorted or nearly sorted data.
- It has an adaptive property, meaning it performs better when the list is partially sorted.
Disadvantages: Sorting a list ascending order in Python without sort
- The time complexity of Insertion Sort is O(n^2), making it inefficient for large lists.
- It requires shifting elements to accommodate the correct position of each element, which can be computationally expensive.
Method 3
Selection Sort
Selection Sort divides the list into two portions: the sorted portion and the unsorted portion.
It repeatedly selects the smallest (or largest) element from the unsorted portion and swaps it with the first element of the unsorted portion, expanding the sorted portion by one element in each iteration.
How to sort a list in ascending order in Python without sort()?
def selection_sort(arr):
n = len(arr)
# Traverse through all array elements
for i in range(n):
# Find the minimum element in the remaining unsorted part of the array
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
# Swap the found minimum element with the first element
arr[i], arr[min_index] = arr[min_index], arr[i]
# Example usage
arr = [5, 2, 1, 6, 9, 7]
print("Original List;", arr)
selection_sort(arr)
print("Sorted List:", arr)Run this code on our free Online Python Compiler.
Output
Original List; [5, 2, 1, 6, 9, 7]
Sorted List: [1, 2, 5, 6, 7, 9]
Advantages: Sorting a list ascending order in Python without sort
- Selection Sort has a simple implementation and requires minimal additional memory.
- It performs well for small lists or lists with a small number of elements to sort.
Disadvantages: Sorting a list ascending order in Python without sort
- The time complexity of the Selection Sort is O(n^2), making it inefficient for large lists.
- It performs unnecessary swaps even when the list is partially sorted, resulting in a higher number of operations.
Method 4
Counting Sort
Counting Sort is a linear time complexity sorting algorithm suitable for lists of non-negative integers with a known range.
It counts the occurrences of each element and places them in order.
How to sort a list in ascending order in Python without sort()?
def counting_sort(arr):
# Find the maximum element in the array to determine the range
max_val = max(arr)
# Create a count list to store the count of each element
count = [0] * (max_val + 1)
# Count the occurrences of each element in the input array
for num in arr:
count[num] += 1
# Calculate the cumulative count
for i in range(1, len(count)):
count[i] += count[i - 1]
# Create a sorted result list
sorted_arr = [0] * len(arr)
# Place each element in its correct position in the sorted list
for num in arr:
sorted_arr[count[num] - 1] = num
count[num] -= 1
return sorted_arr
# Example usage
arr = [5, 2, 1, 6, 9, 7]
print("Original List;", arr)
sorted_arr = counting_sort(arr)
print("Sorted List:", sorted_arr)Run this code on our free Online Python Compiler.
Output
Original List; [5, 2, 1, 6, 9, 7]
Sorted List: [1, 2, 5, 6, 7, 9]
Advantages: Sorting a list ascending order in Python without sort
- Counting Sort has a time complexity of O(n + k), where n is the number of elements and k is the range of values. This makes it highly efficient for lists with a small range of values.
- It is stable, meaning elements with equal values maintain their relative order after sorting.
Disadvantages: Sorting a list ascending order in Python without sort
- Counting Sort requires additional space proportional to the range of values, which can be a limiting factor for large value ranges.
- It is not suitable for sorting lists with negative numbers or non-integer values.
Method 5
Merge Sort
Merge Sort is a divide-and-conquer algorithm that divides the list into smaller sublists, recursively sorts them, and then merges them to obtain the final sorted list.
How to sort a list in ascending order in Python without sort()?
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
return merge(left_half, right_half)
def merge(left, right):
merged = []
left_index = 0
right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] < right[right_index]:
merged.append(left[left_index])
left_index += 1
else:
merged.append(right[right_index])
right_index += 1
# Append the remaining elements from the left or right sublist
merged.extend(left[left_index:])
merged.extend(right[right_index:])
return merged
# Example usage
arr = [5, 3, 8, 4, 2, 1, 6, 9, 7]
print("Original List;", arr)
sorted_arr = merge_sort(arr)
print("Sorted List:", sorted_arr)
Run this code on our free Online Python Compiler.
Output
Original List; [5, 3, 8, 4, 2, 1, 6, 9, 7]
Sorted List: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Advantages: Sorting a list ascending order in Python without sort
- Merge Sort has a time complexity of O(n log n) in all cases, making it efficient for large lists.
- It is a stable sorting algorithm, preserving the relative order of elements with equal values.
- Merge Sort’s divide-and-conquer approach allows it to handle large data sets and performs consistently well.
Disadvantages: Sorting a list ascending order in Python without sort
- Merge Sort requires additional space to store the sublists during the merging phase, which can be a limiting factor for large lists with limited memory.
Method 6
Quick Sort
Quick Sort is a divide-and-conquer algorithm that selects a pivot element, partitions the list into sublists, and recursively sorts them.
Quick Sort is famous for its efficiency.
How to sort a list in ascending order in Python without sort()?
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
arr = [5, 2, 1, 6, 9, 7]
print("Original List;", arr)
sorted_arr = quick_sort(arr)
print("Sorted List:", sorted_arr)
Run this code on our free Online Python Compiler.
Output
Original List; [5, 2, 1, 6, 9, 7]
Sorted List: [1, 2, 5, 6, 7, 9]
Advantages: Sorting a list ascending order in Python without sort
- Quick Sort has an average-case time complexity of O(n log n), making it one of the fastest sorting algorithms.
- It is an in-place sorting algorithm, meaning it requires little additional memory beyond the input list.
- Quick Sort often outperforms other sorting algorithms in practice.
Disadvantages
- The worst-case time complexity of Quick Sort is O(n^2) when the pivot selection is unfavorable, swhich can occur when we have the input list is already sorted or nearly sorted.
- Quick Sort is not a stable sorting algorithm, meaning the relative order of equal elements may change after sorting.
Method 7
Heap Sort
Heap Sort uses a binary heap, a complete binary tree where every parent node is smaller (or larger) than its children.
It repeatedly extracts the minimum (or maximum) element from the heap and places it in the sorted portion.
How to sort a list in ascending order in Python without sort()?
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
return arr
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)
# Example usage
arr = [5, 2, 1, 6, 9, 7]
print("Original List;", arr)
sorted_arr = heap_sort(arr)
print("Sorted List:", sorted_arr)Click on this code and it will be copied automatically.
Then you can run it on our free Online Python Compiler.
Output
Original List; [5, 2, 1, 6, 9, 7]
Sorted List: [1, 2, 5, 6, 7, 9]
Advantages
- Heap Sort has a time complexity of O(n log n) in all cases, making it efficient for large lists.
- It is an in-place sorting algorithm, requiring minimal additional memory beyond the input list.
- Heap Sort guarantees consistent performance and is particularly useful when extracting the smallest (or largest) elements from a list is required.
Disadvantages
- Heap Sort has a larger constant factor compared to other sorting algorithms, making it slower for smaller lists.
- It requires additional code complexity to maintain and manipulate the heap structure during the sorting process.
Wrapping Up
Conclusions
In conclusion, understanding the different sorting algorithms and their characteristics is essential for selecting the most appropriate method for a given scenario.
While some algorithms, such as Bubble Sort and Selection Sort, are simple to implement, they are not suitable for large lists due to their inefficient time complexity.
On the other hand, algorithms like Merge Sort, Quick Sort, and Heap Sort offer better time complexity and performance for larger datasets, with each having its own advantages and considerations.
Consider the size of the list, the nature of the data, stability requirements, and memory constraints when choosing a sorting algorithm.
