package Ġalgorithms . sorting . radix _ sort Ċ Ċ import Ġalgorithms . sorting . In place Sort Ċ import Ġkotlin . math . log 1 0 ĊĊ Ċ class ĠRad ix Sort Ġ: ĠIn place Sort Ġ{ ĊĠĠĠ Ġoverride Ġfun Ġsort ( values : ĠInt Array ) Ġ{ ĊĠĠĠĠĠĠĠ Ġradix Sort ( values ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun ĠgetMax ( array : ĠInt Array ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġmax Ġ= Ġarray [ 0 ] ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġarray . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( array [ i ] Ġ> Ġmax ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmax Ġ= Ġarray [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġmax ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġcalculate NumberOf Digits ( number : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġlog 1 0 ( number . toDouble ()). toInt () Ġ+ Ġ 1 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠRequires Ġall Ġnumbers Ġto Ġbe Ġgreater Ġthan Ġor Ġequal Ġto Ġ 1 ĊĠĠĠ Ġfun Ġradix Sort ( numbers : ĠInt Array ?) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( numbers Ġ== Ġnull Ġ|| Ġnumbers . size Ġ<= Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġmaximum Ġ= ĠgetMax ( numbers ) ĊĠĠĠĠĠĠĠ Ġvar ĠnumberOf Digits Ġ= Ġcalculate NumberOf Digits ( maximum ) ĊĠĠĠĠĠĠĠ Ġvar Ġplace Value Ġ= Ġ 1 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( numberOf Digits -- Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcount Sort ( numbers , Ġplace Value ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġplace Value Ġ*= Ġ 1 0 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġcount Sort ( numbers : ĠInt Array , Ġplace Value : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġrange Ġ= Ġ 1 0 ĊĠĠĠĠĠĠĠ Ġval Ġfrequency Ġ= ĠInt Array ( range ) ĊĠĠĠĠĠĠĠ Ġval Ġsorted Values Ġ= ĠInt Array ( numbers . size ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġnumbers . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdigit Ġ= Ġnumbers [ i ] Ġ/ Ġplace Value Ġ% Ġrange ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfrequency [ digit ] ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 1 Ġuntil Ġrange ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfrequency [ i ] Ġ+= Ġfrequency [ i Ġ- Ġ 1 ] ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġnumbers . indices . reversed ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdigit Ġ= Ġnumbers [ i ] Ġ/ Ġplace Value Ġ% Ġrange ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsorted Values [ frequency [ digit ] Ġ- Ġ 1 ] Ġ= Ġnumbers [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfrequency [ digit ] -- ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ ĠSystem . arraycopy ( sorted Values , Ġ 0 , Ġnumbers , Ġ 0 , Ġnumbers . size ) ĊĠĠĠ Ġ} Ċ }