Einfaldasta framsetning á Quicksort sem ég hef séð

Þetta er alger nerdafærsla en ..  ég hef sjaldan séð snaggaralegri framsetningu á Quicksort.   Þetta er skrifað í Python:

def qsort(L):
    if L == []:
        return []
    pivot = L[0]
    return (qsort([x for x in L[1:] if x < pivot]) +
            [pivot] +
            qsort([x for x in L[1:] if x >= pivot]))


qsort([3,1,4,1,5,2,7])
[1, 1, 2, 3, 4, 5, 7]
>>>

Athugasemdir

[Ra (IP-tala skráð) 17.11.2009 kl. 16:13]

List comprehension ROCKS!

Stutt en auðskilið.

 Hægt að setja í 2 línur sýnist mér en það er ekki eins læsilegt:

def qsort(L):
    if L == []: return []
    return (qsort([x for x in L[1:] if x < L[0]])+[L[0]]+qsort([x for x in L[1:] if x >= L[0]]))

[Kári Harðarson, 17.11.2009 kl. 16:35]

Til samanburðar, hér er Quicksort í BASIC.  Svona sá ég quicksort fyrst.

10  REM     Written 8/28/85;  by James Haley
20  REM     non-recursive quicksort in basic
30  REM
40  OPTION BASE 1          &#39; all arrays start with 1, not zero
50  DEFINT A-Z             &#39; make all variables integers
60  DIM VECTOR(10000)        &#39; the array to be sorted
70  DIM STACK.LEFT(32)     &#39; keeps track of what to sort
80  DIM STACK.RIGHT(32)    &#39; keeps track of what to sort
90  REM
100  REM    read in an array to sort
110  REM    SORT.NUM contains the number of things to sort
120  REM
130  SORT.NUM = 0
140 INPUT "how many elements do you want to sort ";COUNT
150 FOR K = 1 TO COUNT
160    SORT.NUM = SORT.NUM + 1
170    VECTOR(SORT.NUM) = INT(RND*1000)
180 NEXT K
190 PRINT TIME$
200 REM
210 REM initialize the stack
220 REM
230 STACK.POINTER = 1
240 STACK.LEFT(STACK.POINTER) = 1         &#39; this is the first thing to sort
250 STACK.RIGHT(STACK.POINTER) = SORT.NUM &#39; this is the last thing to sort
260 REM
270 REM get the right and left limits of the array to sort from the stack
280 REM top of sort loop
290 REM
300   LEFT = STACK.LEFT(STACK.POINTER)
310   RIGHT = STACK.RIGHT(STACK.POINTER)
320   STACK.POINTER = STACK.POINTER - 1
330   REM
340   REM decide if this partition is sorted
350   REM
360   IF LEFT >= RIGHT THEN IF STACK.POINTER > 0 THEN GOTO 300 ELSE GOTO 570
370   REM
380   REM partition the array around the pivot
390   REM
400   I = LEFT
410   J = RIGHT + 1
420   PIVOT = VECTOR( LEFT )
430      J = J - 1 : IF VECTOR(J) > PIVOT GOTO 430
440      I = I + 1 : IF (VECTOR(I) < PIVOT) AND (I < RIGHT) GOTO 440
450      IF I < J THEN SWAP VECTOR(I), VECTOR(J)  : GOTO 430
460   SWAP  VECTOR(LEFT), VECTOR(J)
470   REM
480   REM set up stack for the sub-partitions
490   REM
500   STACK.POINTER = STACK.POINTER + 1     &#39; increment the stack
510   STACK.LEFT(STACK.POINTER) = J + 1     &#39; for the right side
520   STACK.RIGHT(STACK.POINTER) = RIGHT    &#39; partition
530   STACK.POINTER = STACK.POINTER + 1     &#39; increment the stack
540   STACK.LEFT(STACK.POINTER) = LEFT      &#39; for the left side
550   STACK.RIGHT(STACK.POINTER) = J - 1    &#39; partition
560   GOTO 300     &#39; go back and sort the next sub-partition
570 PRINT TIME$
580 REM
590 REM sort finished, print out the sorted array
600 REM
610 FOR K = 1 TO SORT.NUM
620   PRINT VECTOR(K);
630 NEXT K : PRINT
&#26;                                                                               

[Guðmundur Ásgeirsson, 17.11.2009 kl. 17:04]

Sæl Kári.

Þetta er svo sannarlega hnitmiðuð útfærsla á QuickSort algríminu. Lykilatriði í þessu er hversu einfalt er að flokka stökin eftir því hvort þau eru stærri eða minni en "pivot" stakið. Svipaða eiginleika má líka finna í nýjustu kynslóð af C# með sk. LINQ eða "Language INtegrated Query". Sambærileg útfærsla á QuickSort fallinu í C# gæti því litið út einhvernveginn svona (með fyrirvara, þetta er óprófað):

public static object[] qsort(object[] L)

