onlyforbopi
12/21/2016 - 7:07 AM

## Python.Algorithms.Sorting

PYTHON SORTING

``````
Functions that sort lists:
1.  Bogosort              = Sorts with BogoSort method
2.  Bubblesort            = Sorts with BubbleSort method
3.  Cocktailsort          = Sorts with Cocktailsort method
4.  Combsort              = Sorts with CombSort method
5.  Cyclesort             = Sorts with CycleSort method
6.  Gnomesort             = Sorts with GnomeSort method
7.  Insertionsort         = Sorts with InsertionSort method
8.  Mergesort             = Sorts with MergeSort method
9.  Quicksort             = Sorts with QuickSort method
10. Selectionsort         = Sorts with SelectionSort method
11. Shellsort             = Sorts with ShellSort method
12. Stoogesort            = Sorts with StoogeSort method
13. Strandsort            = Sorts with StrandSort method
14. Swapsort              = Sorts with Swapsort method
14. In_order_Ascending    = Checks if list is in ascending order
15. In_order_Descending   = Checks if list is in descending order
16. TextFileSortSubstr    = Sorts a file (normal/reverse by substring)``````
``````data = [1, 4, 5, 3, -6, 3, -3, 7]

def stoogesort(L, i=0, j=None):
'''
Function: stoogesort
Description: Sorts a list
Input: List
Output: Sorted List
Usage: stoogesort(a)
Notes: Edits in place
Notes2: Sorts in ascending order
'''
if j is None:
j = len(L) - 1
if L[j] < L[i]:
L[i], L[j] = L[j], L[i]
if j - i > 1:
t = (j - i + 1) // 3
stoogesort(L, i  , j-t)
stoogesort(L, i+t, j  )
stoogesort(L, i  , j-t)
return L

print (stoogesort(data))

############################################
# DESCENDING

data = [1, 4, 5, 3, -6, 3, -3, 7]

def stoogesort(L, i=0, j=None):
'''
Function: stoogesort
Description: Sorts a list
Input: List
Output: Sorted List
Usage: stoogesort(a)
Notes: Edits in place
Notes2: Sorts in descending order
'''
if j is None:
j = len(L) - 1
if L[j] > L[i]:
L[i], L[j] = L[j], L[i]
if j - i > 1:
t = (j - i + 1) // 3
stoogesort(L, i  , j-t)
stoogesort(L, i+t, j  )
stoogesort(L, i  , j-t)
return L

print (stoogesort(data))``````
``````def shellSort(alist):
'''
Function: shellsort
Description: Sorts a list
Input: List
Output: Sorted List
Called as(print): print (shellsort(alist))
Called as(assign): b = shellsort(alist)
'''

sublistcount = len(alist)//2
while sublistcount > 0:

for startposition in range(sublistcount):
gapInsertionSort(alist,startposition,sublistcount)

print("After increments of size",sublistcount,
"The list is",alist)

sublistcount = sublistcount // 2

def gapInsertionSort(alist,start,gap):
for i in range(start+gap,len(alist),gap):

currentvalue = alist[i]
position = i

while position>=gap and alist[position-gap]>currentvalue:
alist[position]=alist[position-gap]
position = position-gap

alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]
shellSort(alist)
print(alist)

########################################################
# DESCENDING

def shellSort(alist):
'''
Function: shellsort
Description: Sorts a list
Input: List
Output: Sorted List
Called as(print): print (shellsort(alist))
Called as(assign): b = shellsort(alist)
'''
def gapInsertionSort(alist,start,gap):
for i in range(start+gap,len(alist),gap):

currentvalue = alist[i]
position = i

while position>=gap and alist[position-gap]<currentvalue:
alist[position]=alist[position-gap]
position = position-gap

alist[position]=currentvalue

sublistcount = len(alist)//2
while sublistcount > 0:

for startposition in range(sublistcount):
gapInsertionSort(alist,startposition,sublistcount)

