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.
Your variable names doesn't convey much meaning. I don't get what the
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:
- cache reused values;
- name your object and thus document your algorithm a bit more.
My take on this would be:
if len(values) < 2:
pivot, *values = values # Python 3 syntax, use `pivot, values = values, 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)
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.
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
if len(d_val) <= 1:
return qsort([lt for lt in d_val[1:] if lt < d_val]) + d_val[0:1] + \
qsort([ge for ge in d_val[1:] if ge >= d_val])
return sorted(l, key=itemgetter(3), reverse=True)
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)
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__':
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.
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:
result = list(iterable)
_quick_sort(result, 0, len(result) - 1)
def _quick_sort(values, begin, end):
if end <= begin:
# TODO: implement quick sort using swaps
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.