Insertion Sort in Python

by

Sure, here’s an implementation of insertion sort in Python:

def insertion_sort(arr):
    """
    Sorts an array using the insertion sort algorithm.
    """
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

Here’s how it works:

  • We start by iterating through the array from index 1 to the end.
  • For each element at index i, we store its value in the variable key.
  • We then compare key with the elements before it, starting at index j = i - 1.
  • If the element at index j is greater than key, we shift it one position to the right and decrement j.
  • We continue this process until we find an element that is less than or equal to key, at which point we insert key at index j + 1.

After the loop is complete, the array will be sorted in ascending order.

What is the meaning of in-place and stable?:

“In-place” and “stable” are two properties of sorting algorithms.

“In-place” means that the algorithm sorts the array by modifying the elements of the original array, rather than creating a new array to hold the sorted values. In other words, the algorithm uses only a constant amount of extra memory space, regardless of the size of the input array. The advantage of an in-place sorting algorithm is that it saves memory, which can be important when sorting large arrays.

“Stable” means that the algorithm preserves the relative order of equal elements in the input array. For example, if we have two elements with the same value in the input array, and one appears before the other, a stable sorting algorithm will ensure that the element that appears first in the input array will also appear first in the sorted array. In other words, the algorithm will not change the order of equal elements during the sorting process.

These two properties are important to consider when choosing a sorting algorithm for a particular task. In some cases, we may prioritize memory efficiency and choose an in-place algorithm, while in others, we may prioritize preserving the relative order of equal elements and choose a stable algorithm.

Implementation:

Sure, here’s an implementation of an in-place, stable sorting algorithm called “Insertion Sort” in Python:

def insertion_sort(arr):
    """
    Sorts an array in-place using the insertion sort algorithm.
    """
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

This implementation modifies the original array arr to sort it in-place, and it also preserves the relative order of equal elements, making it a stable sorting algorithm.

Here’s how it works:

  • We start by iterating through the array from index 1 to the end.
  • For each element at index i, we store its value in the variable key.
  • We then compare key with the elements before it, starting at index j = i - 1.
  • If the element at index j is greater than key, we shift it one position to the right and decrement j.
  • We continue this process until we find an element that is less than or equal to key, at which point we insert key at index j + 1.

After the loop is complete, the array will be sorted in ascending order. Since we modify the original array rather than creating a new one, this implementation is an in-place sorting algorithm. Additionally, since we only move elements when key is less than the element before it, the algorithm preserves the relative order of equal elements, making it a stable sorting algorithm.

Sorting Custom Objects:

To sort a list of custom objects in Python, you can use the sorted() function or the sort() method of the list object, and specify a key function to indicate which attribute to use for sorting. Here’s an example:

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age
    
    def __repr__(self):
        return f"Person(name={self.name}, age={self.age})"

people = [
    Person("Alice", 25),
    Person("Bob", 30),
    Person("Charlie", 20),
    Person("Dave", 25),
]

# sort by name (ascending)
sorted_people = sorted(people, key=lambda p: p.name)

# sort by age (descending)
people.sort(key=lambda p: p.age, reverse=True)

print(sorted_people)
print(people)

In this example, we define a Person class with two attributes, name and age. We create a list of Person objects and then sort it in two ways:

  • First, we use the sorted() function to create a new sorted list based on the name attribute of each Person object, in ascending order.
  • Next, we use the sort() method of the list object to sort the list in place based on the age attribute of each Person object, in descending order.

To specify the key function for sorting, we pass a lambda function that takes a Person object as input and returns the attribute to use for sorting. In the first case, we sort by name, so we return p.name, and in the second case, we sort by age, so we return p.age.

The __repr__() method of the Person class is used to provide a string representation of the object for printing purposes.

Time Complexity in Insertion Sort:

The time complexity of Insertion Sort is O(n^2) in the worst case and O(n) in the best case, where n is the number of elements in the array being sorted.

The worst case occurs when the array is in reverse order, which means that for each element, the algorithm has to compare it with all the previous elements before finding the correct position to insert it. In this case, the outer loop will execute n-1 times, and the inner loop will execute approximately n/2 times on average, resulting in a total of approximately (n-1)*(n/2) = (n^2-n)/2 comparisons and swaps. Therefore, the worst-case time complexity is O(n^2).

The best case occurs when the array is already sorted or contains only one element. In this case, the algorithm only needs to make n-1 comparisons and no swaps, as each element is already in its correct position. Therefore, the best-case time complexity is O(n).

In general, the time complexity of Insertion Sort is better than some other sorting algorithms like Bubble Sort, but worse than others like Quick Sort and Merge Sort. However, Insertion Sort has some advantages over these other algorithms in terms of simplicity, space complexity, and its ability to efficiently sort small arrays or partially sorted arrays.

Conclusion:

In this conversation, we discussed the Insertion Sort algorithm in Python. Insertion Sort is an in-place, stable sorting algorithm that iterates through an array and inserts each element into its proper place in a sorted subarray. We provided an implementation of the algorithm in Python and discussed its time complexity, which is O(n^2) in the worst case and O(n) in the best case.

We also discussed how to sort custom objects in Python using the sorted() function or the sort() method, and specifying a key function to indicate which attribute to use for sorting.

Overall, Insertion Sort is a simple and efficient algorithm for sorting small or partially sorted arrays, and is useful to know when working with custom objects that need to be sorted based on a specific attribute.