💡 Problem Formulation: Sorting an array is a fundamental task in programming. Specifically, we are interested in the process of sorting an array using insertion sort algorithm in Python, where we quantify the efficiency of sorting by counting the number of shifts performed. For an unsorted array like [4, 3, 2, 1], we aim to determine the number of shifts required to sort it to [1, 2, 3, 4].
Method 1: Basic Insertion Sort Function
This method involves writing a basic insertion sort function which, apart from sorting the array, also counts and returns the number of shifts required to sort the array. The function iterates over the array elements and positions each element in its correct place in the sorted part of the array, while keeping a count of the shifts.
Here’s an example:
def insertion_sort(arr):
shift_counter = 0
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
shift_counter += 1
arr[j+1] = key
return shift_counter
# Test the function
print(insertion_sort([4, 3, 2, 1]))
The output of this code snippet will be: 6
This code defines a function insertion_sort() that sorts an input array while counting shifts. Each time an element is moved one position to the left (a “shift”), the shift_counter is incremented. The function sorts the array in-place and returns the number of shifts at the end. When applied to an array in reverse order, the number of shifts reflects the sum of the indices of each element, as each has to move to the beginning of the array.
Method 2: Enhanced Insertion Sort with Early Stopping
This enhanced insertion sort method builds on the basic insertion sort algorithm by adding an early stopping condition. If no shift is required for an element, the algorithm moves to the next element. This optimization can reduce the number of unnecessary comparisons and shifts.
Here’s an example:
def enhanced_insertion_sort(arr):
shift_counter = 0
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
shift_counter += 1
arr[j+1] = key
if j != i-1:
shift_counter += 1
return shift_counter
# Test the function
print(enhanced_insertion_sort([4, 3, 2, 1]))
The output of this code snippet will be: 6
This version of the insertion sort function includes an early stopping optimization. The shift counter is increased not only when shifts occur, but also after placing each key in its position if any shifts have happened at all in that iteration, which can provide better insight into the total number of operations performed.
Summary/Discussion
- Method 1: Basic Insertion Sort. This is the most straightforward method. It is easy to understand and implement, but it doesn’t incorporate optimizations that can reduce unnecessary operations. Suitable for small arrays or educational purposes.
- Method 2: Enhanced Insertion Sort with Early Stopping. It introduces a small optimization which can help to reduce the number of shifts in scenarios where no shifts are necessary. This method is slightly more complex than the basic version, but can perform better on presorted or partially sorted arrays.