The selection sort algorithm sorts an array by iteratively finding the minimum (for ascending order) / maximum (for descending order) element from the unsorted part and putting it at the beginning of the array.

The algorithm will be considering two subarrays in a given array.

1. The subarray which is already sorted.
2. Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order)/ the maximum element (considering descending order) from the unsorted subarray is picked and moved to the sorted subarray. The movement is the process of swapping the minimum element with the current element.

How selection sort works ?

We will see the implementation of sorting in ascending order.

Consider the array : 29,10,14,37,14

First Iteration

Initially the val of min_index is 0. The element at the min_index is 29.

Then we can iterate over the rest of the array to find if there are any element which are minimum than the element at min_index.

By iterating, we found 10 is the minimum element present in the array. Thus, replace 29 with 10. After one iteration 10, which happens to be the least value in the array, tends to appear in the first position of the sorted list.

Second Iteration

Now the value of min_index will be incremented by 1. So now it will be min_index = 1 . Then we can iterate over the rest of the array to find if the there are any element which are minimum than the element at min_index.

By iterating, we found 14 is the minimum element present in the array. Thus, swap 29 with 14.

Third Iteration

We can repeat the same process till the entire array is sorted.

Now the value of min_index will be incremented by 1. So now it will be min_index = 2 . Then we can iterate over the rest of the array to find if the there are any element which are minimum than the element at min_index.

By iterating, we found 14 is the minimum element present in the array. Thus, swap 29 with 14.

Fourth Iteration

Now the value of min_index will be incremented by 3. So now it will be min_index = 3 . Then we can iterate over the rest of the array to find if the there are any element which are minimum than the element at min_index.

By iterating, we found 29 is the minimum element present in the array. Thus, swap 29 with 37.

Its Done.

After 4th iteration, the entire array is sorted.

So we can define the approach like,

• Initialize minimum value(min_index) to location 0
• Traverse the array to find the minimum element in the array
• While traversing if any element smaller than min_index is found then swap both the values.
• Then, increment min_index to point to next element
• Repeat until array is sorted

Code

def selection_sort(array, size):
    
    for itr in range(size):
        min_index = itr
        for ctr in range(itr + 1, size):
            if array[ctr] < array[min_index]:
                min_index = ctr
        array[itr], array[min_index] = array[min_index], array[itr]
 
arr = [29,10,14,37,14]
size = len(arr)
selection_sort(arr, size)

print(arr)

Complexity analysis

Time Complexity

The sort complexity is used to express the number of execution times it takes to sort the list. The implementation has two loops. The outer loop which picks the values one by one from the list is executed n times where n is the total number of values in the list. The inner loop, which compares the value from the outer loop with the rest of the values, is also executed n times where n is the total number of elements in the list.

Therefore, the number of executions is (n * n), which can also be expressed as O(n2).

1. Worst case – this is where the list provided is in descending order. The algorithm performs the maximum number of executions which is expressed as [Big-O] O(n2)
2. Best case – this occurs when the provided list is already sorted. The algorithm performs the minimum number of executions which is expressed as [Big-Omega] Ω(n2)
3. Average case – this occurs when the list is in random order. The average complexity is expressed as [Big-theta] Θ(n2)

Space Complexity

Since selection sort is an inplace sorting algorithm, it has a space complexity of O(1) as it requires one temporal variable used for swapping values.

Is Selection sort algorithm stable ?

The default implementation is not stable. However it can be made stable. But it can be achived using stable selection sort.

Is Selection Sort Algorithm in-place?

Yes, it does not require extra space.

When to use selection sort ?

1. Selection sort can be good at checking if everything is already sorted .
2. It is also good to use when memory space is limited. This is because unlike other sorting algorithms, selection sort doesn’t go around swapping things until the very end, resulting in less temporary storage space used.
3. When a simple sorting implementation is desired
4. When the array to be sorted is relatively small

When to avoid selection sort ?

1. The array to be sorted has a large number of elements
2. The array is nearly sorted
3. You want a faster run time and memory is not a concern.

Summary

1. Selection sort is an in-place comparison algorithm that is used to sort a random list into an ordered list. It has a time complexity of O(n2)
2. The list is divided into two sections, sorted and unsorted. The minimum value is picked from the unsorted section and placed into the sorted section.
3. This thing is repeated until all items have been sorted.
4. The time complexity measures the number of steps required to sort the list.
5. The worst-case time complexity happens when the list is in descending order. It has a time complexity of [Big-O] O(n2)
6. The best-case time complexity happens when the list is already in ascending order. It has a time complexity of [Big-Omega] O(n2)
7. The average-case time complexity happens when the list is in random order. It has a time complexity of [Big-theta] O(n2)
8. The selection sort is best used when you have a small list of items to sort, the cost of swapping values does not matter, and checking of all the values is mandatory.
9. The selection sort does not perform well on huge lists

Bonus Section

For the bigger array, how selection sort will work with insertion sort ?

The size of the array involved is rarely of much consequence. The real question is the speed of comparison vs. copying. The time a selection sort will win is when a comparison is a lot faster than copying. Just for example, let’s assume two fields: a single int as a key, and another megabyte of data attached to it. In such a case, comparisons involve only that single int, so it’s really fast, but copying involves the entire megabyte, so it’s almost certainly quite a bit slower.

