Quicksort with Python

Question

I am totally new to python and I am trying to implement quicksort in it  Could someone please help me complete my code   I do not know how to concatenate the three arrays and printing them    def sort array  12 4 5 6 7 3 1 15        less          equal          greater           if len array   gt  1          pivot   array 0          for x in array              if x  lt  pivot                  less append x              if x    pivot                  equal append x              if x  gt  pivot                  greater append x              sort less              sort pivot              sort greater

User · Answer

There is another concise and beautiful version

def qsort(arr): 
    if len(arr) <= 1:
        return arr
    else:
        return qsort([x for x in arr[1:] if x < arr[0]]) + \
               [arr[0]] + \
               qsort([x for x in arr[1:] if x >= arr[0]])

# this comment is just to improve readability due to horizontal scroll!!!

Let me explain the above codes for details

pick the first element of array arr[0] as pivot

[arr[0]]
qsort those elements of array which are less than pivot with List Comprehension

qsort([x for x in arr[1:] if x < arr[0]])
qsort those elements of array which are larger than pivot with List Comprehension

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

User · Answer

def quicksort items       if not len items   gt  1          return items     items  pivot   partition items      return quicksort items  pivot      items pivot     quicksort items pivot   1      def partition items       i   1     pivot   0     for j in range 1  len items            if items j   lt   items pivot               items i   items j    items j   items i              i    1     items i - 1   items pivot    items pivot   items i - 1      return items  i - 1

User · Answer

def quick sort list       if len list    0          return         return  quick sort filter  lambda item  item  lt  list 0  list      v for v in list if v  list 0        quick sort  filter  lambda item  item  gt  list 0   list

User · Answer

Partition - Split an array by a pivot that smaller elements move to the left and greater elemets move to the right or vice versa  A pivot can be an random element from an array  To make this algorith we need to know what is begin and end index of an array and where is a pivot  Then set two auxiliary pointers L  R   So we have an array user     begin     end       The start position of L and R pointers      begin next     end       nbsp  nbsp  nbsp  nbsp  nbsp R nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp L  while L  lt  end  nbsp  nbsp 1  If a user pivot    user L  then move R by one and swap user R  with user L   nbsp  nbsp 2  move L by one  After while swap user R  with user pivot   Quick sort - Use the partition algorithm until every next part of the split by a pivot will have begin index greater or equals than end index   def qsort user  begin  end        if begin  gt   end          return        partition       pivot   begin     L   begin 1     R   begin     while L  lt  end          if user begin   gt  user L               R  1             user R   user L    user L   user R          L   1     user R   user begin    user begin   user R       qsort user  0  R      qsort user  R 1  end   tests           sample   1   answer   1          sample   3 9   answer   3 9          sample   1 8 1   answer   1 1 8          sample   7 5 5 1   answer   1 5 5 7          sample   4 10 5 9 3   answer   3 4 5 9 10          sample   6 6 3 8 7 7   answer   3 6 6 7 7 8          sample   3 6 7 2 4 5 4   answer   2 3 4 4 5 6 7          sample   1 5 6 1 9 0 7 4   answer   0 1 1 4 5 6 7 9          sample   0 9 5 2 2 5 8 3 8   answer   0 2 2 3 5 5 8 8 9          sample   2 5 3 3 2 0 9 0 0 7   answer   0 0 0 2 2 3 3 5 7 9      for test in tests       sample   test  sample          answer   test  answer        qsort sample 0 len sample        print sample    answer

User · Answer

functional programming aproach  smaller   lambda xs  y  filter lambda x  x  lt   y  xs  larger   lambda xs  y  filter lambda x  x  gt  y  xs  qsort   lambda xs  qsort smaller xs 1   xs 0       xs 0     qsort larger xs 1   xs 0    if xs       else     print qsort  3 1 4 2 5       1 2 3 4 5

User · Answer

