package Ġcom . kot ling round . algorithms . sorting . quick sort Ċ Ċ // Ġpartitions Ġa Ġslice Ġinto Ġ 2 Ġand Ġreturns Ġthe Ġpivot Ġindex . ĠAss umes Ġthe Ġpivot Ġis Ġat Ġthe Ġend Ġof Ġthe Ġslice Ċ fun Ġpartition ( the Array : ĠInt Array , ĠstartIndex : ĠInt , Ġend Index : ĠInt ): ĠInt Ġ{ ĊĊĠĠĠ Ġval Ġpivot Ġ= Ġthe Array [ end Index ] ĊĊĠĠĠ Ġvar Ġleft Index Ġ= ĠstartIndex ĊĠĠĠ Ġvar Ġright Index Ġ= Ġend Index Ġ- Ġ 1 ĊĊĠĠĠ Ġwhile Ġ( left Index Ġ<= Ġright Index ) Ġ{ ĊĊĠĠĠĠĠĠĠ Ġ// Ġwalk Ġuntil Ġwe Ġfind Ġsomething Ġon Ġthe Ġleft Ġside Ġthat Ġbelongs Ġon Ġthe Ġright Ġ( less Ġthan Ġthe Ġpivot ) ĊĠĠĠĠĠĠĠ Ġwhile Ġ( left Index Ġ<= Ġend Index Ġ&& Ġthe Array [ left Index ] Ġ< Ġpivot ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft Index ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// Ġwalk Ġuntil Ġwe Ġfind Ġsomething Ġon Ġthe Ġright Ġside Ġthat Ġbelongs Ġon Ġthe Ġleft ( greater Ġthan Ġor Ġequal Ġto Ġthe Ġpivot ) ĊĠĠĠĠĠĠĠ Ġwhile Ġ( right Index Ġ>= ĠstartIndex Ġ&& Ġthe Array [ right Index ] Ġ>= Ġpivot ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġright Index -- ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġif Ġ( left Index Ġ< Ġright Index ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġswap Ġthe Ġitems Ġat Ġthe Ġleft _ index Ġand Ġright _ index , Ġmoving Ġthe Ġelement Ġthat 's Ġsmaller Ġthan Ġthe Ġpivot Ġto ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthe Ġleft ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġhalf Ġand Ġthe Ġelement Ġthat 's Ġlarger Ġthan Ġthe Ġpivot Ġto Ġthe Ġright Ġhalf ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtemp Ġ= Ġthe Array [ left Index ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthe Array [ left Index ] Ġ= Ġthe Array [ right Index ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthe Array [ right Index ] Ġ= Ġtemp ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġunless Ġwe Ġhave Ġlooked Ġat Ġall Ġthe Ġelements Ġin Ġthe Ġlist Ġand Ġare Ġdone Ġpartition ing . ĠIn Ġthat Ġcase , Ġmove Ġthe ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġpivot Ġelement ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġinto Ġit 's Ġfinal Ġposition ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtemp Ġ= Ġthe Array [ left Index ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthe Array [ left Index ] Ġ= Ġthe Array [ end Index ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthe Array [ end Index ] Ġ= Ġtemp ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġreturn Ġleft Index Ċ } Ċ Ċ // Ġquick sort Sub Array Ġuses Ġrecur st ion Ġto Ġsort Ġeach Ġpartition Ġof Ġthe Ġslice Ċ fun Ġquick sort Sub Array ( the Array : ĠInt Array , ĠstartIndex : ĠInt , Ġend Index : ĠInt ) Ġ{ ĊĊĠĠĠ Ġ// Ġbase Ġcase , Ġlist Ġwith Ġ 0 Ġor Ġ 1 Ġelement ĊĠĠĠ Ġif Ġ( startIndex Ġ>= Ġend Index ) Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// Ġdivide Ġthe Ġlist Ġinto Ġ 2 Ġsmaller Ġsub lists ĊĠĠĠ Ġval Ġpivot Index Ġ= Ġpartition ( the Array , ĠstartIndex , Ġend Index ) ĊĊĠĠĠ Ġ// ĠRe cursively Ġsort Ġeach Ġsub list ĊĠĠĠ Ġquick sort Sub Array ( the Array , ĠstartIndex , Ġpivot Index Ġ- Ġ 1 ) ĊĠĠĠ Ġquick sort Sub Array ( the Array , Ġpivot Index Ġ+ Ġ 1 , Ġend Index ) Ċ } Ċ Ċ // Ġquick sort Ġsorts Ġa Ġslice Ġof Ġintegers Ġusing Ġquick sort Ġalgorithm Ċ fun Ġquick sort ( the Array : ĠInt Array ): ĠInt Array Ġ{ ĊĠĠĠ Ġval Ġlength Ġ= Ġthe Array . size ĊĊĠĠĠ Ġ// ĠNothing Ġto Ġsort Ġhere ĊĠĠĠ Ġif Ġ( length Ġ<= Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġthe Array ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġquick sort Sub Array ( the Array , Ġ 0 , Ġlength Ġ- Ġ 1 ) ĊĠĠĠ Ġreturn Ġthe Array Ċ } Ċ