object ĠQuick Sort Ġ{ ĊĊĠĠĠ Ġ// Ġ ĠThis Ġmethod Ġf oll ws Ġthe Ġstandard Ġapproach , Ġmirror ing Ġthat Ġof Ġthe Ġjava Ġimplementation ĊĠĠĠ Ġ// Ġ ĠDeclare Ġmethod Ġto Ġperform Ġthe Ġsort , Ġtaking Ġan Ġarray Ġas Ġparam ĊĠĠĠ Ġfun Ġquick Sort Alpha ( arr : ĠInt Array , Ġfirst Index : ĠInt , Ġlast Index : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġ ĠQuick Ġsort : ĠSelect s Ġan Ġindex Ġ( pivot ) Ġand Ġsorts Ġaround Ġit , Ġmeaning Ġthat Ġall Ġleft Ġitems Ġare Ġless er Ġand ĊĠĠĠĠĠĠĠ Ġ// Ġ Ġall Ġright Ġitems Ġare Ġlarger . ĠThis Ġis Ġperformed Ġrecursively Ġon Ġeither Ġside Ġof Ġthe Ġpivot ĊĠĠĠĠĠĠĠ Ġ// Ġ ĠTime ĠComplex ity : ĠBest Ġ- ĠO ( n Ġlog 2 Ġn ) ĠAverage Ġ- ĠO ( n Ġlog 2 Ġn ) ĠW or st Ġ- ĠO ( n ^ 2 ) ĊĊĠĠĠĠĠĠĠ Ġ// Ġ ĠDeclare Ġi , Ġj , Ġpivot , Ġand Ġtemp Ġas Ġintegers ĊĠĠĠĠĠĠĠ Ġvar Ġi : ĠInt ĊĠĠĠĠĠĠĠ Ġvar Ġj : ĠInt ĊĠĠĠĠĠĠĠ Ġval Ġpivot : ĠInt ĊĠĠĠĠĠĠĠ Ġval Ġtemp : ĠInt ĊĊĠĠĠĠĠĠĠ Ġ// Ġ ĠVerify Ġthat Ġa Ġvalid Ġrange Ġhas Ġbeen Ġgiven / Ġthat Ġthe Ġindices Ġdo Ġnot Ġmatch ĊĠĠĠĠĠĠĠ Ġ// Ġ ĠWhen Ġthe Ġindices Ġmatch , Ġthere Ġwill Ġonly Ġbe Ġ 1 Ġitem Ġin Ġthe Ġarray Ġto Ġsort ĊĠĠĠĠĠĠĠ Ġif Ġ( first Index Ġ< Ġlast Index ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠSelect Ġa Ġvalue Ġto Ġpivot Ġaround , Ġin Ġthis Ġcase Ġthe Ġfirst Ġindex Ġis Ġselected ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠThis Ġis Ġnot Ġalways Ġideal , Ġhowever Ġin Ġmany Ġcases Ġthis Ġis Ġfine ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpivot Ġ= Ġfirst Index ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠSet Ġvalues Ġfor Ġiterators Ġi Ġand Ġj ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi Ġ= Ġfirst Index ĊĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ= Ġlast Index ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠWh il st Ġi Ġis Ġless Ġthan Ġj , Ġmake Ġcomparisons Ġthat Ġclose Ġaround Ġthe Ġpivot ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< Ġj ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠWh il st Ġthe Ġvalue Ġat Ġindex Ġi Ġis Ġless Ġthan Ġor Ġequal Ġto Ġthat Ġof Ġthe Ġpivot ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ Ġand Ġi Ġis Ġless Ġthan Ġthe Ġend Ġof Ġthe Ġarray , Ġincrement Ġi ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( arr [ i ] Ġ<= Ġarr [ pivot ] Ġ&& Ġi Ġ< Ġlast Index ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠWh il st Ġthe Ġvalue Ġat Ġindex Ġj Ġis Ġlarger Ġthan Ġthat Ġat Ġthe Ġpivot , Ġdecrement Ġj ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( arr [ j ] Ġ> Ġarr [ pivot ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠIf Ġi Ġis Ġless Ġthan Ġj , Ġswap Ġthe Ġvalues Ġat Ġthe Ġindex Ġlocations ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠAs Ġprior Ġloops Ġfilter Ġuntil Ġa Ġswap Ġis Ġneeded , Ġthis Ġis Ġwhere Ġthe Ġswap Ġtakes Ġplace ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( i Ġ< Ġj ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġarr [ i ] Ġ= Ġarr [ i ] Ġ+ Ġarr [ j ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġarr [ j ] Ġ= Ġarr [ i ] Ġ- Ġarr [ j ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġarr [ i ] Ġ= Ġarr [ i ] Ġ- Ġarr [ j ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠUpdate Ġthe Ġvalue Ġof Ġthe Ġpivot Ġindex ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠNOTE : ĠArithmetic Ġsw apping Ġhere Ġcauses Ġerr one ous Ġresults , Ġpossibly Ġdue Ġto Ġoverlapping Ġvalues ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtemp Ġ= Ġarr [ pivot ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġarr [ pivot ] Ġ= Ġarr [ j ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġarr [ j ] Ġ= Ġtemp ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠAs Ġthe Ġpivot Ġshould Ġnow Ġbe Ġplaced Ġcorrectly , Ġsort Ġthe Ġsub arrays Ġon Ġeither Ġside Ġof Ġit ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquick Sort Alpha ( arr , Ġfirst Index , Ġj Ġ- Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquick Sort Alpha ( arr , Ġj Ġ+ Ġ 1 , Ġlast Index ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// Ġ ĠThis Ġapproach Ġis Ġmore Ġeleg ant Ġand Ġutil ises Ġfunctions Ġbuilt Ġinto Ġthe ĠKotlin Ġlanguage Ġto Ġspeed Ġup Ġthe Ġprocess ĊĠĠĠ Ġ// Ġ ĠThis Ġfunction Ġdoes Ġnot Ġwork Ġin Ġplace , Ġhowever Ġcould Ġbe Ġadjusted Ġto Ġalter Ġthe Ġarray Ġin Ġplace Ġin Ġa Ġfuture Ġversion ĊĠĠĠ Ġfun Ġquick Sort Beta ( arr : ĠInt Array ): ĠInt Array Ġ{ ĊĊĠĠĠĠĠĠĠ Ġ// Ġ ĠVerify Ġthat Ġthe Ġarray Ġis Ġnot Ġempty Ġ( this Ġuses Ġthe Ġin built Ġis NotEmpty Ġfunction ) ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( arr . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠDefine Ġthe Ġpivot Ġto Ġuse Ġthe Ġvalue Ġat Ġthe Ġstart Ġof Ġthe ĠintArray ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpivot Ġ= Ġarr [ 0 ] ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠUse Ġthe Ġfilter Ġmethod Ġto Ġextract Ġall Ġvalues Ġthat Ġare Ġequal Ġto Ġthe Ġpivot ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ Ġand Ġconvert Ġthe Ġresult ant Ġlist Ġto Ġan ĠintArray ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġequal Ġ= Ġarr . filter Ġ{ Ġit Ġ== Ġpivot Ġ}. to IntArray () ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠUse Ġthe Ġfilter Ġmethod Ġto Ġextract Ġall Ġvalues Ġthat Ġare Ġless Ġthan Ġthe Ġpivot ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ Ġand Ġconvert Ġthe Ġresult ant Ġlist Ġto Ġan ĠintArray ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġless Ġ= Ġarr . filter Ġ{ Ġit Ġ< Ġpivot Ġ}. to IntArray () ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠUse Ġthe Ġfilter Ġmethod Ġto Ġextract Ġall Ġvalues Ġthat Ġare Ġlarger Ġthan Ġthe Ġpivot ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ Ġand Ġconvert Ġthe Ġresult ant Ġlist Ġto Ġan ĠintArray ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlarger Ġ= Ġarr . filter Ġ{ Ġit Ġ> Ġpivot Ġ}. to IntArray () ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠRe cursively Ġapply Ġthe Ġfunction Ġto Ġthe Ġless Ġand Ġlarger Ġint Arrays ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠThis Ġwill Ġrepeat Ġuntil Ġthe Ġarray Ġis Ġempty , Ġat Ġwhich Ġpoint Ġall Ġsorting Ġwill Ġbe Ġdone ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠBuild Ġa Ġfinal ĠintArray Ġby Ġconcaten ating Ġthe Ġless er Ġvalues , Ġequal Ġvalues , Ġand Ġlarger Ġvalues ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquick Sort Beta ( less ) Ġ+ Ġequal Ġ+ Ġquick Sort Beta ( l arger ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠIf Ġthe Ġarray Ġis Ġempty , Ġreturn Ġthe Ġarray ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠThis Ġwill Ġavoid Ġan Ġinfinite Ġrecursion ĊĠĠĠĠĠĠĠĠĠĠĠ Ġarr ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