My answer is very similar to the great one from  alisianoi   However  I believe there is a slight inefficiency in his code  see my comment   which I removed  Moreover  I added more explanation and was a bit more specific about the problem of duplicate  pivot  values  def quicksort nums  begin 0  end None         Only at the beginning end None  In this case set to len nums -1     if end is None  end   len nums  - 1        If list part is invalid or has only 1 element  do nothing     if begin gt  end  return        Pick random pivot     pivot   nums random randint begin  end          Initialize left and right pointers     left  right   begin  end     while left  lt  right            Find first  quot wrong quot  value from left hand side  i e  first value  gt   pivot           Find first  quot wrong quot  value from right hand side  i e  first value  lt   pivot           Note  In the LAST while loop  both left and right will point to pivot          while nums left   lt  pivot  left    1         while nums right   gt  pivot  right -  1            Swap the  quot wrong quot  values         if left    right              nums left   nums right    nums right   nums left                Problem   loop can get stuck if pivot value exists more than once  Simply solve with                if nums left     nums right                   assert nums left   pivot                 left    1        Now  left and right both point to a pivot value        All values to its left are smaller  or equal in case of duplicate pivot values        All values to its right are larger      assert left    right and nums left     pivot     quicksort nums  begin  left - 1      quicksort nums  left   1  end      return  Without recursion  def quicksort nums  ranges None       if ranges is None          ranges     0  len nums  - 1       while ranges                 start  end    ranges 0          ranges   ranges 1           if start  gt   end              continue         pivot   nums randint start  end           left   start         right   end         while left  lt  right              while nums left   lt  pivot                  left    1             while nums right   gt  pivot                  right -  1             if left    right                  nums left   nums right    nums right   nums left                  if nums left     nums right                       left    1         ranges     start  left - 1    left   1  end     ranges

User · Answer

This algorithm doesn t use recursive functions   Let N be any list of numbers with len N   gt  0  Set K    N  and execute the following program   Note  This is a stable sorting algorithm   def BinaryRip2Singletons K  S       K L          K P      K 0  0          K R          for i in range 1  len K 0             if   K 0  i   lt  K 0  0               K L append K 0  i           elif K 0  i   gt  K 0  0               K R append K 0  i           else              K P append   K 0  i         K new    K L  bool len K L     K P    K R  bool len K R     K 1       while len K new   gt  0          if len K new 0      1              S append K new 0  0               K new   K new 1           else               break     return K new  S  N    16  19  11  15  16  10  12  14  4  10  5  2  3  4  7  1  K     N   S       print  K     K   S     S  while len K   gt  0      K  S   BinaryRip2Singletons K  S      print  K     K   S     S       PROGRAM OUTPUT    K     16  19  11  15  16  10  12  14  4  10  5  2  3  4  7  1   S      K     11  15  10  12  14  4  10  5  2  3  4  7  1    16    16    19   S      K     10  4  10  5  2  3  4  7  1    11    15  12  14    16    16    19   S      K     4  5  2  3  4  7  1    10    10    11    15  12  14    16    16    19   S      K     2  3  1    4    4    5  7    10    10    11    15  12  14    16    16    19   S      K     5  7    10    10    11    15  12  14    16    16    19   S    1  2  3  4  4  K     15  12  14    16    16    19   S    1  2  3  4  4  5  7  10  10  11  K     12  14    15    16    16    19   S    1  2  3  4  4  5  7  10  10  11  K      S    1  2  3  4  4  5  7  10  10  11  12  14  15  16  16  19

User · Answer

I know many people have answered this question correctly and I enjoyed reading them  My answer is almost the same as zangw but I think the previous contributors did not do a good job of explaining visually how things actually work   so here is my attempt to help others that might visit this question answers in the future about a simple solution for quicksort implementation   How does it work     We basically select the first item as our pivot from our list and then we create two sub lists  Our first sublist contains the items that are less than pivot  Our second sublist contains our items that are great than or equal to pivot We then quick sort each of those and we combine them the first group    pivot   the second group to get the final result    Here is an example along with visual to go with it      pivot 9 11 2 0  average  n log of n   worse case  n 2     The code   def quicksort data   if  len data   lt  2       return data else      pivot   data 0     pivot      starting from element 1 to the end     rest   data 1       low    each for each in rest if each  lt  pivot      high    each for each in rest if each  gt   pivot      return quicksort low     pivot    quicksort high    items  9 11 2 0  print quicksort items

