How to sort a list in Python without the sort function?

To sort lists without using the built-in sort() function, the algorithms include bubble sort, selection sort, insertion sort, quick sort, merge sort, and heap sort. The post also provides examples of how to use these sorting techniques to sort a list in Python.

built in functions, how to sort a list in python without sort function

Sorting a list in Python is a common task, and the built-in sort() function is the go-to method. However, did you know that Python sort can also be achieved without using the sort() function? In this blog, we will explore alternative methods to sort a Python list in various ways. By the end, you'll have a deeper understanding of different sorting techniques and their implementations, empowering you to sort lists efficiently using Python sort in various scenarios.

Sorting Techniques

random import shuffle, list in ascending order

Bubble Sort Algorithm:

The Bubble Sort algorithm is simple and easy to understand. It compares all the elements in the list and swaps them if they are in the wrong order. This process is repeated until the list is completely sorted. While Bubble Sort is straightforward, it may not be the best choice for sorting large lists.

def bubble_sort(lst):
    n = len(lst)
    for i in range(n):
        for j in range(0, n - i - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]

The sorting criteria for the bubble sort algorithm is the comparison between adjacent elements in the list. This Python program has a bubble_sort function, designed to sort a given list lst, and operates through an iterative process. Firstly, it calculates the length of the list, denoted as n, using the len(lst) function. The algorithm then initiates an outer loop, which iterates n times, each iteration focusing on one element within the list. Concurrently, an inner loop is nested within the outer loop. This inner loop ranges from the beginning of the list to the (n - i - 1)th element, where i represents the current iteration of the outer loop.

Within the inner loop, an if block evaluates whether the current element, lst[j], is greater than the subsequent element, lst[j + 1]. In case this comparison is true, a swap operation transpires. Consequently, the smaller value is positioned before the larger one. This comparison and swapping process iterates through every adjacent pair of elements until the largest element "bubbles up" to the list's end. Upon the completion of the inner loop for each i, the largest element resides at the end of the list, enabling the subsequent outer loop iteration to concentrate on the remaining elements that are yet to be sorted.

Selection Sort Algorithm:

The Selection Sort algorithm finds the smallest element in the unsorted part of the list and moves it to the beginning. It then continues this process for the remaining unsorted elements until the entire list is sorted. Although Selection Sort can be more efficient than Bubble Sort, it still may not be the best choice for large lists.

def selection_sort(lst):
    n = len(lst)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if lst[j] < lst[min_index]:
                min_index = j
        lst[i], lst[min_index] = lst[min_index], lst[i]

Descending order sorting can be achieved by modifying the selection_sort function. Instead of finding the smallest element, find the largest element and swap it with the current element.

This Python program has a function named selection_sort that implements the Selection Sort algorithm to sort a given list lst. It begins by determining the length of the list using n = len(lst). The main loop iterates through each element of the list, identified by the index i. Within this loop, a variable min_index is initialized to i, representing the index of the minimum value encountered so far. Another nested loop starts from i + 1 and scans through the remaining elements to find the index of the smallest value. If an element at index j is smaller than the element at min_index, min_index is updated to j, reflecting the new index of the smallest value in the remaining portion of the list.

Once the inner loop completes its search for the smallest value, a swap is performed between the element at index i and the element at min_index. As the main loop progresses, the sorted portion of the list gradually expands, and the process repeats until the entire list is sorted. The algorithm sorts the list in place, meaning that the original list lst is directly modified as the sorting progresses, without requiring the creation of a new list.

Insertion Sort Algorithm:

The Insertion Sort algorithm builds the sorted list one element at a time. It efficiently places each element in its proper position by comparing it with the elements already sorted. Insertion Sort is often used for small or nearly sorted lists.

def insertion_sort(lst):
    for i in range(1, len(lst)):
        key = lst[i]
        j = i - 1
        while j >= 0 and key < lst[j]:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = key

This Python program has an `insertion_sort` function that efficiently arranges elements within a list `lst`. Starting from the second element, the algorithm considers each subsequent item and designates it as the 'key'. The variable `j` is then initialized to the index one less than the key's position. This loop scrutinizes the key against preceding elements, effectively moving larger values one step forward to accommodate the eventual placement of the key. The 'key' is inserted at the appropriate position, where the loop ends.

In essence, the `insertion_sort` method maintains a 'sorted' portion at the beginning of the list, incrementally extending it by integrating the next unsorted element at its suitable spot. This 'sorted' portion expands iteratively, leading to the entire list becoming sorted by the time the algorithm concludes. The method's efficiency lies in its approach of addressing only the necessary portions of the list, minimizing unnecessary comparisons and swaps, and making it particularly suitable for relatively small lists or partially sorted datasets.

Quick Sort Algorithm:

Quick Sort is a highly efficient sorting algorithm that follows the Divide and Conquer approach. It works by selecting a pivot element from the list and partitioning the other elements into two sub-lists: those less than the pivot and those greater than the pivot. The sub-lists are then recursively sorted using Quick Sort. This process continues until the entire list is sorted. Quick Sort is known for its fast average-case performance and is widely used in practice.

