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

Reset to default
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\$ Commented 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\$ Commented 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\$ Commented Apr 29, 2020 at 18:38
  • 1
    \$\begingroup\$ @vnp Shall we continue this in chat \$\endgroup\$ Commented Apr 29, 2020 at 22:33

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.