User · Answer

def quicksort array    if len array   lt  2    return array  else    pivot   array 0    less    i for i in array 1   if i  lt   pivot   greater    i for i in array 1   if i  gt  pivot   return quicksort less     pivot    quicksort greater

User · Answer

I will do quicksort using numpy library  I think it is really usefull library  They already implemented the quick sort method but you can implment also your custom method   import numpy array    3 4 8 1 2 13 28 11 99 76   The array what we want to sort  indexes   numpy argsort  array   None   quicksort   None  index list   list indexes   temp array       for index in index list      temp array append  array index    array   temp array  print array  it will show sorted array

User · Answer

def sort array  12 4 5 6 7 3 1 15           Sort the array by using quicksort          less          equal          greater           if len array   gt  1          pivot   array 0          for x in array              if x  lt  pivot                  less append x              elif x    pivot                  equal append x              elif x  gt  pivot                  greater append x            Don t forget to return something          return sort less  equal sort greater     Just use the   operator to join lists       Note that you want equal       not pivot     else     You need to handle the part at the end of the recursion - when you only have one element in your array  just return the array          return array

User · Answer

First we declare the first value in the array to be the pivot value and we also set the left and right marks We create the first while loop  this while loop is there to tell the partition process to run again if it doesn t satisfy the necessary condition then we apply the partition process after both partition processes have ran  we check to see if it satisfies the proper condition  If it does  we mark it as done  if not we switch the left and right values and apply it again Once its done switch the left and right values and return the split point   I am attaching the code below  This quicksort is a great learning tool because of the Location of the pivot value  Since it is in a constant place  you can walk through it multiple times and really get a hang of how it all works  In practice it is best to randomize the pivot to avoid O N 2  runtime   def quicksort10 alist       quicksort helper10 alist  0  len alist -1   def quicksort helper10 alist  first  last                    if first  lt  last          split point   partition10 alist  first  last          quicksort helper10 alist  first  split point - 1          quicksort helper10 alist  split point   1  last   def partition10 alist  first  last       done   False     pivot value   alist first      leftmark   first   1     rightmark   last     while not done          while leftmark  lt   rightmark and alist leftmark   lt   pivot value              leftmark   leftmark   1         while leftmark  lt   rightmark and alist rightmark   gt   pivot value              rightmark   rightmark - 1          if leftmark  gt  rightmark              done   True         else              temp   alist leftmark              alist leftmark    alist rightmark              alist rightmark    temp     temp   alist first      alist first    alist rightmark      alist rightmark    temp     return rightmark

User · Answer

I think both answers here works ok for the list provided  which answer the original question   but would breaks if an array containing non unique values is passed  So for completeness  I would just point out the small error in each and explain how to fix them   For example trying to sort the following array   12 4 5 6 7 3 1 15 1   Note that 1 appears twice  with Brionius algorithm    at some point will end up with the less array empty and the equal array with a pair of values  1 1  that can not be separated in the next iteration and the len     1   hence you ll end up with an infinite loop  You can fix it by either returning array if less is empty or better by not calling sort in your equal array  as in zangw answer   def sort array  12 4 5 6 7 3 1 15        less          equal          greater           if len array   gt  1          pivot   array 0          for x in array              if x  lt  pivot                  less append x              if x    pivot                  equal append x              if x  gt  pivot                  greater append x             Don t forget to return something          return sort less   equal  sort greater     Just use the   operator to join lists       Note that you want equal       not pivot     else     You need to hande the part at the end of the recursion - when you only have one element in your array  just return the array          return array   The fancier solution also breaks  but for a different cause  it is missing the return clause in the recursion line  which will cause at some point to return None and try to append it to a list       To fix it just add a return to that line  def qsort arr       if len arr   lt   1        return arr    else        return qsort  x for x in arr 1   if x lt arr 0       arr 0     qsort  x for x in arr 1   if x gt  arr 0

