Question

Java code: Use Radix sort to sort them in alphabetic order. How many passes would be made through the outer while loop? Trace the contents of the list after each of these passes.

Define the efficiency of the following code fragment:

            K := 1

            repeat  

                  J := 1

                        repeat

                             ……..

                             J := J * 2

                        until J >= N

                        K := K + 1

               until K >= N

Answer 1

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class RadixSort {
        public static void main(String[]args) throws FileNotFoundException{
                Linkedlist[] allNameLinkedList = new Linkedlist[26]; // create an array of LinkedList for 26 letters in alphabets
                int count = 0;
                // initialize all the elements in the array to new LinkedList
                for (int i = 0; i < allNameLinkedList.length; i++) {
                        allNameLinkedList[i] = new Linkedlist();
                }
                Scanner scan = new Scanner(new File("radixnames.txt"));
                
                // Put the names in the file according to their third character into the corresponding LinkedLists
                // For example, "Zachary" would go to to allNameLinkedList[2]
                while(scan.hasNextLine())
                {
                        String currentname = scan.nextLine();
                        for(int i = 0; i < 26; i++){
                                if(currentname.charAt(2) == (char)(i+97))
                                {
                                        allNameLinkedList[i].addNodeToTheEndOfTheList(currentname);
                                }
                        }
                        count++;
                }
                
                // copy sorted nodes to new LinkedList called container
                Linkedlist container = new Linkedlist();
                for (int i = 0; i < 26; i++) {
                        Node n = allNameLinkedList[i].front;
                        
                                while(n != null){
                                        container.addNodeToTheEndOfTheList(n.name);
                                        n = n.next;
                                }
                        }
                        // empty all the elements of array
                        for (int i = 0; i < allNameLinkedList.length; i++) {
                                allNameLinkedList[i] = new Linkedlist();
                        }
                        
                        Node m = container.front;
                        while(m!=null)
                        {
                                String currentname = m.name;
                                for(int i = 0; i < 26; i++){
                                        if(currentname.charAt(1) == (char)(i+97))
                                        {
                                                allNameLinkedList[i].addNodeToTheEndOfTheList(currentname);
                                        }
                                }
                                m = m.next;
                                count++;
                        }
                        container = new Linkedlist();
                        for (int i = 0; i < 26; i++) {
                                m = allNameLinkedList[i].front;
        
                                while(m!=null){
                                        container.addNodeToTheEndOfTheList(m.name);
                                        m = m.next;
                                }
                        }
                        for (int i = 0; i < allNameLinkedList.length; i++) {
                                allNameLinkedList[i] = new Linkedlist();
                        }
                        m = container.front;
                        
                        while(m!=null)
                        {
                                String currentname = m.name;
                                
                                for(int i = 0; i < 26; i++){
                                        if(currentname.charAt(0) == (char)(i+97))
                                        {
                                                allNameLinkedList[i].addNodeToTheEndOfTheList(currentname);
                                        }
                                }
                                m = m.next;
                                count++;
                        }
                        container = new Linkedlist();
                        for (int i = 0; i < 26; i++) {
                                m = allNameLinkedList[i].front;
        
                                while(m!=null){
                                        System.out.println(m.name);
                                        container.addNodeToTheEndOfTheList(m.name);
                                        m = m.next;
                                }
                        }
                        scan.close();
                        System.out.println("The total number of comparisions was :"+count);
                }
        }