package Ġcom . your tion . sort Ċ Ċ import Ġcom . your tion . list . List Ċ import Ġcom . your tion . utils . swap Ċ Ċ /** Ċ Ġ* ĠQuick ĠSort Ċ Ġ* ĠCreated Ġby ĠYour tion Ġon Ġ 1 3 / 0 6 / 2 0 1 7 . Ċ Ġ*/ Ċ Ċ private Ġfun Ġ< T > ĠMutable List < T >. partition ( i : ĠInt , Ġk : ĠInt , Ġc : ĠComparator < T >): ĠInt Ġ{ ĊĠĠĠ Ġval Ġr 0 Ġ= ĠList ( 3 , Ġ{ Ġ( Math . random () Ġ* Ġ( k Ġ- Ġi Ġ+ Ġ 1 ) Ġ+ Ġi ). toInt () Ġ}) ĊĠĠĠ Ġval Ġr Ġ= Ġthis [ r 0 . sorted ()[ 1 ]] ĊĠĠĠ Ġvar Ġi 0 Ġ= Ġi Ġ- Ġ 1 ĊĠĠĠ Ġvar Ġk 0 Ġ= Ġk Ġ+ Ġ 1 ĊĊĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠ Ġdo Ġk 0 -- ĊĠĠĠĠĠĠĠ Ġwhile Ġ( c . compare ( this [ k 0 ], Ġr ) Ġ> Ġ 0 ) ĊĊĠĠĠĠĠĠĠ Ġdo Ġi 0 ++ ĊĠĠĠĠĠĠĠ Ġwhile Ġ( c . compare ( this [ i 0 ], Ġr ) Ġ< Ġ 0 ) ĊĊĠĠĠĠĠĠĠ Ġif Ġ( i 0 Ġ>= Ġk 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis . swap ( i 0 , Ġk 0 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġreturn Ġk 0 Ċ } Ċ Ċ /** Ċ Ġ* Ġ å¿«éĢŁ æİĴåºı Ċ Ġ*/ Ċ fun Ġ< T > ĠMutable List < T >. qk _ sort ( c : ĠComparator < T >, Ġi : ĠInt Ġ= Ġ 0 , Ġk : ĠInt Ġ= Ġthis . size Ġ- Ġ 1 ) Ġ{ ĊĠĠĠ Ġif Ġ( i Ġ< Ġk ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġj Ġ= Ġthis . partition ( i , Ġk , Ġc ) ĊĠĠĠĠĠĠĠ Ġthis . qk _ sort ( c , Ġi , Ġj ) ĊĠĠĠĠĠĠĠ Ġthis . qk _ sort ( c , Ġj Ġ+ Ġ 1 , Ġk ) ĊĠĠĠ Ġ} Ċ } Ċ Ċ /** Ċ Ġ* Ġ å¿«éĢŁ æİĴåºı Ċ Ġ*/ Ċ fun Ġ< E > ĠIterable < E >. qk _ sort ( comparator : ĠComparator < E >): ĠList < E > Ġ{ ĊĠĠĠ Ġval Ġres : ĠMutable List < E > Ġ= Ġmutable ListOf () ĊĠĠĠ Ġthis . forEach ({ Ġit Ġ-> Ġres . add ( it ) Ġ}) ĊĠĠĠ Ġres . qk _ sort ( comparator ) ĊĠĠĠ Ġval Ġresult Ġ= ĠList < E >() ĊĠĠĠ Ġres . forEach Ġ{ Ġit Ġ-> Ġresult . insert _ next ( it , Ġresult . tail ) Ġ} ĊĠĠĠ Ġreturn Ġresult Ċ } Ċ