User · Answer

def is sorted arr    check if array is sorted     for i in range len arr  - 2           if arr i   gt  arr i   1               return False     return True  def qsort in place arr  left  right    arr - given array   left - first element index   right - last element index     if right - left  lt  1   if we have empty or one element array - nothing to do         return     else          left point   left  set left pointer that points on element that is candidate to swap with element under right pointer or pivot element         right point   right - 1  set right pointer that is candidate to swap with element under left pointer          while left point  lt   right point   while we have not checked all elements in the given array             swap left   arr left point   gt   arr right   True if we have to move that element after pivot             swap right   arr right point   lt  arr right   True if we have to move that element before pivot              if swap left and swap right   if both True we can swap elements under left and right pointers                 arr right point   arr left point    arr left point   arr right point                  left point    1                 right point -  1             else   if only one True we don t have place for to swap it                 if not swap left   if we dont need to swap it we move to next element                     left point    1                 if not swap right   if we dont need to swap it we move to prev element                     right point -  1          arr left point   arr right    arr right   arr left point   swap left element with pivot          qsort in place arr  left  left point - 1   execute qsort for left part of array  elements less than pivot          qsort in place arr  left point   1  right   execute qsort for right part of array  elements most than pivot   def main        import random     arr   random sample range 1  4000   10   generate random array     print arr      print is sorted arr       qsort in place arr  0  len arr  - 1      print arr      print is sorted arr    if   name         main         main

User · Answer

inlace sort  def qsort a  b 0  e None         partitioning     def part a  start  end           p   start         for i in xrange start 1  end               if a i   lt  a p                   a i   a p 1    a p 1   a i                  a p 1   a p    a p   a p 1                  p    1         return p      if e is None          e   len a      if e-b  lt   1  return      p   part a  b  e      qsort a  b  p      qsort a  p 1  e    without recursion   deq   collections deque   deq append  b  e   while len deq       el   deq pop       if el 1  - el 0   gt  1          p   part a  el 0   el 1           deq append  el 0   p           deq append  p 1  el 1

User · Answer

There are many answers to this already  but I think this approach is the most clean implementation   def quicksort arr           Quicksort a list       type arr  list      param arr  List to sort      returns  list -- Sorted list             if not arr          return         pivots    x for x in arr if x    arr 0       lesser   quicksort  x for x in arr if x  lt  arr 0        greater   quicksort  x for x in arr if x  gt  arr 0         return lesser   pivots   greater   You can of course skip storing everything in variables and return them straight away like this   def quicksort arr           Quicksort a list       type arr  list      param arr  List to sort      returns  list -- Sorted list             if not arr          return         return quicksort  x for x in arr if x  lt  arr 0                 x for x in arr if x    arr 0               quicksort  x for x in arr if x  gt  arr 0

User · Answer

The algorithm has 4 simple steps    Divide the array into 3 different parts  left  pivot and right  where pivot will have only one element  Let us choose this pivot element as the first element of array Append elements to the respective part by comparing them to pivot element   explanation in comments  Recurse this algorithm till all elements in the array have been sorted Finally  join left pivot right parts   Code for the algorithm in python   def my sort A          p A 0                                         determine pivot element         left                                          create left array       right                                         create right array       for i in range 1 len A             if cur elem is less than pivot  add elem in left array         if A i  lt  p            left append A i                       the recurssion will occur only if the left array is atleast half the size of original array           if len left  gt 1 and len left  gt  len A   2                          left my sort left                              recursive call         elif A i  gt p             right append A i                                   if elem is greater than pivot  append it to right array           if len right  gt 1 and len right  gt  len A   2           recurssion will occur only if length of right array is atleast the size of original array               right my sort right       A left  p  right                                         append all three part of the array into one and return it      return A  my sort  12 4 5 6 7 3 1 15     Carry on with this algorithm recursively with the left and right parts

User · Answer

