Geek Answers Handbook

How to insert sorting through swap or through pop () - insert ()?

I made my own version of insertion sorting, which uses pop and insert - to select the current element and insert it before the smallest element larger than the current one - instead of the standard swap back until an element of a larger size is found. When I run two on my computer, mine is about 3.5 times faster. However, when we did this in class, everything was much slower, which is really confusing. Anyway, here are two functions:

def insertionSort(alist):
    for x in range(len(alist)):
        for y in range(x,0,-1):
            if alist[y]<alist[y-1]:
                alist[y], alist[y-1] = alist[y-1], alist[y]
            else:
                break

def myInsertionSort(alist):
    for x in range(len(alist)):
       for y in range(x):
            if alist[y]>alist[x]:
                alist.insert(y,alist.pop(x))
                break

Which one should be faster? Does it alist.insert(y,alist.pop(x))resize listback and forth, and how does this affect time efficiency?

Here is my pretty primitive test of two functions:

from time import time
from random import shuffle

listOfLists=[]
for x in range(100):
    a=list(range(1000))
    shuffle(a)
    listOfLists.append(a)

start=time()
for i in listOfLists:
    myInsertionSort(i[:])
myInsertionTime=time()-start

start=time()
for i in listOfLists:
    insertionSort(i[:])
insertionTime=time()-start

print("regular:",insertionTime)
print("my:",myInsertionTime)
+4
1

, . .

  • lst.insert(y, lst.pop(x)) - O(n), lst.pop(x) O(len(lst) - x), , , , x dually lst.insert(y, _) O(len(lst) - y), .

    , O (n ^ 3) . , [, O (n ^ 2) O (n ^ 3)], , . , n n , O (n * n + n ^ 2) = O (n ^ 2), n ^ 2 , n ^ 2 . , , .

  • y. , .   , , ( ). , , , , , , .

    In [2]: %timeit insertionSort(list(range(10)))
100000 loops, best of 3: 5.46 us per loop

In [3]: %timeit myInsertionSort(list(range(10)))
100000 loops, best of 3: 8.47 us per loop

In [4]: %timeit insertionSort(list(reversed(range(10))))
10000 loops, best of 3: 20.4 us per loop

In [5]: %timeit myInsertionSort(list(reversed(range(10))))
100000 loops, best of 3: 9.81 us per loop

    () .

  • - O (n ^ 2). , .

  • , insert+pop , swap. , O (n ^ 2) O (n) -.

, . , , , , . . , , .

, : . , , ( ):

, :

In [6]: import random
   ...: input_list = list(range(10))
   ...: random.shuffle(input_list)
   ...: 

In [7]: %timeit insertionSort(input_list)  # Note: no input_list[:]!! Argh!
100000 loops, best of 3: 4.82 us per loop

In [8]: %timeit myInsertionSort(input_list)
100000 loops, best of 3: 7.71 us per loop

, :

In [11]: input_list = list(range(1000))
    ...: random.shuffle(input_list)

In [12]: %timeit insertionSort(input_list)  # Note: no input_list[:]! Argh!
1000 loops, best of 3: 508 us per loop

In [13]: %timeit myInsertionSort(input_list)
10 loops, best of 3: 55.7 ms per loop

, , , , .

insertionSort, , , -! , ( , !) myInsertionSort , ? , myInsertionSort - ! :

for x in range(len(alist)):
   for y in range(x):
        if alist[y]>alist[x]:
            alist.insert(y,alist.pop(x))
            break

, alist[y] > alist[x] . : "perfect! No swaps = > no O (n) work = > ", , , break , , n*(n+1)/2, .

, !!! , , , .

, , insert + pop swap, .

+2

More articles:


All Articles