Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def sort():
- lst = [ int( member ) for member in input( ).split( ) ]
- return helper_sort(lst)
- def helper_sort(lst):
- #GETS MY MIDDLE VALUE FOR LIST DIVISION
- average = 0
- for index_value in range(len(lst)):
- average += (lst[index_value])
- index_value += 1
- middle_value = (average // (len(lst)))
- return creation_of_lists(lst , middle_value)
- #################################################
- def creation_of_lists(lst , middle_value):
- #creates my lists of equal lenght (or length differs by one)
- sub_lst_1 = [ lst[x] for x in range(len(lst)) if lst[x] <= middle_value]
- print(sub_lst_1)
- sub_lst_2 = [ lst[x] for x in range(len(lst)) if lst[x] > middle_value]
- print(sub_lst_2)
- #below will check for outliers to ensure that the lenght of the list
- #only differ by no more than 1.
- while len(sub_lst_1) != (len(sub_lst_2)+1):
- if len(sub_lst_1) > len(sub_lst_2):
- return creation_of_lists(lst , middle_value-1)
- if len(sub_lst_1) < len(sub_lst_2):
- return creation_of_lists(lst , middle_value+1)
- if len(sub_lst_1) != (len(sub_lst_2)+1):
- return sorting_lst_1(sub_lst_1 , i=1) + sorting_lst_2(sub_lst_2 , i=1)
- return sorting_lst_1(sub_lst_1 , i=1) + sorting_lst_2(sub_lst_2 , i=1)
- ########################################################
- def sorting_lst_1(sub_lst_1,i=1):
- #This will recursively sort out the 1st half of the sub divided list (sub_lst_1)
- if i >= len(sub_lst_1):
- return sub_lst_1
- if sub_lst_1[i-1] > sub_lst_1[i]:
- temp = sub_lst_1[i]
- #temp is my variable to keep hold of my current value in the list
- for a in range(0, i):
- #Allows me two check my two values and updates my pointer when done
- if temp < sub_lst_1[a]:
- sub_lst_1.insert(a,temp)
- del sub_lst_1[i+1]
- break
- return sorting_lst_1(sub_lst_1, i+1)
- def sorting_lst_2(sub_lst_2,i=1):
- #THIS IS A COPY OF ABOVE
- #This will recursively sort out the 2nd half of the sub divided list (sub_lst_2)
- if i >= len(sub_lst_2):
- return sub_lst_2
- if sub_lst_2[i-1] > sub_lst_2[i]:
- temp = sub_lst_2[i]
- for a in range(0, i):
- if temp < sub_lst_2[a]:
- sub_lst_2.insert(a,temp)
- del sub_lst_2[i+1]
- break
- return sorting_lst_2(sub_lst_2, i+1)
- ###############################################
- #Function Sort
- #This function is there to call the recursive function ‘Helper_Sort’ and to output the sorted list.
- #Helper_Sort.
- #For ease of reading I have divide this function into three separate parts.
- #Part
- #Code
- #median = 0
- #for index_value in range(len(lst)):
- # median += lst[index_value]
- # index_value += 1
- #middle_value = median // 2
- #Explanation and Reasoning
- #1) This part essentially makes my arranging of the two lists easier.
- #2) I find the Median by adding all the individual values in the list and dividing by the number of integers in the list
- #3) Having the median as a halfway point will more often than not split my list equally into two parts. If there is an outlier I deal with them in Part 3.
- #
- #Part 2:
- # sub_lst_1 = [ lst[x] for x in lst if x <= middle_value]
- # sub_lst_2 = [ lst[x] for x in lst if x > middle_value]
- #Explanation and Reasoning
- #1) What I do here is split my original list into two smaller lists.
- #2) I use the value of the median to act as a rough sort. Where there will be a gradual increase in the number.
- #3) I use a list comprehension to generate my two sub lists. To allow for me to order them
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement