Sort data from a text file in descending order using quick sort

Question

I have a text file containing the following data.

ascon1 201707011 John 77.5 11.5 11.5 11.5
ascon1 201707012 Grld 70.0 11.5 11.5 11.5
ascon1 201707013 Josh 79.5 11.5 11.5 11.5 
ascon1 201707014 Jess 67.5 11.5 11.5 11.5 
ascon1 201707015 Jack 97.5 11.5 11.5 11.5 

I need the data to look like this.

ascon1 201707015 Jack 97.5 11.5 11.5 11.5 
ascon1 201707013 Josh 79.5 11.5 11.5 11.5
ascon1 201707011 John 77.5 11.5 11.5 11.5 
ascon1 201707012 Grld 70.0 11.5 11.5 11.5 
ascon1 201707014 Jess 67.5 11.5 11.5 11.5 

so here is my code. The above part is working using the inbuilt sorted function from python. but in ascending order instead of decending order.

with open('input.txt') as f:
    lines = [line.split(' ') for line in f]
output = open("input(sorted).txt", 'w')

for line in sorted(lines, key=itemgetter(3)):
    output.write(' '.join(line))

output.close()

I want to use the quick-sort function to solve this problem. this is my function.

def qsort(d_val):
    if len(d_val) <= 1: return d_val
    return qsort([lt for lt in d_val[1:] if lt < d_val[0]]) + d_val[0:1] + \
           qsort([ge for ge in d_val[1:] if ge >= d_val[0]])

Answer 1

tl; dr

Use sorted(lines, key=itemgetter(3), reverse=True) instead of your custom function. This is both faster, more efficient, easier to read and easily understood by anyone.

Style

Your variable names doesn't convey much meaning. I don't get what the d in d_val can mean (data ?). In general, abreviations put unnecessary mental burden on the reader so avoid them. Do not hesitate to use more intermediate variable also as you can both:

1. cache reused values;
2. name your object and thus document your algorithm a bit more.

My take on this would be:

def quick_sort(values):
    if len(values) < 2:
        return values

    pivot, *values = values  # Python 3 syntax, use `pivot, values = values[0], values[1:]` on Python 2
    lower = [x for x in values if x < pivot]
    upper = [x for x in values if x >= pivot]
    return quick_sort(lower) + [pivot] + quick_sort(upper)

Performances

Each time you call qsort, you’re building 5 new lists: two for the intermediate values and one for the returned value plus 2 for each d_val[1:]. This quintuple the amount of memory needed by quick_sort call. Luckily for you, these are shallow copies which means inner lists are not copied, only their reference count increases.

Speed

Creating all these lists means a lot of allocations and/or copies happening under the hood, which slows down the whole thing. A simple sort of 2500 values timed using the following code:

from operator import itemgetter
import timeit


def qsort(d_val):
    if len(d_val) <= 1:
        return d_val
    return qsort([lt for lt in d_val[1:] if lt < d_val[0]]) + d_val[0:1] + \
           qsort([ge for ge in d_val[1:] if ge >= d_val[0]])


def qsort_test_case(l):
    return qsort(l)


def sorted_test_case(l):
    return sorted(l, key=itemgetter(3), reverse=True)


def generate_data():
    data = '''ascon1 201707011 John 77.5 11.5 11.5 11.5
ascon1 201707012 Grld 70.0 11.5 11.5 11.5
ascon1 201707013 Josh 79.5 11.5 11.5 11.5
ascon1 201707014 Jess 67.5 11.5 11.5 11.5
ascon1 201707015 Jack 97.5 11.5 11.5 11.5'''
    data = '\n'.join(data for _ in range(500))
    for line in data.splitlines():
        name, date, n, d1, d2, d3, d4 = line.split()
        yield name, date, n, float(d1), float(d2), float(d3), float(d4)


def main():
    print(timeit.timeit('test(l)', setup='from __main__ import generate_data, qsort_test_case as test; l = list(generate_data())', number=100))
    print(timeit.timeit('test(l)', setup='from __main__ import generate_data, sorted_test_case as test; l = list(generate_data())', number=100))


if __name__ == '__main__':
    main()

Yields a runtime of 18.58127073900141 seconds for your quick sort versus 0.03511061900098866 seconds for sorted. 530 times slower, I guess quick sort is not the right name there.

Alternate approach

Instead of creating intermediate lists, you could have an helper function that sort in-place but accept start and stop indices as arguments; and the recursive call will only change these values. This means you'll have to wrap the first call in a function that will perform a copy of the original list, call this helper to sort the copy in-place, and return the copy; leaving the original list untouched.

The advantage of this approach is that you can now use any iterable as input, not necessarily lists:

def quick_sort(iterable):
    result = list(iterable)
    _quick_sort(result, 0, len(result) - 1)
    return result


def _quick_sort(values, begin, end):
    if end <= begin:
        return
    # TODO: implement quick sort using swaps

Genericity

Your qsort function does not sort the array the same way than the sorted call in your original code. This is due to the fact that each item will sorted according to its first element then second if it compares equal (then third…) in your implementation (implicit rule for list comparisons); whereas you are using itemgetter(3) in the sorted call to compare only the fourth element.

Adding this kind of genericity to your quick sort will cost you time, impair readability and understanding of the code and can become error-prone at some point. Whereas when using sorted you don't have to worry about this kind of details that comes for free.