Here s an easy implementation -  def quicksort array               if len array   lt  2                    return array             else                    pivot  array 0                    less    i for i in array 1   if i  lt   pivot                     greater    i for i in array 1   if i  gt  pivot                     return quicksort less     pivot    quicksort greater   print quicksort  10  5  2  3

User · Answer

Another quicksort implementation     A   Array    s   start index   e   end index   p   pivot index   g   greater than pivot boundary index  def swap A i1 i2     A i1   A i2    A i2   A i1   def partition A g p         O n  - just one for loop that visits each element once     for j in range g p         if A j   lt   A p           swap A j g          g    1      swap A p g      return g  def  quicksort A s e         Base case - we are sorting an array of size 1     if s  gt   e        return        Partition current array     p   partition A s e       quicksort A s p-1    Left side of pivot      quicksort A p 1 e    Right side of pivot    Wrapper function for the recursive one def quicksort A        quicksort A 0 len A -1   A    3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 -1   print A  quicksort A  print A

User · Answer

def Partition A p q       i p     x A i      for j in range p 1 q 1           if A j  lt  x              i i 1             tmp A j              A j  A i              A i  tmp     l A p      A p  A i      A i  l     return i  def quickSort A p q       if p lt q          r Partition A p q          quickSort A p r-1          quickSort A r 1 q      return A

User · Answer

A  true  in-place implementation  Algorithms 8 9  8 11 from the Algorithm Design and Applications Book by Michael T  Goodrich and Roberto Tamassia    from random import randint  def partition  A  a  b       p   randint a b        or mid point       p    a   b    2      piv   A p         swap the pivot with the end of the array     A p    A b      A b    piv      i   a       left index  right movement - gt       j   b - 1   right index  left movement  lt -       while i  lt   j            move right if smaller eq than to piv         while A i   lt   piv and i  lt   j              i    1           move left if greater eq than to piv         while A j   gt   piv and j  gt   i              j -  1            indices stopped moving          if i  lt  j                swap             t   A i              A i    A j              A j    t       place pivot back in the right place       all values  lt  pivot are to its left and        all values  gt  pivot are to its right     A b    A i      A i    piv      return i  def IpQuickSort  A  a  b        while a  lt  b          p   partition A  a  b    p is pivot s location           sort the smaller partition         if p - a  lt  b - p              IpQuickSort A a p-1              a   p   1   partition less than p is sorted         else              IpQuickSort A p 1 b              b   p - 1   partition greater than p is sorted   def main        A     12 3 5 4 7 3 1 3      print A     IpQuickSort A 0 len A -1      print A  if   name         main     main

User · Answer

functional approach   def qsort list       if len list   lt  2          return list      pivot   list pop       left   filter lambda x  x  lt   pivot  list      right   filter lambda x  x  gt  pivot  list       return qsort left     pivot    qsort right

User · Answer

For Version Python 3 x  a functional-style using operator module  primarily to improve readability    from operator import ge as greater  lt as lesser  def qsort L        if len L   lt   1  return L     pivot     L 0      sublist   lambda op    filter lambda num  op num  pivot   L 1          return qsort sublist lesser     pivot    qsort sublist greater     and is tested as          print  qsort  3 1 4 2 5       1 2 3 4 5

User · Answer

Full example with printed variables at partition step   def partition data  p  right       print   n   gt  Enter partition  p     right     format p  right       pivot   data right      print  pivot   data           format right  pivot        i   p - 1    this is a dangerous line      for j in range p  right           print  j      format j           if data j   lt   pivot              i   i   1             print  new i      format i               print  swap      lt - gt      format data i   data j                data i   data j    data j   data i       print  swap2      lt - gt      format data i   1   data right        data i   1   data right    data right   data i   1      return i   1   def quick sort data  left  right       if left  lt  right          pivot   partition data  left  right          quick sort data  left  pivot - 1          quick sort data  pivot   1  right   data    2  8  7  1  3  5  6  4   print  Input array      format data   quick sort data  0  len data  - 1  print  Output array      format data

User · Answer

