-1

I found this function written in python on the internet and I'm confused if it's a quick sort or not because it's written in one line and it work very well and quickly and I think that it work with the complexity of O (n*log n) even in the worst case, so this is the code: 

def qsort(L): 
  return (qsort([x for x in L[1:] if x < L[0]]) +\
          L[0:1] + \
          qsort([x for x in L[1:] if x >= L[0]])) if L else []
Adelov
  • 18
  • 7
  • 1
    Looks like a Quicksort. – Carcigenicate Mar 16 '17 at 00:44
  • 1
    Break this one liner into multiple lines to make sense of it. One liners just for the sake of it often are a poor idea if it hinders readability... – Julien Mar 16 '17 at 00:44
  • Yes, it’s a quicksort. (It uses less-than-optimal space, but it still counts.) – Ry- Mar 16 '17 at 00:46
  • 1
    Yes that looks like quicksort. But keep in mind that the worst case complexity of quicksort is O(n^2), not O(n*log n). – Russel Simmons Mar 16 '17 at 00:47
  • To build on previous comment: look at what happens when the input list is already in order. – Julien Mar 16 '17 at 00:49
  • @Carcigenicate i think so . – Adelov Mar 16 '17 at 00:52
  • This is virtually identical to a version that is frequently taught in introductions to functional programming, often using Haskell or ML. Some regard it as not a "true" quicksort since it some ways it doesn't really follow Hoare's original algorithm very closely. That is possible semantics, Here are a couple of questions discussing the issue: http://stackoverflow.com/q/7717691/4996248 and http://stackoverflow.com/q/42101051/4996248 – John Coleman Mar 16 '17 at 01:32

1 Answers1

0

Yes it's quick sort as it's perfectly matching this algorithm definition: pick up arbitrary element from the list, move values lower than this element to the beginning of the list (before selected element) and perform quick sort recursively:

qsort([x for x in L[1:] if x < L[0]])

bigger or equal values to the end of the list (after selected element) and perform quick sort recursively

qsort([x for x in L[1:] if x >= L[0]])

if list is empty (recursion termination) then of course result is empty list.

Michał Załęski
  • 28
  • 3