I want to find a more elegant way to build a recursive sorting function.
The function randomly selects one of the numbers from a given list, k
, and splits the list into three: list of smaller numbers, equal to and greater than k
.
Now, I recursively sort each list and then combine the 3 to a single sorted list.
For example:
The list [5,2,7,4,9,3]
for k = 5
is split into three: [7,9], [5], [2,4,3]
.
Now sort recursively to get the lists [7,9]
and [2,4,3]
in order to receive [7,9] and [2,3,4]
.
The three lists sorted for the receipt of one sorted list: [2,3,4,5,7,9]
Any suggestions?
def partition(lst,k):
bigger = []
smaller = []
equal = []
i = 0
while i < len(lst) :
if lst[i] < k:
smaller.append(lst[i])
i += 1
elif lst[i] == k:
equal.append(lst[i])
i += 1
else:
bigger.append(lst[i])
i += 1
# merge 3 list:
merged = [smaller,equal ,bigger]
return merged
def my_sort(lst):
import random
k = (random.choice(lst))
lst3 = partition(lst,k)
def merge(left, right):
merged = []
left_i, right_i = 0, 0
while left_i < len(left) and right_i < len(right):
if left[left_i] <= right[right_i]:
merged.append(left[left_i])
left_i += 1
else:
merged.append(right[right_i])
right_i += 1
# copy remaining:
merged += left[left_i:] + right[right_i:]
return merged
def mergesort(lst):
if len(lst) <= 1:
return lst
middle = len(lst) / 2
left = mergesort(lst[: middle])
right = mergesort(lst[middle:])
return merge(left, right)
left = mergesort(lst3[0])
right = mergesort(lst3[2])
print k
return merge(merge(left,lst3[1]),right)