print("After increments of size",sublistcount,
"The list is",alist)

sublistcount = sublistcount // 2

alist = [54,26,93,17,77,31,44,55,20]
shellSort(alist)
print(alist)``````
``````def selectionsort(alist):
'''
Function: selectionsort
Description: Sorts a list
Input: List
Output: Sorted List
Called as(print): print (selectionsort(alist))
Called as(assign): b = selectionsort(alist)
'''
for fillslot in range(len(alist)-1,0,-1):
positionOfMax=0
for location in range(1,fillslot+1):
if alist[location]>alist[positionOfMax]:
positionOfMax = location

temp = alist[fillslot]
alist[fillslot] = alist[positionOfMax]
alist[positionOfMax] = temp

alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)``````
``````def mergeSort(alist):
'''
Function: mergeSort
Description: Sorts a list
Input: List
Output: Sorted List
Usage: mergeSort(a)
Notes: Edits in place
Notes2: Sorts in ascending order
'''
print("Splitting ",alist)
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]

mergeSort(lefthalf)
mergeSort(righthalf)

i=0
j=0
k=0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1

while i < len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1

while j < len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

#######################################################
# DESCENDING

def mergeSort(alist):
'''
Function: mergeSort
Description: Sorts a list
Input: List
Output: Sorted List
Usage: mergeSort(a)
Notes: Edits in place
Notes2: Sorts in descending order
'''
print("Splitting ",alist)
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]

mergeSort(lefthalf)
mergeSort(righthalf)

i=0
j=0
k=0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] > righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1

while i < len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1

while j < len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)``````
``````def insertionSort(alist):
'''
Function: insertionSort
Description: Sorts a list
Input: List
Output: Sorted List
Usage: insertionSort(a)
Notes: Edits in place
Notes2: Sorts in ascending order
'''
for index in range(1,len(alist)):

currentvalue = alist[index]
position = index

while position>0 and alist[position-1]>currentvalue:
alist[position]=alist[position-1]
position = position-1

alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print(alist)

#######################################################
# DESCENDING

def insertionSort(alist):
'''
Function: insertionSort
Description: Sorts a list
Input: List
Output: Sorted List
Usage: insertionSort(a)
Notes: Edits in place
Notes2: Sorts in descending order
'''
for index in range(1,len(alist)):

currentvalue = alist[index]
position = index

while position>0 and alist[position-1]<currentvalue:
alist[position]=alist[position-1]
position = position-1

alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print(alist)

``````
``````def in_order_desc(l):
'''
Function: in_order_desc
Description: Checks if a list is in descending order
Input: List
Output: T / F
Usage: in_order_desc(a)
'''
if not l:
return True
last = l[0]
for x in l[1:]:
if x > last:
return False
last = x
return True

a = [ 7,6,5,4,3,2,1]

print (in_order_asc(a))``````
``````def gnomesort(a):
'''
Function: gnomesort
Description: Sorts a list
Input: List
Output: Sorted List
Usage: gnomesort(a)
Notes: Edits in place
Notes2: Sorts in ascending order
'''
i,j,size = 1,2,len(a)
while i < size:
if a[i-1] <= a[i]:
i,j = j, j+1
else:
a[i-1],a[i] = a[i],a[i-1]
i -= 1
if i == 0:
i,j = j, j+1
return a

print (gnomesort([3,4,2,5,1,6]))

###################################################
# Descending Order

def gnomesort(a):
'''
Function: gnomesort
Description: Sorts a list
Input: List
Output: Sorted List
Usage: gnomesort(a)
Notes: Edits in place
Notes2: Sorts in descending order
'''
i,j,size = 1,2,len(a)
while i < size:
if a[i-1] >= a[i]:
i,j = j, j+1
else:
a[i-1],a[i] = a[i],a[i-1]
i -= 1
if i == 0:
i,j = j, j+1
return a

print (gnomesort([3,4,2,5,1,6]))

