I made two source codes of the insertion sort algorithm.
def insertsort(iterable) :
for current in range(len(iterable)) : # 'current' is the index of the element being sorted
compare, n = 0,0 # Initializes 'compare' and 'n' which is used in for-loop in each current for-loop
current_value = iterable[current] # Saves the element being sorted since the corresponding space will be assigned by the leading value
for compare in range(0,current) : # Compares the element from [0] to the element right ahead of [current]
if iterable[compare] > iterable[current] : # Finds where to insert 'current_value,' stored value of [current]
for n in range(current,compare,-1) : # Translate the values to one space to make the space where 'current_value' will be put empty
iterable[n] = iterable[n-1]
iterable[compare] = current_value # Insert the saved value of [current] to the right place
return(iterable)
The first one is the one I made myself without any guide.
def insertsort(iterable) :
for current in range(1,len(iterable)) : # iterable[0] is consdiered as resorted in the beginning
current_value = iterable[current] # saving current value
compare = current
while 0 < compare and iterable[compare-1] > current_value : # finding out where to put the sorted current value
iterable[compare] = iterable[compare-1] # this line in the while loop moves the elements not sorted
compare -= 1
iterable[compare] = current_value # put current value into the right place that the while loop found out
return(iterable)
The second is one I made looking at some webpages.
Comparing two, I found that the second from the internet is shorter than the one I made.
The second also demonstrated seemingly-efficient performance according to the 10-time average runtime, sorting 10000 consecutive elements (data = [i for i in range(10000, 0, -1)]
It was about 0.4 seconds faster while spending about 16 seconds to sort them all.
However, when testing with 100,000 consecutive elements(data = [i for i in range(100000, 0 ,-1)]), the first one(which I made) was faster than the second one.
The first one was about 1700 seconds, which is 200 seconds faster than the second one.
Here is my question.
- What is the time complexity of each code? I assume both are n^2 although I'm not sure.
- Why does the one I made seem to show better performance? I made for-loop and if-statement into while loop in the second one, but made it slower I guess.
Just in case, I attach the time-measurement method that I used. I referred to https://stackoverflow.com/a/1557584
