/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package radixsort2;

import java.util.LinkedList;
/**
 *
 * @author Diana
 */
public class RadixSort2 {
    LinkedList<LinkedList<Long>> hinkar;
    
    public RadixSort2(){
        hinkar = new LinkedList<LinkedList<Long>>();
        for(int i=0; i<10; i++){
            hinkar.add(new LinkedList<Long>());
        }
    }

    public static void main(String[] args) {
        RadixSort2 sorter = new RadixSort2();
        long[] arr = {1,2,10,20,21,22,23};
        //long[] arr = {1,2};
        sorter.sort(arr);
        System.out.println(java.util.Arrays.toString(arr));
    }
    
    public void sort(long[] array){
        //Skapa en kopia av arrayen men med Long-objekt
        Long[] larray = new Long[array.length];
        
        //Kopiera innehållet i array till larray, fast i objektform
        for(int n=0; n<array.length; n++){
            Long lo = new Long(array[n]);
            larray[n] = lo;
        }
        
        
        for(int digitNumber = 0; digitNumber<10; digitNumber++){
            //Töm hinkarna, så att de är tomma vid starten på varje varv
            hinkar = new LinkedList<LinkedList<Long>>();
            for(int i=0; i<10; i++){
                hinkar.add(new LinkedList<Long>());
            }
            
            //Lägg tal-objekten i rätt "hink"
            for(int i=0; i<larray.length; i++){
                Long tal = larray[i];
                //I första varvet blir digit sista siffran,
                //Nästa varv blir digit näst sista siffran osv...
                int base = (int)Math.pow(10,digitNumber);
                int digit = (int)((tal/base)%10); 
                LinkedList<Long> hink = hinkar.get(digit);
                hink.add(tal);
            }

            //Töm larray genom att initiera om 
            larray = new Long[array.length];

            //Lägg tillbaka talen i larray igen, i den nya ordningen
            int index = 0;
            for(int i=0; i<10; i++){ //loopa igenom tio varv eftersom det finns så många siffror
                LinkedList<Long> hink = hinkar.get(i);
                for(int k=0; k<hink.size(); k++){
                    Long tal = hink.get(k);
                    larray[index++] = tal;
                }
            }
        }
        
        //Kopiera larray till ursprungliga arrayen
        for(int n=0; n<array.length; n++){
            array[n] = larray[n];
        }
        
    }
   
    
}