생성일: 2021년 12월 13일 오후 6:59
def min_index(values, start_index, end_index):
index_of_min = start_index
for index in range(start_index + 1, end_index + 1):
if (values[index] < values[index_of_min]):
index_of_min = index
return index_of_min
def selection_sort(values):
endIndex = len(values) - 1
for current in range(0, endIndex):
index = min_index(values, current, endIndex)
values[current], values[index] = values[index], values[current]
def bubble_sort(values):
current = 0
while(current < len(values) - 1):
BubbleUp(values, current, len(values) - 1)
current += 1
def BubbleUp(values, startIndex, endIndex):
for i in range(endIndex, startIndex, -1):
if (values[i] < values[i-1]):
values[i], values[i-1] = values[i-1], values[i]
def short_bubble(values, numValues):
'''[10]'''
current = 0
sort = False
while(current < numValues - 1 and not sort):
bubble_up(values, current, numValues - 1, sort)
current += 1
def bubble_up(values, startIndex, endIndex, sort):
'''[11]'''
sort = True
for index in range(endIndex, startIndex - 1, -1):
if (values[index] < values[index - 1]):
values[index], values[index - 1] = values[index - 1], values[index]
sort = False
def insertion_sort(values):
for count in range(0, len(values)):
insert_item(values, 0, count)
def insert_item(values, start_index, end_index):
finished = False
current = end_index
more_to_search = (current != start_index)
while(more_to_search and not finished):
if (values[current] < values[current - 1]):
values[current], values[current - 1] = values[current- 1], values[current]
current -= 1
more_to_search = (current != start_index)
else:
finished = True
def reheap_down(elements, root, bottom):
left_child = root * 2 + 1
right_child = root * 2 + 2
if(left_child <= bottom):
if (left_child == bottom):
max_child = left_child
else:
if (elements[left_child] <= elements[right_child]):
max_child = right_child
else:
max_child = left_child
if (elements[root] < elements[max_child]):
elements[root], elements[max_child] = elements[max_child], elements[root]
reheap_down(elements, max_child, bottom)
def heap_sort(values, numValues):
for index in range(numValues//2 - 1, -1, -1):
reheap_down(values, index, numValues - 1)
for index in range(numValues - 1, 0, -1):
values[0], values[index] = values[index], values[0]
reheap_down(values, 0, index - 1)
def split(values, first, last):
splitVal = values[first]
saveFirst = first
first += 1
while(True):
onCorrectSide = True
while(onCorrectSide):
if(values[first] > splitVal):
onCorrectSide = False
else:
first += 1
onCorrectSide = (first <= last)
onCorrectSide = (first <= last)
while(onCorrectSide):
if(values[last] <= splitVal):
onCorrectSide = False
else:
last -= 1
onCorrectSide = (first <= last)
if(first < last):
values[first], values[last] = values[last], values[first]
first += 1
last -= 1
if (first > last):
break
splitPoint = last
values[saveFirst], values[splitPoint] = values[splitPoint], values[saveFirst]
return splitPoint
def quick_sort(values, first, last):
if (first < last):
splitPoint = split(values, first, last)
quick_sort(values, first, splitPoint - 1)
quick_sort(values, splitPoint + 1, last)
return values
def merge_sort(values, first, last):
if (first < last):
middle = (first + last) // 2
merge_sort(values, first, middle)
merge_sort(values, middle + 1, last)
return merge(values, first, middle, middle + 1, last)
else:
return values
def merge(values, leftFirst, leftLast, rightFirst, rightLast):
tempArray = [0] * len(values)
index = leftFirst
saveFirst = leftFirst
while((leftFirst <= leftLast) and (rightFirst <= rightLast)):
if (values[leftFirst] < values[rightFirst]):
tempArray[index] = values[leftFirst]
leftFirst += 1
else:
tempArray[index] = values[rightFirst]
rightFirst += 1
index += 1
while(leftFirst <= leftLast):
tempArray[index] = values[leftFirst]
leftFirst += 1
index += 1
while(rightFirst <= rightLast):
tempArray[index] = values[rightFirst]
rightFirst += 1
index += 1
for index in range(saveFirst, rightLast + 1):
values[index] = tempArray[index]
return values