package Ġcom . f reak lius . kotlin . algorithms . sort Ċ Ċ import Ġjava . util . LinkedList Ċ Ċ /** Ċ Ġ* ĠBucket Ġsort Ġalgorithm Ċ Ġ* ĠAverage Ġperformance Ġ= ĠO ( n ) Ċ Ġ*/ Ċ public Ġclass ĠBucket Sort Ġ: ĠSort Algorithm Ġ{ ĊĊĠĠĠ Ġpublic Ġoverride Ġfun Ġsort ( arr : ĠArray < Long >): ĠArray < Long > Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Number Ġof Ġbuckets Ġcan Ġdepend Ġon Ġinput Ġarray Ġsize ĊĠĠĠĠĠĠĠ Ġvar ĠnumberOf Buckets Ġ= Ġif Ġ( arr . size Ġ> Ġ 1 0 0 ) ĠMath . floor ( arr . size Ġ/ Ġ 1 0 . 0 ). toInt () Ġelse Ġ 1 0 ; ĊĠĠĠĠĠĠĠ Ġvar Ġoutput Array Ġ= Ġarr ; ĊĠĠĠĠĠĠĠ Ġvar Ġsort Array Ġ= ĠArray < LinkedList < Long >>( numberOf Buckets , Ġ{ i Ġ-> ĠLinkedList () }); Ġ// We Ġneed Ġto Ġstore Ġdigits Ġin Ġrange Ġ 0 .. 9 ĊĠĠĠĠĠĠĠ Ġvar Ġmax Array Value Ġ= Ġmaximum ( arr ); ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. arr . size Ġ- Ġ 1 ){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġvalue Ġ= Ġarr [ i ]; ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġvalue Index Ġ= ĠMath . floor (( numberOf Buckets Ġ* Ġ( value Ġ/ Ġmax Array Value )). toDouble ()). toInt (); Ġ// ĠIt 's Ġa Ġnumber Ġin Ġrange Ġ 0 .. 9 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( value Index Ġ== Ġarr . size ){ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvalue Index Ġ= Ġarr . size Ġ- Ġ 1 ; Ġ// Maximum Ġvalues Ġgo Ġto Ġthe Ġlast Ġbucket ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsort Array [ value Index ]. add ( value ); ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġvar Ġoutput ArrayIndex Ġ= Ġ 0 ; ĊĠĠĠĠĠĠĠ Ġfor Ġ( list Ġin Ġsort Array ){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( list . size () Ġ> Ġ 0 ){ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġarray From List Ġ= ĠArray < Long >( list . size (), Ġ{ i Ġ-> Ġlist . get ( i )}); ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( value Ġin ĠInsert ion Sort (). sort ( array From List )){ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġoutput Array [ output ArrayIndex ] Ġ= Ġvalue ; ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġoutput ArrayIndex ++; ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġoutput Array ; ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġpublic Ġoverride Ġfun ĠgetName (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġ" Bucket Sort "; ĊĠĠĠ Ġ} Ċ }