Problem scenario
You want to use recursion in Python in a sorting algorithm. How do you do this?
Solution
Save this program as contintsort.py and run it python contintsort.py. The code closer to the top is in Python 2, and the code closer to the bottom is in Python 3.
# Written by www.continualintegration.com
# Usage is self-explanatory. Just run the program. python contintsort.py
# No extra files are needed.
# This demonstrates a sorting algorithm. It runs in O(n^2) time in worst case scenarios.
# It runs in O(n) time in best case scenarios (when the data is already sorted).
# It accepts user input as long as the input is an integer.
import random, re # We need random to generate random integers. We need re to do "regular expressions"
# Regular expressions are methods of searching one pattern of text with another.
print "If you just press enter with the prompts below, you will get random integers assigned."
print "Enter an integer or press enter to get one assigned at random."
print " "
first = raw_input("Enter the first number: ")
second = raw_input("Enter the second number: ")
third = raw_input("Enter the third number: ")
fourth = raw_input("Enter the fourth number: ")
fifth = raw_input("Enter the fifth number: ")
sixth = raw_input("Enter the sixth number: ")
seventh = raw_input("Enter the seventh number: ")
eighth = raw_input("Enter the eighth number: ")
ninth = raw_input("Enter the ninth number: ")
tenth = raw_input("Enter the tenth number: ")
coolList = [first, second, third, fourth, fifth, sixth, seventh, eighth, ninth, tenth]
for i in range(10):
if coolList[i] == "":
coolList[i] = random.randint(1,1001) # Assign if a blank was entered
else:
b = coolList[i] # Assign input to a variable.
a = (re.search('[a-zA-Z]', b)) # Check for non-numerical characters that were inputted.
if a: coolList[i] = random.randint(1,1001) # Assign random int if alphabet chars were entered
else: coolList[i] = int(coolList[i]) # make input an integer (cast input to be an integer)
def swapper(counter, interListb, flag): # Define a function that requires three parameters when called.
if (flag == 'exitnow'):
print "************************************" # This function will end if the flag was set to exit.
else:
x = interListb[(counter)]
y = interListb[(counter + 1)]
if (y < x): # swap and then verify previous pair in list is ordered after swap
interListb[(counter + 1)] = x
interListb[(counter)] = y
counter = counter -1 # Now that there was a swap, let's see of the pair to the left of swapped number is in order.
if (counter < 1):
counter = 0 # Do not go outside the index. Go to the left-most item in the list.
swapper(counter, interListb, flag) # Make recursive calls to check adjacent pairs in the list moving to the left.
else: # do not swap. do move to the right in the list to continue checking pairs.
var1 = (len(interListb) - 2) # Counter will be incremented later. Lists are 0 based. Length counts the 0th (first) item.
if counter >= var1: # The right-most item was reached. Set a flag to exit the recursive calling of swapper.
flag = 'exitnow' # Exit recursion with the next call.
counter = counter + 1
swapper(counter, interListb, flag) # Make recursive calls to check adjacent pairs in the list moving to the right.
return interListb # Return the list outside of the recursion. In Python you do not return something inside a recursive call.
qq = swapper(0, coolList, 'enter') # This invokes swapper for the first time.
print qqHere is the program in Python 3:
# Written by www.continualintegration.com
# Usage is self-explanatory. Just run the program. python contintsort.py
# No extra files are needed.
# This demonstrates a sorting algorithm. It runs in O(n^2) time in worst case scenarios.
# It runs in O(n) time in best case scenarios (when the data is already sorted).
# It accepts user input as long as the input is an integer.
import random, re # We need random to generate random integers. We need re to do "regular expressions"
# Regular expressions are methods of searching one pattern of text with another.
print("If you just press enter with the prompts below, you will get random integers assigned.")
print("Enter an integer or press enter to get one assigned at random.")
print(" ")
first = input("Enter the first number: ")
second = input("Enter the second number: ")
third = input("Enter the third number: ")
fourth = input("Enter the fourth number: ")
fifth = input("Enter the fifth number: ")
sixth = input("Enter the sixth number: ")
seventh = input("Enter the seventh number: ")
eighth = input("Enter the eighth number: ")
ninth = input("Enter the ninth number: ")
tenth = input("Enter the tenth number: ")
pre_list = [first, second, third, fourth, fifth, sixth, seventh, eighth, ninth, tenth]
for i in range(10):
if pre_list[i] == "":
pre_list[i] = random.randint(1,1001) # Assign if a blank was entered
else:
b = pre_list[i] # Assign input to a variable.
a = (re.search('[a-zA-Z]', b)) # Check for non-numerical characters that were inputted.
if a: pre_list[i] = random.randint(1,1001) # Assign random int if alphabet chars were entered
else: pre_list[i] = int(pre_list[i]) # make input an integer (cast input to be an integer)
def swapper(counter, intermediate_list, flag): # Define a function that requires three parameters when called.
if (flag == 'exitnow'):
print("************************************") # This function will end if the flag was set to exit.
else:
x = intermediate_list[(counter)]
y = intermediate_list[(counter + 1)]
if (y < x): # swap and then verify previous pair in list is ordered after swap
intermediate_list[(counter + 1)] = x
intermediate_list[(counter)] = y
counter = counter -1 # Now that there was a swap, let's see of the pair to the left of swapped number is in order.
if (counter < 1):
counter = 0 # Do not go outside the index. Go to the left-most item in the list.
swapper(counter, intermediate_list, flag) # Make recursive calls to check adjacent pairs in the list moving to the left.
else: # do not swap. do move to the right in the list to continue checking pairs.
var1 = (len(intermediate_list) - 2) # Counter will be incremented later. Lists are 0 based. Length counts the 0th (first) item.
if counter >= var1: # The right-most item was reached. Set a flag to exit the recursive calling of swapper.
flag = 'exitnow' # Exit recursion with the next call.
counter = counter + 1
swapper(counter, intermediate_list, flag) # Make recursive calls to check adjacent pairs in the list moving to the right.
return intermediate_list # Return the list outside of the recursion. In Python you do not return something inside a recursive call.
sorted_list = swapper(0, pre_list, 'enter') # This invokes swapper for the first time.
print(sorted_list)