How to sort a list in Python without sort function?

Sorting a List in Python without the Built-in Sort Function

Python provides a built-in sort function that sorts lists in ascending or descending order. However, in some situations, you might need to sort a list without using the built-in sort function. In this article, we will explore how to sort a list in Python without the built-in sort function.

Why Sort a List Without the Built-in Sort Function?

There are several scenarios where you might need to sort a list without using the built-in sort function. For example, you might want to sort a list of dictionaries based on a specific key, or you might want to sort a list of objects based on their attributes. In such cases, you need to implement a custom sorting algorithm.

Sorting Algorithms

There are several sorting algorithms that you can use to sort a list in Python. Here are a few examples:

• Bubble Sort: This is a simple sorting algorithm that works by repeatedly iterating through the list and swapping adjacent elements if they are in the wrong order.
• Selection Sort: This algorithm works by selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the beginning (or end) of the unsorted portion.
• Insertion Sort: This algorithm works by iterating through the list one element at a time, inserting each element into its proper position in the sorted portion of the list.
• Merge Sort: This is a divide-and-conquer algorithm that works by splitting the list into smaller sublists, sorting each sublist, and then merging the sorted sublists back together.

Implementing a Custom Sorting Algorithm

Here is an example of how you can implement a custom sorting algorithm using the Bubble Sort algorithm:

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]

    return lst

Implementing a Custom Sorting Algorithm Using the Selection Sort Algorithm

Here is an example of how you can implement a custom sorting algorithm using the Selection Sort algorithm:

def selection_sort(lst):

    n = len(lst)

    for i in range(n):

        min_idx = i

        for j in range(i + 1, n):

            if lst[j] < lst[min_idx]:

                min_idx = j

        lst[i], lst[min_idx] = lst[min_idx], lst[i]

    return lst

Implementing a Custom Sorting Algorithm Using the Insertion Sort Algorithm

Here is an example of how you can implement a custom sorting algorithm using the Insertion Sort algorithm:

def insertion_sort(lst):

    n = len(lst)

    for i in range(1, n):

        key = lst[i]

        j = i - 1

        while j >= 0 and lst[j] > key:

            lst[j + 1] = lst[j]

            j -= 1

        lst[j + 1] = key

    return lst

Implementing a Custom Sorting Algorithm Using the Merge Sort Algorithm

Here is an example of how you can implement a custom sorting algorithm using the Merge Sort algorithm:

def merge_sort(lst):

    if len(lst) <= 1:

        return lst

    mid = len(lst) // 2

    left_half = merge_sort(lst[:mid])

    right_half = merge_sort(lst[mid:])

    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

    merged.extend(left[left_index:])

    merged.extend(right[right_index:])

    return merged

Sorting a List in Python without the Built-in Sort Function

Here is an example of how you can sort a list in Python without using the built-in sort function:

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]

    return lst



def selection_sort(lst):

    n = len(lst)

    for i in range(n):

        min_idx = i

        for j in range(i + 1, n):

            if lst[j] < lst[min_idx]:

                min_idx = j

        lst[i], lst[min_idx] = lst[min_idx], lst[i]

    return lst



def insertion_sort(lst):

    n = len(lst)

    for i in range(1, n):

        key = lst[i]

        j = i - 1

        while j >= 0 and lst[j] > key:

            lst[j + 1] = lst[j]

            j -= 1

        lst[j + 1] = key

    return lst



def merge_sort(lst):

    if len(lst) <= 1:

        return lst

    mid = len(lst) // 2

    left_half = merge_sort(lst[:mid])

    right_half = merge_sort(lst[mid:])

    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

    merged.extend(left[left_index:])

    merged.extend(right[right_index:])

    return merged



# Example usage

lst = [64, 34, 25, 12, 22, 11, 90]

print("Original list:", lst)

print("Sorted list:", bubble_sort(lst))

print("Sorted list:", selection_sort(lst))

print("Sorted list:", insertion_sort(lst))

print("Sorted list:", merge_sort(lst))

Conclusion

In this article, we explored how to sort a list in Python without using the built-in sort function. We discussed several sorting algorithms, including Bubble Sort, Selection Sort, Insertion Sort, and Merge Sort. We also implemented custom sorting algorithms using these algorithms. Finally, we provided an example usage of each sorting algorithm.