Or if you prefer a one-liner that also illustrates the Python equivalent of C C   varags  lambda expressions  and if expressions   qsort   lambda x None   xs     if x is None else qsort   a for a in xs if a lt x      x    qsort   a for a in xs if a gt  x

User · Answer

Quicksort with Python   In real life  we should always use the builtin sort provided by Python  However  understanding the quicksort algorithm is instructive    My goal here is to break down the subject such that it is easily understood and replicable by the reader without having to return to reference materials   The quicksort algorithm is essentially the following    Select a pivot data point  Move all data points less than  below  the pivot to a position below the pivot - move those greater than or equal to  above  the pivot to a position above it  Apply the algorithm to the areas above and below the pivot   If the data are randomly distributed  selecting the first data point as the pivot is equivalent to a random selection   Readable example   First  let s look at a readable example that uses comments and variable names to point to intermediate values   def quicksort xs          Given indexable and slicable iterable  return a sorted list        if xs    if given list  or tuple  with one ordered item or more           pivot   xs 0            below will be less than          below    i for i in xs 1   if i  lt  pivot             above will be greater than or equal to          above    i for i in xs 1   if i  gt   pivot          return quicksort below     pivot    quicksort above      else           return xs   empty list   To restate the algorithm and code demonstrated here - we move values above the pivot to the right  and values below the pivot to the left  and then pass those partitions to same function to be further sorted   Golfed   This can be golfed to 88 characters   q lambda x x and q  i for i in x 1  if i lt  x 0     x 0   q  i for i in x 1  if i gt x 0      To see how we get there  first take our readable example  remove comments and docstrings  and find the pivot in-place   def quicksort xs       if xs           below    i for i in xs 1   if i  lt  xs 0            above    i for i in xs 1   if i  gt   xs 0           return quicksort below     xs 0     quicksort above      else           return xs   Now find below and above  in-place   def quicksort xs       if xs           return  quicksort  i for i in xs 1   if i  lt  xs 0                        xs 0                      quicksort  i for i in xs 1   if i  gt   xs 0         else           return xs   Now  knowing that and returns the prior element if false  else if it is true  it evaluates and returns the following element  we have   def quicksort xs       return xs and  quicksort  i for i in xs 1   if i  lt  xs 0                           xs 0                         quicksort  i for i in xs 1   if i  gt   xs 0       Since lambdas return a single epression  and we have simplified to a single expression  even though it is getting more unreadable  we can now use a lambda   quicksort   lambda xs   quicksort  i for i in xs 1   if i  lt  xs 0                                xs 0                              quicksort  i for i in xs 1   if i  gt   xs 0       And to reduce to our example  shorten the function and variable names to one letter  and eliminate the whitespace that isn t required   q lambda x x and q  i for i in x 1  if i lt  x 0     x 0   q  i for i in x 1  if i gt x 0      Note that this lambda  like most code golfing  is rather bad style   In-place Quicksort  using the Hoare Partitioning scheme  The prior implementation creates a lot of unnecessary extra lists  If we can do this in-place  we ll avoid wasting space   The below implementation uses the Hoare partitioning scheme  which you can read more about on wikipedia  but we have apparently removed up to 4 redundant calculations per partition   call by using while-loop semantics instead of do-while and moving the narrowing steps to the end of the outer while loop     def quicksort a list          Hoare partition scheme  see https   en wikipedia org wiki Quicksort        def  quicksort a list  low  high             must run partition on sections with 2 elements or more         if low  lt  high               p   partition a list  low  high               quicksort a list  low  p               quicksort a list  p 1  high      def partition a list  low  high           pivot   a list low          while True              while a list low   lt  pivot                  low    1             while a list high   gt  pivot                  high -  1             if low  gt   high                  return high             a list low   a list high    a list high   a list low              low    1             high -  1      quicksort a list  0  len a list -1      return a list   Not sure if I tested it thoroughly enough   def main        assert quicksort  1       1      assert quicksort  1 2       1 2      assert quicksort  1 2 3       1 2 3      assert quicksort  1 2 3 4       1 2 3 4      assert quicksort  2 1 3 4       1 2 3 4      assert quicksort  1 3 2 4       1 2 3 4      assert quicksort  1 2 4 3       1 2 3 4      assert quicksort  2 1 1 1       1 1 1 2      assert quicksort  1 2 1 1       1 1 1 2      assert quicksort  1 1 2 1       1 1 1 2      assert quicksort  1 1 1 2       1 1 1 2    Conclusion  This algorithm is frequently taught in computer science courses and asked for on job interviews  It helps us think about recursion and divide-and-conquer    Quicksort is not very practical in Python since our builtin timsort algorithm is quite efficient  and we have recursion limits  We would expect to sort lists in-place with list sort or create new sorted lists with sorted - both of which take a key and reverse argument

