1
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ From your description, that's not merge sort, it's quicksort. \$\endgroup\$ – Tom Karzes Dec 7 '17 at 11:30
  • \$\begingroup\$ Merge sort combines 2 sorted lists in the end, not 3. This is definitely quicksort instead. \$\endgroup\$ – RoadRunner Dec 7 '17 at 11:49
  • \$\begingroup\$ Re "and split the list into three: list of smaller numbers, Equal to and greater than k.": why do you need to sort the list of Equals? By definition, that list is already sorted. \$\endgroup\$ – boardrider Dec 8 '17 at 8:20
  • \$\begingroup\$ This is neither mergesort nor quicksort. Based on the description of your algorithm, one optimization to shorten the code and simplify the logic would be to only use 2 buckets rather than 3 (e.g.: lower or equal, and higher). The time complexity is O(N log N) which is optimal. The space complexity is also O(N log N): look up quicksort for a similar algorithm in O(N) space. \$\endgroup\$ – marcv81 Dec 18 '17 at 9:58
1
\$\begingroup\$

When you've split a list into a smaller and a bigger halves, after sorting them the elements in the first half are all still smaller than all the elements in the second.

So, merging such sorted halves is just positional concatenation, i.e. putting the two halves beside each other so that in the resulting sequence, first go the elements of the first half (sorted), and then the second.

There's no need to compare the elements values in your merge, results of such comparisons are known in advance, predetermined by the partition stage.

This is the essence of quicksort - partition by value, necessarily putting some effort into doing that, and then, after sorting the halves, join positionally, easily and simply.

The merge sort works the other way - it partitions the list simply, by position; and spends more effort merging the sorted parts, according to the elements' values:

                 mergesort             quicksort

partition        positional            by value

merge            by value              positional

Splitting into three parts is a good optimization, but changes nothing regarding the above.

\$\endgroup\$
  • \$\begingroup\$ quicksort is thus essentially recursive, and mergesort essentially iterative. \$\endgroup\$ – Will Ness Dec 19 '17 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy