A - compare

1. Build a new list as the result
2. Transfer the minimum value in original list into new list
3. Repeat step 2
4. End when the original list has length of 0 or 1

example code:

B - recursion

1. If the list has a length of 0 or 1, just return it.
2. Otherwise, return the minimum value as a single-value list plus the output list of the remnant list.

example code:

Benchmark

Which one is the best?
Firstly I made 20 640-length-integer list to test two sorting methods.

Then I copy the result data into R and visualize it:

The reason

• In sort1, we have two loops.

• One is for i in range(len(iList)) and the other is for x in iList[1:] which is inside the first one.
• For an i-th iteration, it has a sub-loop with n-i iteration (n=len(list)).
• So each sorting has $\frac{1}{2}n^2+n+\frac{1}{2}$ times iterations.
• Sort1’ order of growth is $O(n^2)$.
• In sort2, however, we use recursive loop.

• For the last recursion, it only have 2-time calculation. One for checking if’s condition and one for return value.
• The second last one has 4-time calculation plus 2-time calculation from the last recursion.
• The third last one also has 4-time calculation plus 6-time calculation from the second last recursion.
• Overall, recursive method has $4*(n-1)+2=4n-2$ times of calculation.
• Its order of growth is $O(n)$.

In conclusion, their calculation amount is not the same and this is the reason that sort1 spend much more time.
The advantage of recursion can be more obvious in big data.

0%