tra-analysis/analysis-master/tra_analysis/Sort.py

424 lines
7.0 KiB
Python
Raw Permalink Normal View History

tra-analysis v 3.0.0 aggregate PR (#73) * reflected doc changes to README.md Signed-off-by: Arthur Lu <learthurgo@gmail.com> * tra_analysis v 2.1.0-alpha.1 Signed-off-by: Arthur Lu <learthurgo@gmail.com> * changed setup.py to use __version__ from source added Topic and keywords Signed-off-by: Arthur Lu <learthurgo@gmail.com> * updated Supported Platforms in README.md Signed-off-by: Arthur Lu <learthurgo@gmail.com> * moved required files back to parent Signed-off-by: Arthur Lu <learthurgo@gmail.com> * moved security back to parent Signed-off-by: Arthur Lu <learthurgo@gmail.com> * moved security back to parent moved contributing back to parent Signed-off-by: Arthur Lu <learthurgo@gmail.com> * add PR template Signed-off-by: Arthur Lu <learthurgo@gmail.com> * moved to parent folder Signed-off-by: Arthur Lu <learthurgo@gmail.com> * moved meta files to .github folder Signed-off-by: Arthur Lu <learthurgo@gmail.com> * Analysis.py v 3.0.1 Signed-off-by: Arthur Lu <learthurgo@gmail.com> * updated test_analysis for submodules, and added missing numpy import in Sort.py * fixed item one of Issue #58 Signed-off-by: Arthur Lu <learthurgo@gmail.com> * readded cache searching in postCreateCommand Signed-off-by: Arthur Lu <learthurgo@gmail.com> * added myself as an author * feat: created kivy gui boilerplate * added Kivy to requirements.txt Signed-off-by: Arthur Lu <learthurgo@gmail.com> * feat: gui with placeholders * fix: changed config.json path * migrated docker base image to debian Signed-off-by: ltcptgeneral <learthurgo@gmail.com> * style: spaces to tabs * migrated to ubuntu Signed-off-by: ltcptgeneral <learthurgo@gmail.com> * fixed issues Signed-off-by: ltcptgeneral <learthurgo@gmail.com> * fix: docker build? * fix: use ubuntu bionic * fix: get kivy installed * @ltcptgeneral can't spell * optim dockerfile for not installing unused packages * install basic stuff while building the container * use prebuilt image for development * install pylint on base image * rename and use new kivy * tests: added tests for Array and CorrelationTest Both are not working due to errors * use new thing * use 20.04 base * symlink pip3 to pip * use pip instead of pip3 * equation.Expression.py v 0.0.1-alpha added corresponding .pyc to .gitignore * parser.py v 0.0.2-alpha * added pyparsing to requirements.txt * parser v 0.0.4-alpha * Equation v 0.0.1-alpha * added Equation to tra_analysis imports * tests: New unit tests for submoduling (#66) * feat: created kivy gui boilerplate * migrated docker base image to debian Signed-off-by: ltcptgeneral <learthurgo@gmail.com> * migrated to ubuntu Signed-off-by: ltcptgeneral <learthurgo@gmail.com> * fixed issues Signed-off-by: ltcptgeneral <learthurgo@gmail.com> * fix: docker build? * fix: use ubuntu bionic * fix: get kivy installed * @ltcptgeneral can't spell * optim dockerfile for not installing unused packages * install basic stuff while building the container * use prebuilt image for development * install pylint on base image * rename and use new kivy * tests: added tests for Array and CorrelationTest Both are not working due to errors * fix: Array no longer has *args and CorrelationTest functions no longer have self in the arguments * use new thing * use 20.04 base * symlink pip3 to pip * use pip instead of pip3 * tra_analysis v 2.1.0-alpha.2 SVM v 1.0.1 added unvalidated SVM unit tests Signed-off-by: ltcptgeneral <learthurgo@gmail.com> * fixed version number Signed-off-by: ltcptgeneral <learthurgo@gmail.com> * tests: added tests for ClassificationMetric * partially fixed and commented out svm unit tests * fixed some SVM unit tests * added installing pytest to devcontainer.json * fix: small fixes to KNN Namely, removing self from parameters and passing correct arguments to KNeighborsClassifier constructor * fix, test: Added tests for KNN and NaiveBayes. Also made some small fixes in KNN, NaiveBayes, and RegressionMetric * test: finished unit tests except for StatisticalTest Also made various small fixes and style changes * StatisticalTest v 1.0.1 * fixed RegressionMetric unit test temporarily disabled CorrelationTest unit tests * tra_analysis v 2.1.0-alpha.3 * readded __all__ * fix: floating point issues in unit tests for CorrelationTest Co-authored-by: AGawde05 <agawde05@gmail.com> Co-authored-by: ltcptgeneral <learthurgo@gmail.com> Co-authored-by: Dev Singh <dev@devksingh.com> Co-authored-by: jzpan1 <panzhenyu2014@gmail.com> * fixed depreciated escape sequences * ficed tests, indent, import in test_analysis * changed version to 3.0.0 added backwards compatibility * ficed pytest install in container * removed GUI changes Signed-off-by: Arthur Lu <learthurgo@gmail.com> * incremented version to rc.1 (release candidate 1) Signed-off-by: Arthur Lu <learthurgo@gmail.com> * fixed NaiveBayes __changelog__ Signed-off-by: Arthur Lu <learthurgo@gmail.com> * fix: __setitem__ == to single = * Array v 1.0.1 * Revert "Array v 1.0.1" This reverts commit 59783b79f7451586bc9741794589e00f0c625348. * Array v 1.0.1 * Array.py v 1.0.2 added more Array unit tests * cleaned .gitignore tra_analysis v 3.0.0-rc2 Signed-off-by: Arthur Lu <learthurgo@gmail.com> * added *.pyc to gitignore finished subdividing test_analysis * feat: gui layout + basic func * Froze and removed superscript (data-analysis) * remove data-analysis deps install for devcontainer * tukey pairwise comparison and multicomparison but no critical q-values * quick patch for devcontainer.json * better fix for devcontainer.json * fixed some styling in StatisticalTest removed print statement in StatisticalTest unit tests * update analysis tests to be more effecient * don't use loop for test_nativebayes * removed useless secondary docker files * tra-analysis v 3.0.0 Co-authored-by: James Pan <panzhenyu2014@gmail.com> Co-authored-by: AGawde05 <agawde05@gmail.com> Co-authored-by: zpan1 <72054510+zpan1@users.noreply.github.com> Co-authored-by: Dev Singh <dev@devksingh.com> Co-authored-by: = <=> Co-authored-by: Dev Singh <dsingh@imsa.edu> Co-authored-by: zpan1 <zpan@imsa.edu>
2021-04-29 00:33:50 +00:00
# Titan Robotics Team 2022: Sort submodule
# Written by Arthur Lu and James Pan
# Notes:
# this should be imported as a python module using 'from tra_analysis import Sort'
# setup:
__version__ = "1.0.1"
__changelog__ = """changelog:
1.0.1:
- fixed __all__
1.0.0:
- ported analysis.Sort() here
- removed classness
"""
__author__ = (
"Arthur Lu <learthurgo@gmail.com>",
"James Pan <zpan@imsa.edu>",
tra-analysis v 3.0.0 aggregate PR (#73) * reflected doc changes to README.md Signed-off-by: Arthur Lu <learthurgo@gmail.com> * tra_analysis v 2.1.0-alpha.1 Signed-off-by: Arthur Lu <learthurgo@gmail.com> * changed setup.py to use __version__ from source added Topic and keywords Signed-off-by: Arthur Lu <learthurgo@gmail.com> * updated Supported Platforms in README.md Signed-off-by: Arthur Lu <learthurgo@gmail.com> * moved required files back to parent Signed-off-by: Arthur Lu <learthurgo@gmail.com> * moved security back to parent Signed-off-by: Arthur Lu <learthurgo@gmail.com> * moved security back to parent moved contributing back to parent Signed-off-by: Arthur Lu <learthurgo@gmail.com> * add PR template Signed-off-by: Arthur Lu <learthurgo@gmail.com> * moved to parent folder Signed-off-by: Arthur Lu <learthurgo@gmail.com> * moved meta files to .github folder Signed-off-by: Arthur Lu <learthurgo@gmail.com> * Analysis.py v 3.0.1 Signed-off-by: Arthur Lu <learthurgo@gmail.com> * updated test_analysis for submodules, and added missing numpy import in Sort.py * fixed item one of Issue #58 Signed-off-by: Arthur Lu <learthurgo@gmail.com> * readded cache searching in postCreateCommand Signed-off-by: Arthur Lu <learthurgo@gmail.com> * added myself as an author * feat: created kivy gui boilerplate * added Kivy to requirements.txt Signed-off-by: Arthur Lu <learthurgo@gmail.com> * feat: gui with placeholders * fix: changed config.json path * migrated docker base image to debian Signed-off-by: ltcptgeneral <learthurgo@gmail.com> * style: spaces to tabs * migrated to ubuntu Signed-off-by: ltcptgeneral <learthurgo@gmail.com> * fixed issues Signed-off-by: ltcptgeneral <learthurgo@gmail.com> * fix: docker build? * fix: use ubuntu bionic * fix: get kivy installed * @ltcptgeneral can't spell * optim dockerfile for not installing unused packages * install basic stuff while building the container * use prebuilt image for development * install pylint on base image * rename and use new kivy * tests: added tests for Array and CorrelationTest Both are not working due to errors * use new thing * use 20.04 base * symlink pip3 to pip * use pip instead of pip3 * equation.Expression.py v 0.0.1-alpha added corresponding .pyc to .gitignore * parser.py v 0.0.2-alpha * added pyparsing to requirements.txt * parser v 0.0.4-alpha * Equation v 0.0.1-alpha * added Equation to tra_analysis imports * tests: New unit tests for submoduling (#66) * feat: created kivy gui boilerplate * migrated docker base image to debian Signed-off-by: ltcptgeneral <learthurgo@gmail.com> * migrated to ubuntu Signed-off-by: ltcptgeneral <learthurgo@gmail.com> * fixed issues Signed-off-by: ltcptgeneral <learthurgo@gmail.com> * fix: docker build? * fix: use ubuntu bionic * fix: get kivy installed * @ltcptgeneral can't spell * optim dockerfile for not installing unused packages * install basic stuff while building the container * use prebuilt image for development * install pylint on base image * rename and use new kivy * tests: added tests for Array and CorrelationTest Both are not working due to errors * fix: Array no longer has *args and CorrelationTest functions no longer have self in the arguments * use new thing * use 20.04 base * symlink pip3 to pip * use pip instead of pip3 * tra_analysis v 2.1.0-alpha.2 SVM v 1.0.1 added unvalidated SVM unit tests Signed-off-by: ltcptgeneral <learthurgo@gmail.com> * fixed version number Signed-off-by: ltcptgeneral <learthurgo@gmail.com> * tests: added tests for ClassificationMetric * partially fixed and commented out svm unit tests * fixed some SVM unit tests * added installing pytest to devcontainer.json * fix: small fixes to KNN Namely, removing self from parameters and passing correct arguments to KNeighborsClassifier constructor * fix, test: Added tests for KNN and NaiveBayes. Also made some small fixes in KNN, NaiveBayes, and RegressionMetric * test: finished unit tests except for StatisticalTest Also made various small fixes and style changes * StatisticalTest v 1.0.1 * fixed RegressionMetric unit test temporarily disabled CorrelationTest unit tests * tra_analysis v 2.1.0-alpha.3 * readded __all__ * fix: floating point issues in unit tests for CorrelationTest Co-authored-by: AGawde05 <agawde05@gmail.com> Co-authored-by: ltcptgeneral <learthurgo@gmail.com> Co-authored-by: Dev Singh <dev@devksingh.com> Co-authored-by: jzpan1 <panzhenyu2014@gmail.com> * fixed depreciated escape sequences * ficed tests, indent, import in test_analysis * changed version to 3.0.0 added backwards compatibility * ficed pytest install in container * removed GUI changes Signed-off-by: Arthur Lu <learthurgo@gmail.com> * incremented version to rc.1 (release candidate 1) Signed-off-by: Arthur Lu <learthurgo@gmail.com> * fixed NaiveBayes __changelog__ Signed-off-by: Arthur Lu <learthurgo@gmail.com> * fix: __setitem__ == to single = * Array v 1.0.1 * Revert "Array v 1.0.1" This reverts commit 59783b79f7451586bc9741794589e00f0c625348. * Array v 1.0.1 * Array.py v 1.0.2 added more Array unit tests * cleaned .gitignore tra_analysis v 3.0.0-rc2 Signed-off-by: Arthur Lu <learthurgo@gmail.com> * added *.pyc to gitignore finished subdividing test_analysis * feat: gui layout + basic func * Froze and removed superscript (data-analysis) * remove data-analysis deps install for devcontainer * tukey pairwise comparison and multicomparison but no critical q-values * quick patch for devcontainer.json * better fix for devcontainer.json * fixed some styling in StatisticalTest removed print statement in StatisticalTest unit tests * update analysis tests to be more effecient * don't use loop for test_nativebayes * removed useless secondary docker files * tra-analysis v 3.0.0 Co-authored-by: James Pan <panzhenyu2014@gmail.com> Co-authored-by: AGawde05 <agawde05@gmail.com> Co-authored-by: zpan1 <72054510+zpan1@users.noreply.github.com> Co-authored-by: Dev Singh <dev@devksingh.com> Co-authored-by: = <=> Co-authored-by: Dev Singh <dsingh@imsa.edu> Co-authored-by: zpan1 <zpan@imsa.edu>
2021-04-29 00:33:50 +00:00
)
__all__ = [
"quicksort",
"mergesort",
"introsort",
"heapsort",
"insertionsort",
"timsort",
"selectionsort",
"shellsort",
"bubblesort",
"cyclesort",
"cocktailsort",
]
import numpy as np
def quicksort(a):
def sort(array):
less = []
equal = []
greater = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
less.append(x)
elif x == pivot:
equal.append(x)
elif x > pivot:
greater.append(x)
return sort(less)+equal+sort(greater)
else:
return array
return np.array(sort(a))
def mergesort(a):
def sort(array):
array = array
if len(array) >1:
middle = len(array) // 2
L = array[:middle]
R = array[middle:]
sort(L)
sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
array[k] = L[i]
i+= 1
else:
array[k] = R[j]
j+= 1
k+= 1
while i < len(L):
array[k] = L[i]
i+= 1
k+= 1
while j < len(R):
array[k] = R[j]
j+= 1
k+= 1
return array
return sort(a)
def introsort(a):
def sort(array, start, end, maxdepth):
array = array
if end - start <= 1:
return
elif maxdepth == 0:
heapsort(array, start, end)
else:
p = partition(array, start, end)
sort(array, start, p + 1, maxdepth - 1)
sort(array, p + 1, end, maxdepth - 1)
return array
def partition(array, start, end):
pivot = array[start]
i = start - 1
j = end
while True:
i = i + 1
while array[i] < pivot:
i = i + 1
j = j - 1
while array[j] > pivot:
j = j - 1
if i >= j:
return j
swap(array, i, j)
def swap(array, i, j):
array[i], array[j] = array[j], array[i]
def heapsort(array, start, end):
build_max_heap(array, start, end)
for i in range(end - 1, start, -1):
swap(array, start, i)
max_heapify(array, index=0, start=start, end=i)
def build_max_heap(array, start, end):
def parent(i):
return (i - 1)//2
length = end - start
index = parent(length - 1)
while index >= 0:
max_heapify(array, index, start, end)
index = index - 1
def max_heapify(array, index, start, end):
def left(i):
return 2*i + 1
def right(i):
return 2*i + 2
size = end - start
l = left(index)
r = right(index)
if (l < size and array[start + l] > array[start + index]):
largest = l
else:
largest = index
if (r < size and array[start + r] > array[start + largest]):
largest = r
if largest != index:
swap(array, start + largest, start + index)
max_heapify(array, largest, start, end)
maxdepth = (len(a).bit_length() - 1)*2
return sort(a, 0, len(a), maxdepth)
def heapsort(a):
def sort(array):
array = array
n = len(array)
for i in range(n//2 - 1, -1, -1):
heapify(array, n, i)
for i in range(n-1, 0, -1):
array[i], array[0] = array[0], array[i]
heapify(array, i, 0)
return array
def heapify(array, n, i):
array = array
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and array[i] < array[l]:
largest = l
if r < n and array[largest] < array[r]:
largest = r
if largest != i:
array[i],array[largest] = array[largest],array[i]
heapify(array, n, largest)
return array
return sort(a)
def insertionsort(a):
def sort(array):
array = array
for i in range(1, len(array)):
key = array[i]
j = i-1
while j >=0 and key < array[j] :
array[j+1] = array[j]
j -= 1
array[j+1] = key
return array
return sort(a)
def timsort(a, block = 32):
BLOCK = block
def sort(array, n):
array = array
for i in range(0, n, BLOCK):
insertionsort(array, i, min((i+31), (n-1)))
size = BLOCK
while size < n:
for left in range(0, n, 2*size):
mid = left + size - 1
right = min((left + 2*size - 1), (n-1))
merge(array, left, mid, right)
size = 2*size
return array
def insertionsort(array, left, right):
array = array
for i in range(left + 1, right+1):
temp = array[i]
j = i - 1
while j >= left and array[j] > temp :
array[j+1] = array[j]
j -= 1
array[j+1] = temp
return array
def merge(array, l, m, r):
len1, len2 = m - l + 1, r - m
left, right = [], []
for i in range(0, len1):
left.append(array[l + i])
for i in range(0, len2):
right.append(array[m + 1 + i])
i, j, k = 0, 0, l
while i < len1 and j < len2:
if left[i] <= right[j]:
array[k] = left[i]
i += 1
else:
array[k] = right[j]
j += 1
k += 1
while i < len1:
array[k] = left[i]
k += 1
i += 1
while j < len2:
array[k] = right[j]
k += 1
j += 1
return sort(a, len(a))
def selectionsort(a):
array = a
for i in range(len(array)):
min_idx = i
for j in range(i+1, len(array)):
if array[min_idx] > array[j]:
min_idx = j
array[i], array[min_idx] = array[min_idx], array[i]
return array
def shellsort(a):
array = a
n = len(array)
gap = n//2
while gap > 0:
for i in range(gap,n):
temp = array[i]
j = i
while j >= gap and array[j-gap] >temp:
array[j] = array[j-gap]
j -= gap
array[j] = temp
gap //= 2
return array
def bubblesort(a):
def sort(array):
for i, num in enumerate(array):
try:
if array[i+1] < num:
array[i] = array[i+1]
array[i+1] = num
sort(array)
except IndexError:
pass
return array
return sort(a)
def cyclesort(a):
def sort(array):
array = array
writes = 0
for cycleStart in range(0, len(array) - 1):
item = array[cycleStart]
pos = cycleStart
for i in range(cycleStart + 1, len(array)):
if array[i] < item:
pos += 1
if pos == cycleStart:
continue
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
writes += 1
while pos != cycleStart:
pos = cycleStart
for i in range(cycleStart + 1, len(array)):
if array[i] < item:
pos += 1
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
writes += 1
return array
return sort(a)
def cocktailsort(a):
def sort(array):
array = array
n = len(array)
swapped = True
start = 0
end = n-1
while (swapped == True):
swapped = False
for i in range (start, end):
if (array[i] > array[i + 1]) :
array[i], array[i + 1]= array[i + 1], array[i]
swapped = True
if (swapped == False):
break
swapped = False
end = end-1
for i in range(end-1, start-1, -1):
if (array[i] > array[i + 1]):
array[i], array[i + 1] = array[i + 1], array[i]
swapped = True
start = start + 1
return array
return sort(a)