3
\$\begingroup\$

Is my approach to insertion Sort in Python efficient?

What can be improved efficiency wise?

def insertion_sort(array):
    sorted_array = []  

    for elem in array:
        insertion_index = len(sorted_array) #insert at end of list by default
        for elem_sorted in sorted_array:
            if elem_sorted > elem:
                insertion_index = sorted_array.index(elem_sorted)
                break
        sorted_array.insert(insertion_index, elem)
    return sorted_array


num_elems = int(input('Number Of Elements?: '))
array = [int(input(f'Enter Number#{i+1}: ')) for i in range(num_elems)]
a = insertion_sort(array)
print(a)
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

You are looping over the array elements, and once you find an element greater than the element you are about to insert, you have to again find that element in the array of elements.

        insertion_index = len(sorted_array)
        for elem_sorted in sorted_array:
            if elem_sorted > elem:
                insertion_index = sorted_array.index(elem_sorted)
                break

You could instead use enumerate to extract both the element and its index:

        insertion_index = len(sorted_array)
        for index, elem_sorted in sorted_array:
            if elem_sorted > elem:
                insertion_index = index
                break

When you search for an element using a for loop and break when you find the element of interest, if you don't find the element, the for loop will execute an optional else: clause, so you don't need to preset the insertion_index:

        for index, elem_sorted in sorted_array:
            if elem_sorted > elem:
                insertion_index = index
                break
        else:
            insertion_index = len(sorted_array)

Biggest inefficiency

sorted_array is in sorted order. You could use a binary search to find the insertion location, \$O(\log N)\$, instead of a linear search \$O(N)\$.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Second advice is very wrong. Search will be necessarily followed by insertion, which is \$O(N)\$, and binary serch will drive the overall complexity to \$O(N*(N + \log N))\$. Insertion sort uses linear search for the reason. \$\endgroup\$
    – vnp
    Apr 29, 2020 at 4:58
  • \$\begingroup\$ @vnp Linear search + linear insertion is \$O(N + N)\$, which is \$O(N)\$. Binary search + linear search is \$O(\log N + N)\$, which is still \$O(N)\$, since \$O(\log N) \lt O(N)\$. Total complexity is \$O(N^2)\$ either way. A binary search should still speed up the algorithm, but without improving the overall time complexity. \$\endgroup\$
    – AJNeufeld
    Apr 29, 2020 at 5:07
  • \$\begingroup\$ Linear search + linear insertion is not \$O(N + N)\$. This would be the case if the insertion started from the beginning. On the contrary, the insertion starts from the insertion point, which search would return. Together search and insertion do one pass over the array. Compare it with the binary search worst case (all insertions are into the beginning of the array). \$\endgroup\$
    – vnp
    Apr 29, 2020 at 18:38
  • 1
    \$\begingroup\$ @vnp Shall we continue this in chat \$\endgroup\$
    – AJNeufeld
    Apr 29, 2020 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.