Shakesort in Python 3

Question

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 2016 Shakesort Algorithm @author: frye """ import random def 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))) 

Answer 1

Here are some minor coding style suggestions.

Layout

In a simple if condition like this:

if(listLength <= 1): 

the parentheses are usually omitted:

if listLength <= 1: 

The black program can be used to automatically reformat the code to remove them.

Also, comparison to False:

if(xChanged == False): 

is usually written as:

if not xChanged: 

Move the check of listLength right after you set the variable:

def shakesort(workList): listLength = len(workList) if listLength <= 1: return workList, 1 

This results in a quicker exit from the function.

Simpler

Lines like this:

step = step + 1 # For counting purpose 

are simpler using the special assignment operators:

step += 1 

In this case, the comment is not needed since it is obvious it is a counter.

Documentation

The PEP 8 style guide recommends adding docstrings for functions. You should summarize its purpose as well as describe the input and return types.

Naming

PEP 8 recommends snake_case for function and variable names. For example:

def shakesort(workList): 

would be:

def shake_sort(work_list): 

tvar is not a descriptive name.

Typo

"throught" should be "through":

# This will loop n times throught the whole list till the