Question

In: Computer Science

Java code: Use Radix sort to sort them in alphabetic order. How many passes would be...

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

Solutions

Expert Solution

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);
                }
        }



Related Solutions

implement merge sort,quick sort, and radix sort algorithms in java and test how long it will...
implement merge sort,quick sort, and radix sort algorithms in java and test how long it will take to sort with random data sets of users input numbers.
(C++)Radix Sort: Write C++ codes for radix sort: use counting sort for decimal digits from the...
(C++)Radix Sort: Write C++ codes for radix sort: use counting sort for decimal digits from the low order to high order. The input array is A = {329, 457, 657, 839, 436, 720, 353}
Add bubble sort, radix sort, insertion sort, and merge sort to the code provided. Import a...
Add bubble sort, radix sort, insertion sort, and merge sort to the code provided. Import a data set (txt file) then do the sorting algorithm to measure how long it took and how many movements occurred. Please write codes in C++ Here's data set (should be stored in txt file) 7426 4524 4737 9436 3997 2757 6288 5414 9590 5968 6638 3199 9514 1541 9866 2144 6731 911 2171 6135 6437 912 9417 2662 6606 6349 707 2890 5386 9718...
Why is radix sort generally rejected by so many computer programmers? Under what conditions does Radix-Sort...
Why is radix sort generally rejected by so many computer programmers? Under what conditions does Radix-Sort run faster than O(n lg n) algorithms such as quicksort? Under what conditions does Radix-Sort run slower than O(n lg n) algorithms such as quicksort? How common are each of these conditions? When do you think a sort such as radix sort would be useful?
In Java: Write two advanced sorting methods of your choice: (Shell Sort OR Radix Sort) AND...
In Java: Write two advanced sorting methods of your choice: (Shell Sort OR Radix Sort) AND (Merge Sort OR Quick Sort). If you choose Shell Sort, experiment with different incremental sequences to see how they affect the algorithm's run time efficiency (count the number of comparisons and exchanges). If you choose to implement Radix Sort, answer the following question as well: Can you write a version of Radix Sort for String objects? If yes, explain how. If not, explain why....
Give an example of how Radix sort works
Give an example of how Radix sort works
Hello i need someone to implement for me RADIX SORT IN JAVA for Characters NOT numbers...
Hello i need someone to implement for me RADIX SORT IN JAVA for Characters NOT numbers and i need the code super fast please
Hello i need someone to implement in JAVA a radix sort algorithm forsorting strings in ascending...
Hello i need someone to implement in JAVA a radix sort algorithm forsorting strings in ascending order. The input to your algorithm should be a (multi)set S = [S1, S2, . . . , Sn] of strings each of which is of length m over the English alphabet [A…Z, a…z]. The output should be the set sorted in ascending lexicographical order. Number of strings is >= 100 and number of characters >= 50 i need the answer fast please
How would I make a bubble sort and an optimized bubble sort with the code given?...
How would I make a bubble sort and an optimized bubble sort with the code given? I also need to implement a timer into each sort and display runtime with the sorts. NODE.H _______________________________________________________________________________________________________ /* node.h */ /* two classes 1: node.h 2. singlylinkedlist.h nod1 (value + pointer) ---> node2 ---> node3 ---> |||| <--- node.h ^ | singlylinkedlist ----------------*node head; */ #ifndef NODE_H #define NODE_H #include <iostream> using namespace std; class Node {    friend class singlyLinkedList; public:   ...
Java : Modify the selection sort algorithm to sort an array of integers in descending order....
Java : Modify the selection sort algorithm to sort an array of integers in descending order. describe how the skills you have gained could be applied in the field. Please don't use an already answered solution from chegg. I've unfortunately had that happen at many occasion ....... ........ sec01/SelectionSortDemo.java import java.util.Arrays; /** This program demonstrates the selection sort algorithm by sorting an array that is filled with random numbers. */ public class SelectionSortDemo { public static void main(String[] args) {...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT