1
\$\begingroup\$
a = [5, 2, 4, 6, 1, 3]

def insert(arr):
    if len(arr) == 1:
        return arr
    # outer loop
    for i in range(1, len(arr)): 
        # inner loop
        for j in range(i, 0, -1):
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
    return arr

print(insert(a))

I am getting a time out for this program implementing bubble sort. Where is the problem and how can I optimize this? My hunch is that it might be the inner loop, which loops through the list backward, but I can't seem to understand why it would take like 4.5s to sort the above list.

\$\endgroup\$
  • 2
    \$\begingroup\$ This doesn't look like Quicksort to me. More like a type of bubblesort. \$\endgroup\$ – Gloweye Oct 10 at 10:23
  • 1
    \$\begingroup\$ I agree with Gloweye, this looks like bubble sort and bubble sort is in fact one of the most inefficient sorting algorithms, so it's not unlikely to take some time sorting things \$\endgroup\$ – bullseye Oct 10 at 10:30
  • \$\begingroup\$ There is no reason to comment # outer loop and # inner loop. Anyone can see that for themselves. You really don't need comments for the obvious and the real goal is to write your code in a way that removes the need for comments by making the code readable. readability > shorter code. Of coarse there will be some cases where comments will be needed but for the most part you can avoid things like # this loop does this thing or # setting up my variables and so on. \$\endgroup\$ – Mike - SMT Oct 10 at 12:26
  • 2
    \$\begingroup\$ If I run you exact code here, it runs quite fast. Fast enough for me to get the same timestamp before and after execution(python's time.time() - I dont bother with timeit for something like this). Could you sort this out and then edit that into the question ? \$\endgroup\$ – Gloweye Oct 10 at 12:39
  • 1
    \$\begingroup\$ Why would you call a sorting function insert? \$\endgroup\$ – 409_Conflict Oct 15 at 10:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.