{

  if (L.Length == 0) return new object[0];

  object pivot = L[0];

  object[] notpivot = new object[L.Length - 1];

  L.CopyTo(notpivot, 1);

  object[] low = (from o in notpivot where o < pivot select o).ToArray();

  object[] high = (from o in notpivot where o >= pivot select o).ToArray();

  return

    qsort(low).Concat(new object[] {pivot}).Concat(qsort(high)).ToArray();

}

P.S. Einfaldasta leiðin til að raða með QuickSort í C# er hinsvegar:

Array.Sort(L);    

Bestu kveðjur.

[Carlos Ferrer (IP-tala skráð) 17.11.2009 kl. 17:28]

Loksins, loksins blogg eins Guð ætlaðist til að það væri notað þegar hún skapaði það!

[Kári Harðarson, 17.11.2009 kl. 21:05]

Maður að vestan sendi þetta inn:

Dýrt er einnig kveðið í Ruby:

def sort(array)
  return [] if array.empty?
  left, right = array[1..-1].partition { |y| y <= array.first }
  sort(left) + [ array.first ] + sort(right) end

[Kama Sutra, 18.11.2009 kl. 03:39]

[Ágúst H Bjarnason, 18.11.2009 kl. 08:35]

Eiginlega finnst mér BASIC útfærslan auðskildari

Hvernig skyldi þetta vera í FORTRAN og ALGOL sem ég lærði í HÍ (á IBM-1620) og LTH í den... 

[Kári Harðarson, 18.11.2009 kl. 09:30]

Úlfar Erlingsson sendi mér þetta í tölvupósti:

Inspirerad af faerslu Gudmundar.  Thetta her ad nedan er generic, og strongly typed, og svipad laesilegt og Pythonid (en tho ekkert hradvirkara).
 

IEnumerable<T>

qsort<T>(IEnumerable<T> L) where T : IComparable<T>

{
    if (L.Count() <= 1) return L;

    T pivot = L.First();

    var low = from x in L where x.CompareTo(pivot) < 0 select x;
    var high = from y in L where 0 < y.CompareTo(pivot) select y;

    return qsort(low)
           .Concat(new T[] { pivot })
           .Concat(qsort(high));
}

 

Til samanburdar vid BASIC utgafuna, tha vaeri skemmtilegt ad sja folk reyna ad skrifa skiljanlegan non-recursive koda i sinu uppahalds forritunarmali.  En i thvi samhengi verdur lika ad geta thess ad Leslie Lamport keyrdi fyrir nokkrum arum QuickSort af haskolakennslusidum i gegnum TLC model-checkerinn sinn--og 18 af 20 utgafum voru vitlausar!  Thannig ad einfalt, laesilegt, og rett er kannski best, tho thad se inefficient.  :-)

[Árni Már (IP-tala skráð) 18.11.2009 kl. 10:10]

Haskell (sama hugmynd og Python útfærslan):

qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Hér er líka bráðskemmtilegur fyrirlestur með Bentley, þar sem hann er í gegnum 3 útgáfur sem taka á veikleikum fyrri útfærslna:

http://www.youtube.com/watch?v=aMnn0Jq0J-E

Einhver skemmtilegasti tölvunarfræðifyrirlestur sem ég hef séð.

[Lára Hanna Einarsdóttir, 18.11.2009 kl. 15:49]

Ég ætla ekki einu sinni að þykjast botna í ykkur! 

[Guðmundur Ásgeirsson, 18.11.2009 kl. 18:31]

Þakka Úlfari Erlingssyni fyrir vandaða framsetningu á C# hugmyndinni. IEnumerable og generics er auðvitað miklu "nútímalegra" en að nota hrá fylki enda var þetta líka bara uppkast hjá mér, en þarna sjást kannski merki þess að ég lærði hlutbundna forritun fyrst í C++.

[, 19.11.2009 kl. 11:51]

Takk fyrir aðvörunina í byrjun færslunnar. Ég er alveg örugglega ekki nörd - skildi ekki staf í þessu  

[Einar Indriðason, 26.11.2009 kl. 09:06]

í perl:

@arr = sort(@arr); 

:-)

[Einar Jón, 2.12.2009 kl. 15:51]

Snyrtilegt.

Nú kann ég ekkert á Python, en er fljótlegra að fara alltaf niður í "tómt fylki" frekar en að hætta þegar það er eitt stak eftir? Það virðist vera hellingur af óþarfa köllum í qsort([]).

Þ.e.:
    if L.size() <= 1: // eða eitthvað álíka til að finna stærðina
        return L

í stað:
    if L == []:
        return []

Eða er þetta bara einfaldara svona?

[Kári Harðarson, 2.12.2009 kl. 21:18]

Góð spurning Einar,  kóðinn er jafn snyrtilegur með þinni framsetningu og sennilega fljótlegri, sparar amk. óþarfa fallakall.