package Ġsort Ċ Ċ import Ġvisual .* Ċ Ċ class ĠQuick Sort < T Ġ: ĠComparable < T >>( val Ġvisual : ĠVisual Function Ġ= ĠBasic Visual Function ()) Ġ{ ĊĊĠĠĠ Ġfun Ġsort ( list : ĠMutable List < T >, Ġleft Idx : ĠInt Ġ= Ġ 0 , Ġright Idx : ĠInt Ġ= Ġlist . size Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvisual . enter (" sort ", Ġ" left Idx : Ġ$ left Idx Ġright Idx : Ġ$ right Idx ") ĊĊĠĠĠĠĠĠĠ Ġif Ġ( left Idx Ġ>= Ġright Idx ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvisual . exit () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġval Ġindex Ġ= Ġpartition ( list , Ġleft Idx , Ġright Idx ) ĊĠĠĠĠĠĠĠ Ġif Ġ( index Ġ> Ġleft Idx ) Ġsort ( list , Ġindex Ġ- Ġ 1 , Ġright Idx ) ĊĠĠĠĠĠĠĠ Ġif Ġ( index Ġ< Ġright Idx ) Ġsort ( list , Ġindex Ġ+ Ġ 1 , Ġright Idx ) ĊĊĠĠĠĠĠĠĠ Ġvisual . exit () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġpartition ( list : ĠMutable List < T >, Ġleft Idx : ĠInt , Ġright Idx : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvisual . enter (" partition ", Ġ" left Idx : Ġ$ left Idx Ġright Idx : Ġ$ right Idx ") ĊĊĠĠĠĠĠĠĠ Ġvar Ġcur Left Ġ= Ġleft Idx ĊĠĠĠĠĠĠĠ Ġvar Ġcur Right Ġ= Ġright Idx ĊĠĠĠĠĠĠĠ Ġval Ġpartition Ġ= Ġlist [( left Idx Ġ+ Ġright Idx ) Ġ/ Ġ 2 ] ĊĊĠĠĠĠĠĠĠ Ġwhile Ġ( cur Left Ġ< Ġcur Right ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( list [ cur Left ] Ġ< Ġpartition ) Ġcur Left ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( list [ cur Right ] Ġ> Ġpartition ) Ġcur Right -- ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cur Left Ġ<= Ġcur Right ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtmp Ġ= Ġlist [ cur Left ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlist [ cur Left ] Ġ= Ġlist [ cur Right ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlist [ cur Right ] Ġ= Ġtmp ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcur Left ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcur Right -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġvisual . exit () ĊĠĠĠĠĠĠĠ Ġreturn Ġleft Idx ĊĠĠĠ Ġ} Ċ Ċ } Ċ // Ġsimplest Ġsolution Ġbut Ġnot Ġin - place Ċ // fun Ġ< T Ġ: ĠComparable < T >> Ġquick sort ( items : ĠList < T >): ĠList < T > Ġ{ Ċ // ĠĠĠ Ġif Ġ( items . count () Ġ< Ġ 1 ) Ġreturn Ġitems Ċ // ĠĠĠ Ġval Ġpivot Ġ= Ġitems [ items . count () Ġ/ Ġ 2 ] Ċ // ĠĠĠ Ġval Ġequal Ġ= Ġitems . filter Ġ{ Ġit Ġ== Ġpivot Ġ} Ċ // ĠĠĠ Ġval Ġless Ġ= Ġitems . filter Ġ{ Ġit Ġ< Ġpivot Ġ} Ċ // ĠĠĠ Ġval Ġgreater Ġ= Ġitems . filter Ġ{ Ġit Ġ> Ġpivot Ġ} Ċ // ĠĠĠ Ġreturn Ġquick sort ( less ) Ġ+ Ġequal Ġ+ Ġquick sort ( greater ) Ċ //}