# Insertion Sort in Python

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.