User · Answer

This answer is an in-place QuickSort for Python 2 x  My answer is an interpretation of the in-place solution from Rosetta Code which works for Python 3 too  import random  def qsort xs  fst  lst               Sort the range xs fst  lst  in-place with vanilla QuickSort       param xs   the list of numbers to sort      param fst  the first index from xs to begin sorting from                  must be in the range  0  len xs        param lst  the last index from xs to stop sorting at                 must be in the range  fst  len xs        return     nothing  the side effect is that xs fst  lst  is sorted             if fst  gt   lst          return      i  j   fst  lst     pivot   xs random randint fst  lst        while i  lt   j          while xs i   lt  pivot              i    1         while xs j   gt  pivot              j -  1          if i  lt   j              xs i   xs j    xs j   xs i              i  j   i   1  j - 1     qsort xs  fst  j      qsort xs  i  lst   And if you are willing to forgo the in-place property  below is yet another version which better illustrates the basic ideas behind quicksort  Apart from readability  its other advantage is that it is stable  equal elements appear in the sorted list in the same order that they used to have in the unsorted list   This stability property does not hold with the less memory-hungry in-place implementation presented above  def qsort xs       if not xs  return xs   empty sequence case     pivot   xs random choice range 0  len xs          head   qsort  x for x in xs if x  lt  pivot       tail   qsort  x for x in xs if x  gt  pivot       return head    x for x in xs if x    pivot    tail

User · Answer

Instead of taking three different arrays for less equal greater and then concatenating all  try the traditional concept partitioning method    http   pythonplanet blogspot in 2015 08 quick-sort-using-traditional-partition html  this is without using any inbuilt function   partitioning function -  def partitn alist  left  right      i left    j right    mid  left right  2     pivot alist mid    while i  lt   j        while alist i   lt  pivot            i i 1         while alist j   gt  pivot            j j-1         if i  lt   j            temp   alist i            alist i    alist j            alist j    temp           i   i   1            j   j - 1

User · Answer

The algorithm contains two boundaries  one having elements less than the pivot   tracked by index  j   and the other having elements greater than the pivot  tracked by index  i      In each iteration  a new element is processed by incrementing j   Invariant -    all elements between pivot and i are less than the pivot  and  all elements between i and j are greater than the pivot    If the invariant is violated  ith and jth elements are swapped  and i  is incremented    After all elements have been processed  and everything after the pivot  has been partitioned  the pivot element is swapped with the last element  smaller than it   The pivot element will now be in its correct place in the sequence  The  elements before it will be less than it and the ones after it will be  greater than it  and they will be unsorted   def quicksort sequence  low  high       if low  lt  high              pivot   partition sequence  low  high          quicksort sequence  low  pivot - 1          quicksort sequence  pivot   1  high   def partition sequence  low  high       pivot   sequence low      i   low   1     for j in range low   1  high   1           if sequence j   lt  pivot              sequence j   sequence i    sequence i   sequence j              i    1     sequence i-1   sequence low    sequence low   sequence i-1      return i - 1  def main sequence       quicksort sequence  0  len sequence  - 1      return sequence  if   name         main         sequence    -2  0  32  1  56  99  -4      print main sequence     Selecting a pivot  A  good  pivot will result in two sub-sequences of roughly the same  size  Deterministically  a pivot element can either be selected in a  naive manner or by computing the median of the sequence   A naive implementation of selecting a pivot will be the first or last  element  The worst-case runtime in this case will be when the input  sequence is already sorted or reverse sorted  as one of the subsequences  will be empty which will cause only one element to be removed per  recursive call   A perfectly balanced split is achieved when the pivot is the median element of the sequence  There are an equal number of elements greater  than it and less than it  This approach guarantees a better overall  running time  but is much more time-consuming   A non-deterministic random way of selecting the pivot would be to pick  an element uniformly at random  This is a simple and lightweight  approach that will minimize worst-case scenario and also lead to a  roughly balanced split  This will also provide a balance between the naive approach and the median approach of selecting the pivot