``````
``````def cycleSort(vector):
'''
Function: cycleSort
Description: Sorts a list
Input: List
Output: Sorted List
Usage: cycleSort(a)
Notes: Edits in place
Notes2: Sorts in ascending order
'''
writes = 0

# Loop through the vector to find cycles to rotate.
for cycleStart, item in enumerate(vector):

# Find where to put the item.
pos = cycleStart
for item2 in vector[cycleStart + 1:]:
if item2 < item:
pos += 1

# If the item is already there, this is not a cycle.
if pos == cycleStart:
continue

# Otherwise, put the item there or right after any duplicates.
while item == vector[pos]:
pos += 1
vector[pos], item = item, vector[pos]
writes += 1

# Rotate the rest of the cycle.
while pos != cycleStart:

# Find where to put the item.
pos = cycleStart
for item2 in vector[cycleStart + 1:]:
if item2 < item:
pos += 1

# Put the item there or right after any duplicates.
while item == vector[pos]:
pos += 1
vector[pos], item = item, vector[pos]
writes += 1

return writes

if __name__ == '__main__':
x = [0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]
xcopy = x[::]
writes = cycleSort(xcopy)
if xcopy != sorted(x):
print('Wrong order!')
else:
print('%r\nIs correctly sorted using cycleSort to'
'\n%r\nUsing %i writes.' % (x, xcopy, writes))

#################################################
# DESCENDING

def cycleSort(vector):
'''
Function: cycleSort
Description: Sorts a list
Input: List
Output: Sorted List
Usage: cycleSort(a)
Notes: Edits in place
Notes2: Sorts in descending order
'''
writes = 0

# Loop through the vector to find cycles to rotate.
for cycleStart, item in enumerate(vector):

# Find where to put the item.
pos = cycleStart
for item2 in vector[cycleStart + 1:]:
if item2 > item:
pos += 1

# If the item is already there, this is not a cycle.
if pos == cycleStart:
continue

# Otherwise, put the item there or right after any duplicates.
while item == vector[pos]:
pos += 1
vector[pos], item = item, vector[pos]
writes += 1

# Rotate the rest of the cycle.
while pos != cycleStart:

# Find where to put the item.
pos = cycleStart
for item2 in vector[cycleStart + 1:]:
if item2 > item:
pos += 1

# Put the item there or right after any duplicates.
while item == vector[pos]:
pos += 1
vector[pos], item = item, vector[pos]
writes += 1

return writes

a = [ 1, 2, 3, 4, 3, 2, 2, 7, 6 ]
cycleSort(a)
print (a)
``````
``````def combsort(input):
'''
Function: combort
Description: Sorts a list
Input: List
Output: Sorted List
Usage: combsort(a)
Notes: Edits in place
Notes2: Sorts in ascending order
'''
gap = len(input)
swaps = True
while gap > 1 or swaps:
gap = max(1, int(gap / 1.25))  # minimum gap is 1
swaps = False
for i in range(len(input) - gap):
j = i+gap
if input[i] > input[j]:
input[i], input[j] = input[j], input[i]
swaps = True

y = [88, 18, 31, 44, 4, 0, 8, 81, 14, 78, 20, 76, 84, 33, 73, 75, 82, 5, 62, 70]
combsort(y)
print (y)

#######################################################
# DESCENDING

def combsort(input):
'''
Function: combort
Description: Sorts a list
Input: List
Output: Sorted List
Usage: combsort(a)
Notes: Edits in place
Notes2: Sorts in descending order
'''
gap = len(input)
swaps = True
while gap > 1 or swaps:
gap = max(1, int(gap / 1.25))  # minimum gap is 1
swaps = False
for i in range(len(input) - gap):
j = i+gap
if input[i] < input[j]:
input[i], input[j] = input[j], input[i]
swaps = True