Since the selection sort does a lot of comparisons, but relatively few copies, this sort of situation will favor it.

Introduction

Binary insertion sort is a sorting algorithm similar to insertion sort, but instead of using linear search to find the position where the element should be inserted, we use binary search. Thus, we reduce the number of comparisons for inserting one element from O(N) (Time complexity in Insertion Sort) to O(log N).

Best of two worlds

Binary insertion sort is a combination of insertion sort and binary search.

Insertion sort is sorting technique that works by finding the correct position of the element in the array and then inserting it into its correct position. Binary search is searching technique that works by finding the middle of the array for finding the element.

As the complexity of binary search is of logarithmic order, the searching algorithm’s time complexity will also decrease to of logarithmic order. Implementation of binary Insertion sort. this program is a simple Insertion sort program but instead of the standard searching technique binary search is used.

How Binary Insertion Sort works ?

Process flow:

In binary insertion sort, we divide the array into two subarrays — sorted and unsorted. The first element of the array is in the sorted subarray, and the rest of the elements are in the unsorted one.

We then iterate from the second element to the last element. For the i-th iteration, we make the current element our “key.” This key is the element that we have to add to our existing sorted subarray.

Example

Consider the array 29, 10, 14, 37, 14,

First Pass

Key = 1

Since we consider the first element is in the sorted array, we will be starting from the second element. Then we apply the binary search on the sorted array.

In this scenario, we can see that the middle element in sorted array (29) is greater than the key element 10 (key = 1).

Now we need to place the key element before the middle element (i.e.) to the position of 0. Then we can shift the remaining elements by 1 position.

Increment the value of key.

Second Pass

Key = 2

Now the key element is 14. We will apply binary search in the sorted array to find the position of the key element.

In this scenario, by applying binary search, we can see key element to be placed at index 1 (between 10 and 29). Then we can shift the remaining elements by 1 position.

Third Pass

Key = 3

Now the key element is 37. We will apply binary search in the sorted array to find the position of the key element.

In this scenario, by applying binary search, we can see key element is placed in its correct position.

Fourth Pass

Key = 4

Now the key element is 14. We will apply binary search in the sorted array to find the position of the key element.

In this scenario, by applying binary search, we can see key element to be placed at index 2 (between 14 and 29). Then we can shift the remaining elements by 1 position.

Now we can see all the elements are sorted.

def binary_search(arr, key, start, end):
    if start == end:
        if arr[start] > key:
            return start
        else:
            return start+1
 
    if start > end:
        return start
 
    mid = (start+end)//2
    if arr[mid] < key:
        return binary_search(arr, key, mid+1, end)
    elif arr[mid] > key:
        return binary_search(arr, key, start, mid-1)
    else:
        return mid
 
def insertion_sort(arr):
    total_num = len(arr)
    for i in range(1, total_num):
        key = arr[i]
        j = binary_search(arr, key, 0, i-1)
        arr = arr[:j] + [key] + arr[j:i] + arr[i+1:]
    return arr
 

sorted_array = insertion_sort([29, 10, 14, 37, 14])
print("Sorted Array : ", sorted_array)

Complexity Analysis

Worst Case

For inserting the i-th element in its correct position in the sorted, finding the position (pos) will take O(log i) steps. However, to insert the element, we need to shift all the elements from pos to i-1. This will take i steps in the worst case (when we have to insert at the starting position).

We make a total of N insertions. so, the worst-case time complexity of binary insertion sort is O(N^2).

This occurs when the array is initially sorted in descending order.

Best Case

The best case will be when the element is already in its sorted position. In this case, we don’t have to shift any of the elements; we can insert the element in O(1).

But we are using binary search to find the position where we need to insert. If the element is already in its sorted position, binary search will take (log i) steps. Thus, for the i-th element, we make (log i) operations, so its best-case time complexity is O(N log N).

This occurs when the array is initially sorted in ascending order.

Average Case

For average-case time complexity, we assume that the elements of the array are jumbled. Thus, on average, we will need O(i /2) steps for inserting the i-th element, so the average time complexity of binary insertion sort is O(N^2).

Space Complexity Analysis

Binary insertion sort is an in-place sorting algorithm. This means that it only requires a constant amount of additional space. We sort the given array by shifting and inserting the elements.

Therefore, the space complexity of this algorithm is O(1) if we use iterative binary search. It will be O(logN) if we use recursive binary search because of O(log N) recursive calls.

Is Binary Insertion Sort a stable algorithm

It is a stable sorting algorithm, the elements with the same values appear in the same order in the final array as they were in the initial array.

Cons and Pros

1. Binary insertion sort works efficiently for smaller arrays.
2. This algorithm also works well for almost-sorted arrays, where the elements are near their position in the sorted array.
3. However, when the size of the array is large, the binary insertion sort doesn’t perform well. We can use other sorting algorithms like merge sort or quicksort in such cases.
4. Making fewer comparisons is also one of the strengths of this sorting algorithm; therefore, it is efficient to use it when the cost of comparison is high.
5. Its efficient when the cost of comparison between keys is sufficiently high. For example, if we want to sort an array of strings, the comparison operation of two strings will be high.

Bonus Section

Binary Insertion Sort has a quadratic time complexity just as Insertion Sort. Still, it is usually faster than Insertion Sort in practice, which is apparent when comparison takes significantly more time than swapping two elements.