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