y = [88, 18, 31, 44, 4, 0, 8, 81, 14, 78, 20, 76, 84, 33, 73, 75, 82, 5, 62, 70]
combsort(y)
print (y)``````
``````def cocktailSort(A):
'''
Function: cocktailSort
Description: Sorts a list
Input: List
Output: Sorted List
Usage: cocktailSort(a)
Notes: Edits in place
Notes2: Sorts in ascending order
'''
up = range(len(A)-1)
while True:
for indices in (up, reversed(up)):
swapped = False
for i in indices:
if A[i] > A[i+1]:
A[i], A[i+1] =  A[i+1], A[i]
swapped = True
if not swapped:
return

test1 = [7, 6, 5, 9, 40, 4, 3, 1, 2, 0]
cocktailSort(test1)
print (test1)

########################################################
# Descending

def cocktailSort(A):
'''
Function: cocktailSort
Description: Sorts a list
Input: List
Output: Sorted List
Usage: cocktailSort(a)
Notes: Edits in place
Notes2: Sorts in descending order
'''
up = range(len(A)-1)
while True:
for indices in (up, reversed(up)):
swapped = False
for i in indices:
if A[i] < A[i+1]:
A[i], A[i+1] =  A[i+1], A[i]
swapped = True
if not swapped:
return

test1 = [7, 6, 5, 9, 40, 4, 3, 1, 2, 0]
cocktailSort(test1)
print (test1)

``````
``````def bubblesort(alist):
'''
Function: bubblesort
Description: Sorts a list
Input: List
Output: Sorted List
Called as(print): print(bubblesort(a))
Called as(assign): b = bubblesort(a)
Notes : Converts original List
'''
for passnum in range(len(alist)-1,0,-1):
for i in range(passnum):
if alist[i]>alist[i+1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp

alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)

##############################################
# Descending

def bubblesort(alist):
'''
Function: bubblesort
Description: Sorts a list
Input: List
Output: Sorted List
Called as(print): print(bubblesort(a))
Called as(assign): b = bubblesort(a)
Notes : Converts original List
'''
for passnum in range(len(alist)-1,0,-1):
for i in range(passnum):
if alist[i]<alist[i+1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp

alist = [54,26,93,17,77,31,44,55,20]
bubblesort(alist)
print(alist)

``````
``````def bogosort(l):
'''
Function: bogosort
Description: Sorts a list (Ascending)
Input: List
Output: Sorted List
Usage: bogosort(List)
Notes: Edits in place
Notes2: Change to descending, change in order function
'''

def in_order(l):
if not l:
return True
last = l[0]
for x in l[1:]:
if x < last:
return False
last = x
return True

import random
while not in_order(l):
random.shuffle(l)
return l

l = [3,2,1,5,4]
bogosort(l)
print (l)

##########################################
# Descending Version

def bogosort(l):
'''
Function: bogosort
Description: Sorts a list (Ascending)
Input: List
Output: Sorted List
Usage: bogosort(List)
Notes: Edits in place
Notes2: Change to descending, change in order function
'''

def in_order(l):
if not l:
return True
last = l[0]
for x in l[1:]:
if x > last:
return False
last = x
return True

import random
while not in_order(l):
random.shuffle(l)
return l

l = [3,2,5,4]
bogosort(l)
print (l)``````
``````def swapSort(L):
""" L is a list on integers """
print("Original L: ", L)
for i in range(len(L)):
for j in range(i+1, len(L)):
if L[j] < L[i]:
# the next line is a short
# form for swap L[i] and L[j]
L[j], L[i] = L[i], L[j]
print(L)
print("Final L: ", L)``````
``````
def strand_sort(a):
'''
Function: strand_sort
Description: Sorts a list
Input: List
Output: Sorted List
Usage: strand_sort(a)
Notes: Edits in place
Notes2: Sorts in ascending order
'''
def merge_list(a, b):
out = []
while len(a) and len(b):
if a[0] < b[0]:
out.append(a.pop(0))
else:
out.append(b.pop(0))
out += a
out += b
return out

def strand(a):
i, s = 0, [a.pop(0)]
while i < len(a):
if a[i] > s[-1]:
s.append(a.pop(i))
else:
i += 1
return s

out = strand(a)
while len(a):
out = merge_list(out, strand(a))

return out

print (strand_sort([1, 6, 3, 2, 1, 7, 5, 3]))

#######################################################
# DESCENDING

def strand_sort(a):
'''
Function: strand_sort
Description: Sorts a list
Input: List
Output: Sorted List
Usage: strand_sort(a)
Notes: Edits in place
Notes2: Sorts in descending order
'''

def merge_list(a, b):
out = []
while len(a) and len(b):
if a[0] > b[0]:
out.append(a.pop(0))
else:
out.append(b.pop(0))
out += a
out += b
return out

def strand(a):
i, s = 0, [a.pop(0)]
while i < len(a):
if a[i] < s[-1]:
s.append(a.pop(i))
else:
i += 1
return s

out = strand(a)
while len(a):
out = merge_list(out, strand(a))

return out

print (strand_sort([1, 6, 3, 2, 1, 7, 5, 3]))``````
``````def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
if first<last:

splitpoint = partition(alist,first,last)

quickSortHelper(alist,first,splitpoint-1)
quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last):
pivotvalue = alist[first]

