Advertisement
cobster

Untitled

Oct 6th, 2015
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.80 KB | None | 0 0
  1. def sort():
  2. lst = [ int( member ) for member in input( ).split( ) ]
  3. return helper_sort(lst)
  4.  
  5. def helper_sort(lst):
  6.  
  7. #GETS MY MIDDLE VALUE FOR LIST DIVISION
  8.  
  9. average = 0
  10.  
  11. for index_value in range(len(lst)):
  12. average += (lst[index_value])
  13. index_value += 1
  14.  
  15.  
  16. middle_value = (average // (len(lst)))
  17.  
  18. return creation_of_lists(lst , middle_value)
  19.  
  20.  
  21. #################################################
  22.  
  23.  
  24. def creation_of_lists(lst , middle_value):
  25. #creates my lists of equal lenght (or length differs by one)
  26.  
  27. sub_lst_1 = [ lst[x] for x in range(len(lst)) if lst[x] <= middle_value]
  28.  
  29. print(sub_lst_1)
  30.  
  31. sub_lst_2 = [ lst[x] for x in range(len(lst)) if lst[x] > middle_value]
  32.  
  33. print(sub_lst_2)
  34.  
  35. #below will check for outliers to ensure that the lenght of the list
  36. #only differ by no more than 1.
  37.  
  38. while len(sub_lst_1) != (len(sub_lst_2)+1):
  39.  
  40. if len(sub_lst_1) > len(sub_lst_2):
  41. return creation_of_lists(lst , middle_value-1)
  42.  
  43. if len(sub_lst_1) < len(sub_lst_2):
  44. return creation_of_lists(lst , middle_value+1)
  45. if len(sub_lst_1) != (len(sub_lst_2)+1):
  46. return sorting_lst_1(sub_lst_1 , i=1) + sorting_lst_2(sub_lst_2 , i=1)
  47.  
  48. return sorting_lst_1(sub_lst_1 , i=1) + sorting_lst_2(sub_lst_2 , i=1)
  49.  
  50.  
  51. ########################################################
  52.  
  53.  
  54. def sorting_lst_1(sub_lst_1,i=1):
  55.  
  56. #This will recursively sort out the 1st half of the sub divided list (sub_lst_1)
  57.  
  58. if i >= len(sub_lst_1):
  59. return sub_lst_1
  60.  
  61. if sub_lst_1[i-1] > sub_lst_1[i]:
  62. temp = sub_lst_1[i]
  63.  
  64. #temp is my variable to keep hold of my current value in the list
  65.  
  66. for a in range(0, i):
  67.  
  68. #Allows me two check my two values and updates my pointer when done
  69.  
  70. if temp < sub_lst_1[a]:
  71. sub_lst_1.insert(a,temp)
  72. del sub_lst_1[i+1]
  73.  
  74. break
  75.  
  76. return sorting_lst_1(sub_lst_1, i+1)
  77.  
  78. def sorting_lst_2(sub_lst_2,i=1):
  79.  
  80. #THIS IS A COPY OF ABOVE
  81. #This will recursively sort out the 2nd half of the sub divided list (sub_lst_2)
  82.  
  83. if i >= len(sub_lst_2):
  84. return sub_lst_2
  85.  
  86. if sub_lst_2[i-1] > sub_lst_2[i]:
  87. temp = sub_lst_2[i]
  88.  
  89. for a in range(0, i):
  90.  
  91. if temp < sub_lst_2[a]:
  92.  
  93. sub_lst_2.insert(a,temp)
  94. del sub_lst_2[i+1]
  95.  
  96. break
  97.  
  98. return sorting_lst_2(sub_lst_2, i+1)
  99.  
  100.  
  101. ###############################################
  102.  
  103.  
  104. #Function Sort
  105. #This function is there to call the recursive function ‘Helper_Sort’ and to output the sorted list.
  106.  
  107. #Helper_Sort.
  108. #For ease of reading I have divide this function into three separate parts.
  109. #Part
  110.  
  111. #Code
  112. #median = 0
  113.  
  114. #for index_value in range(len(lst)):
  115. # median += lst[index_value]
  116. # index_value += 1
  117.  
  118. #middle_value = median // 2
  119.  
  120. #Explanation and Reasoning
  121. #1) This part essentially makes my arranging of the two lists easier.
  122. #2) I find the Median by adding all the individual values in the list and dividing by the number of integers in the list
  123. #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.
  124. #
  125. #Part 2:
  126. # sub_lst_1 = [ lst[x] for x in lst if x <= middle_value]
  127. # sub_lst_2 = [ lst[x] for x in lst if x > middle_value]
  128.  
  129. #Explanation and Reasoning
  130. #1) What I do here is split my original list into two smaller lists.
  131. #2) I use the value of the median to act as a rough sort. Where there will be a gradual increase in the number.
  132. #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