In this tutorial, I will explain how to sort a list in Python without using the sort() function. Someone asked me doubt on sorting a list without using the sort() function which made me explore more about this topic. Let us learn more about this topic today.
Sort a List in Python Without Using the sort() Function
To sort a list in Python without using the built-in sort() function, you can implement sorting algorithms like Bubble Sort, Selection Sort, or Merge Sort. For example, to sort the list [5, 2, 8, 1, 9] using Bubble Sort, you would repeatedly compare adjacent elements and swap them if they are in the wrong order until the entire list is sorted, resulting in [1, 2, 5, 8, 9].
Read How to Capitalize the First Letter of Every Word in a List using Python?
Bubble Sort Algorithm
One of the simplest sorting algorithms is the Bubble Sort algorithm. It works by repeatedly iterating through the list, comparing adjacent elements, and swapping them if they are in the wrong order. This process continues until the entire list is sorted. Here’s an example of how to implement Bubble Sort in Python:
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# Example usage
customer_names = ["John", "Emily", "Michael", "Amanda", "David"]
sorted_names = bubble_sort(customer_names)
print(sorted_names)Output:
['Amanda', 'David', 'Emily', 'John', 'Michael']You can see the output in the below screenshot.
As you can see, the Bubble Sort algorithm successfully sorts the list of customer names in alphabetical order without using the built-in function sort().
Time Complexity
The time complexity of the Bubble Sort algorithm is O(n^2), where n is the number of elements in the list. This means that the sorting time grows quadratically with the size of the input, making it inefficient for large lists. However, Bubble Sort is easy to understand and implement, making it a good choice for small lists or educational purposes.
Check out How to Check if Any Element in a List is Present in Another List using Python?
Selection Sort Algorithm
Another simple sorting algorithm is the Selection Sort algorithm. It works by dividing the list into two parts: a sorted portion and an unsorted portion. The algorithm repeatedly selects the minimum element from the unsorted portion and appends it to the sorted portion until the entire list is sorted. Here’s an example implementation of Selection Sort in Python:
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
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]
return arr
# Example usage
customer_names = ["Olivia", "Liam", "Emma", "Noah", "Ava"]
sorted_names = selection_sort(customer_names)
print(sorted_names)Output:
['Ava', 'Emma', 'Liam', 'Noah', 'Olivia']You can see the output in the below screenshot.
The Selection Sort algorithm successfully sorts the list of customer names alphabetically without relying on the sort() function.
Time Complexity
Like Bubble Sort, the time complexity of Selection Sort is O(n^2). It performs well for small lists but becomes inefficient for larger datasets.
Read How to Convert String to List in Python?
Insertion Sort Algorithm
Insertion Sort is another simple sorting algorithm that builds the final sorted list one element at a time. It works by dividing the list into a sorted portion and an unsorted portion. The algorithm iterates through the unsorted portion, picking one element at a time, and insert an element into its correct position in the sorted portion. Here’s an example of Insertion Sort in Python:
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# Example usage
customer_names = ["Sophia", "Jackson", "Isabella", "Aiden", "Mia"]
sorted_names = insertion_sort(customer_names)
print(sorted_names)Output:
['Aiden', 'Isabella', 'Jackson', 'Mia', 'Sophia']You can see the output in the below screenshot.
The Insertion Sort algorithm successfully sorts the list of customer names in alphabetical order without using the built-in sorting functions.
Time Complexity
Insertion Sort has a time complexity of O(n^2) in the worst and average cases, but it performs well for small lists or partially sorted lists. It is also relatively easy to implement and understand.
Check out How to Merge Lists Without Duplicates in Python?
Merge Sort Algorithm
Merge Sort is a more advanced sorting algorithm that follows the divide-and-conquer approach. It recursively divides the list into smaller sublists until each sublist contains only one element. Then, it merges the sublists back together in a sorted manner until the entire list is sorted. Here’s an example implementation of Merge Sort in Python:
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):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# Example usage
customer_names = ["Ethan", "Charlotte", "William", "Harper", "James"]
sorted_names = merge_sort(customer_names)
print(sorted_names)Output:
['Charlotte', 'Ethan', 'Harper', 'James', 'William']Merge Sort efficiently sorts the list of customer names alphabetically without relying on the built-in sort() function.
Time Complexity
The time complexity of Merge Sort is O(n log n), making it more efficient than the previous algorithms for larger lists. It guarantees a stable sort and is widely used in practice.
Read How to Convert a Dictionary to a List in Python?
Conclusion
In this tutorial, I explained how to sort a list in Python without using the sort() function. I implemented Bubble Sort, Selection Sort, Insertion Sort, and Merge Sort algorithms from scratch and discussed their time complexities.
You may read:
- How to Sort a List of Tuples by the First Element in Python?
- How to Get the Index of an Element in a List in Python?
- How to Unpack List in Python
I am Bijay Kumar, a Microsoft MVP in SharePoint. Apart from SharePoint, I started working on Python, Machine learning, and artificial intelligence for the last 5 years. During this time I got expertise in various Python libraries also like Tkinter, Pandas, NumPy, Turtle, Django, Matplotlib, Tensorflow, Scipy, Scikit-Learn, etc… for various clients in the United States, Canada, the United Kingdom, Australia, New Zealand, etc. Check out my profile.