leftmark = first+1
rightmark = last

done = False
while not done:

while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1

while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
rightmark = rightmark -1

if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp

temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp

return rightmark

alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)

############################################################
# ONE FUNCTION FORM

def quickSort(alist):
'''
Function: quickSort
Description: Sorts a list
Input: List
Output: Sorted List
Usage: quickSort(a)
Notes: Edits in place
Notes2: Sorts in descending order
'''

def quickSortHelper(alist,first,last):
if first<last:

splitpoint = partition(alist,first,last)

quickSortHelper(alist,first,splitpoint-1)
quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last):
pivotvalue = alist[first]

leftmark = first+1
rightmark = last

done = False
while not done:

while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1

while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
rightmark = rightmark -1

if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp

temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp

return rightmark

quickSortHelper(alist,0,len(alist)-1)

alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)

``````
``````def in_order_asc(l):
'''
Function: in_order_desc
Description: Checks if a list is in ascending order
Input: List
Output: T / F
Usage: in_order_desc(a)
'''
if not l:
return True
last = l[0]
for x in l[1:]:
if x < last:
return False
last = x
return True

a = [ 7,6,5,4,3,2,1]

print (in_order_asc(a))``````
``````

import os
import sys

file_in = sys.argv[1]
sub_start = int(sys.argv[2])
sub_len = int(sys.argv[3])
reverse_in = sys.argv[4]

file_ot = str(file_in) + ".srt"
file_list = []
outfile = open(file_ot, 'w')

if reverse_in == '-n':
reverse_in = False
elif reverse_in == '-r':
reverse_in = True
else:
print("wrong")

# We provide with n++ notation
real_start = sub_start - 1
real_end = real_start + sub_len

with open(file_in, 'r') as f:
for line in f:
file_list.append(line)

file_list.sort(key = lambda x: x[real_start:real_end], reverse=reverse_in)

for j in file_list:
outfile.write(j)

outfile.close()

#################################################################

@timing_val
def main_work(file_in, sub_start, sub_length, reverse_in):

file_ot = str(file_in) + ".srt"
file_list = []
outfile = open(file_ot, 'w')

if reverse_in == '-n':
reverse_in = False
elif reverse_in == '-r':
reverse_in = True
else:
print("wrong")

real_start = sub_start - 1
real_end = real_start + sub_length

with open(file_in, 'r') as f:
for line in f:
file_list.append(line)

file_list.sort(key = lambda x: x[real_start:real_end], reverse=reverse_in)

for j in file_list:
outfile.write(j)

outfile.close()

return True``````