def quick_sort(lst):
    if len(lst) <= 1:
        return lst
    else:
        pivot = lst[0]
        lesser = [x for x in lst[1:] if x < pivot]
        greater = [x for x in lst[1:] if x >= pivot]
        return quick_sort(lesser) + [pivot] + quick_sort(greater)

The `quick_sort` function employs a popular sorting technique called Quick Sort. If the length of the input list `lst` is equal to or less than one, it's considered already sorted and is directly returned. Otherwise, the function identifies a "pivot" element, which is typically the first element of the list. Then, it separates the list into two parts: `lesser`, containing elements smaller than the pivot, and `greater`, containing elements greater than or equal to the pivot. This division is achieved using Python's list comprehension.

Next, the function recursively applies `quick_sort` to both `lesser` and `greater`, which sorts these sublists in a similar manner. Finally, the sorted `lesser` sublist, the pivot element, and the sorted `greater` sublist are concatenated together and returned, resulting in the sorted version of the original list. This process repeats until the entire list is sorted, efficiently dividing and conquering the sorting task.

Merge Sort Algorithm:

Merge Sort is another Divide and Conquer algorithm that works by dividing the list into two halves and recursively sorting each half. Afterwards, it merges the sorted halves to obtain the final sorted list. Merge Sort has a stable time complexity of O(n log n) for both the average and worst-case scenarios, making it a reliable choice for sorting large lists.

def merge_sort(lst):
    if len(lst) > 1:
        mid = len(lst) // 2
        left_half = lst[:mid]
        right_half = lst[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]:
                lst[k] = left_half[i]
                i += 1
            else:
                lst[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            lst[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            lst[k] = right_half[j]
            j += 1
            k += 1

The provided code implements the Merge Sort algorithm to sort a given list `lst`. It recursively divides the list into smaller halves until each sublist contains only one element. Then, it merges these sorted sublists back together to create a fully sorted list. This process is performed by comparing elements within the `left_half` and `right_half` sublists and placing the smaller of the two into the final sorted list `lst`, incrementing the appropriate counters. This procedure repeats until all elements have been merged. The algorithm ensures a sorted output by progressively merging sublists until the entire list is sorted.

Heap Sort Algorithm:

Heap Sort uses a special data structure called a heap to sort elements in the list. It builds a max-heap or min-heap (depending on the desired order) from the list elements. The root of the heap represents the largest or smallest element, which is then swapped with the last element. The heap is reduced in size, and the process repeats until the list is sorted. Heap Sort has a time complexity of O(n log n) and is often used for sorting large data sets.

import heap

def heap_sort(lst):
    heapq.heapify(lst)
    sorted_list = [heapq.heappop(lst) for _ in range(len(lst))]
    lst[:] = sorted_list

This code demonstrates the implementation of the heap sort algorithm. It begins by importing the "heap" module. The `heap_sort` function takes a list called `lst` as input. Inside the function, the `heapify` function from the "heapq" module transforms the input list into a min-heap, rearranging its elements to meet the heap property. Then, a new list called `sorted_list` is generated using a list comprehension.

In this comprehension, the `heappop` function is repeatedly applied, extracting the smallest element from the min-heap and appending it to `sorted_list` for the length of the input list. Finally, the original list `lst` is updated using slicing to match the content of the sorted list, effectively achieving the sorting process. The heap sort leverages the min-heap structure to efficiently extract elements in ascending order.

Performance Considerations

When sorting a list in Python without the built-in sort() function, performance is crucial. Each method's efficiency depends on its time complexity, showing how sorting time grows with list size. Consider these performance aspects for popular sorting algorithms: Bubble Sort, Insertion Sort, Selection Sort, Quick Sort, Merge Sort, and Heap Sort.

Quick Sort and Merge Sort typically perform well with an average time complexity of O(n log n). However, Bubble Sort and Selection Sort have O(n^2) complexities, making them less efficient for large lists. Heap Sort is also O(n log n) but requires less memory due to in-place sorting.

Conclusion

Sorting a list in Python is a fundamental skill, and knowing different sorting techniques gives you more options to tackle sorting challenges. Whether you choose the sorted() function, Bubble Sort, Insertion Sort, Selection Sort, Quick Sort, Merge Sort, or Heap Sort, each method has its use cases and performance considerations. By understanding these methods, you can become a more versatile Python programmer, capable of efficiently sorting lists in various scenarios.

You can also check these blogs:

  1. How to check if an index exists in Python lists?
  2. Efficient Python Variable Clearing
  3. Python argparse
  4. How to handle with open exceptions in Python?
  5. Newton Raphson method in Python
  6. Python isdigit vs isnumeric
  7. Kalman Filter in Python
  8. Python shorthand if
  9. How to use Pi in Python?
  10. How to append multiple elements in a list in Python?