User · Answer

Probably just a preference thing  but I like to add validation to the top of my functions   def quicksort arr     if len arr   lt   1      return arr    left         right        equal        pivot   arr -1    for num in arr      if num  lt  pivot        left append num      elif num    pivot        equal append num      else        right append num     return quicksort left    equal   quicksort right

User · Answer

def quick sort array       return quick sort  x for x in array 1   if x  lt  array 0       array 0               quick sort  x for x in array 1   if x  gt   array 0    if array else

User · Answer

def quick sort l       if len l     0          return l     pivot   l 0      pivots    x for x in l if x    pivot      smaller   quick sort  x for x in l if x  lt  pivot       larger   quick sort  x for x in l if x  gt  pivot       return smaller   pivots   larger

User · Answer

Quick sort without additional memory  in place   Usage    array    97  200  100  101  211  107  quicksort array    array - gt   97  100  101  107  200  211    def partition array  begin  end       pivot   begin     for i in xrange begin 1  end 1           if array i   lt   array begin               pivot    1             array i   array pivot    array pivot   array i      array pivot   array begin    array begin   array pivot      return pivot    def quicksort array  begin 0  end None       if end is None          end   len array  - 1     def  quicksort array  begin  end           if begin  gt   end              return         pivot   partition array  begin  end           quicksort array  begin  pivot-1           quicksort array  pivot 1  end      return  quicksort array  begin  end

User · Answer

def quick sort self  nums       def helper arr           if len arr   lt   1  return arr          lwall is the index of the first element euqal to pivot          rwall is the index of the first element greater than pivot          so arr lwall rwall  is exactly the middle part equal to pivot after one round         lwall  rwall  pivot   0  0  0          choose rightmost as pivot         pivot   arr -1          for i  e in enumerate arr               if e  lt  pivot                   when element is less than pivot  shift the whole middle part to the right by 1                 arr i   arr lwall    arr lwall   arr i                  lwall    1                 arr i   arr rwall    arr rwall   arr i                  rwall    1             elif e    pivot                   when element equals to pivot  middle part should increase by 1                 arr i   arr rwall    arr rwall   arr i                  rwall    1             elif e  gt  pivot  continue         return helper arr  lwall     arr lwall rwall    helper arr rwall        return helper nums

User · Answer

This is a version of the quicksort using Hoare partition scheme and with fewer swaps and local variables  def quicksort array       qsort array  0  len array -1   def qsort A  lo  hi       if lo  lt  hi          p   partition A  lo  hi          qsort A  lo  p          qsort A  p   1  hi   def partition A  lo  hi       pivot   A lo      i  j   lo-1  hi 1     while True        i    1       j -  1       while A i   lt  pivot   i   1       while A j   gt  pivot    j-  1        if i  gt   j             return j        A i   A j    A j   A i    test    21  4  1  3  9  20  25  6  21  14  print quicksort test

User · Answer

Easy implementation from grokking algorithms  def quicksort arr       if len arr   lt  2          return arr  base case     else          pivot   arr 0          less    i for i in arr 1   if i  lt   pivot           more    i for i in arr 1   if i  gt  pivot          return quicksort less     pivot    quicksort more

[python] Quicksort with Python

Examples related to python

Examples related to algorithm

Examples related to sorting

Examples related to quicksort