I've done the shakesort algorithm win \$O(N^2)\$ but it doesn't seem that \$O(N^2)\$ is correct because it takes 6-9 steps in the while loop for a list of 4 integers and \$4^2\$ is 8. ~1975 steps for 80 entries. I think that should be original. Do you have any tips and improvements for me?# -*- coding: utf-8 -*-Created on Nov 25 20:02:33 2016Shakesort Algorithm@author: fryeimport randomdef shakesort(workList):    listLength = len(workList)    listIndexDecr = listLength - 1    listIndexIncr = 0    xChanged = True    step = 0    if(listLength <= 1):        return workList, 1    # This will loop n times throught the whole list till the    # list got looped without a change of number or sort    while (True):        step = step + 1 # For counting purpose        # Init a new loop        if(listIndexDecr <= 0):            listIndexIncr = 0            listIndexDecr = listLength - 1            # Stop if the last loop had no sort!            if(xChanged == False):                break            # Set it False again            xChanged = False        # Walk Forward        if(workList[listIndexIncr] > workList[listIndexIncr+1]):            tvar = workList[listIndexIncr+1]             workList[listIndexIncr+1] = workList[listIndexIncr]            workList[listIndexIncr] = tvar            xChanged = True        listIndexIncr = listIndexIncr + 1        # Walk back        if(workList[listIndexDecr-1] > workList[listIndexDecr]):            tvar = workList[listIndexDecr-1]            workList[listIndexDecr-1] = workList[listIndexDecr]            workList[listIndexDecr] = tvar            xChanged = True        listIndexDecr = listIndexDecr - 1     # Return sorted list and stats    return workList, step#myList = [21,2,43,4,4,2,4,7,87,65,0,0,0,4,3,2,1212,21,212,32,433]myList = random.sample(range(32), 4)print(> +str(myList))myNewList,x = shakesort(myList)print(<  + str(myNewList))print(Finished in +str(x-1)+ steps! List length was: +str(len(myList)))
Shakesort in Python 3
python;algorithm;sorting