Question

In: Computer Science

Data structure program Implement (your own) the Radix Sort using single linked list java language

Data structure program Implement (your own) the Radix Sort using single linked list

java language

Solutions

Expert Solution

public class RadixSort {

    public static void main(String[] args) {
        int[] arr = {80, 406, 21, 655, 55, 4, 8, 91, 87, 6};
        System.out.println("Original Array- " + Arrays.toString(arr));
        radixSort(arr);
        System.out.println("Sorted array after Radix sort- " + Arrays.toString(arr));
    }
    
    private static void radixSort(int[] arr){
        int max = getMaxElement(arr);
        int position = 1;
        while(max/position > 0){
            countingSort(arr, position);
            position *= 10;
        }        
    }
        
    private static int getMaxElement(int[] arr){
        int max = arr[0];
        for(int i = 1; i < arr.length; i++){
            if (arr[i] > max){
                max = arr[i];
            }
        }
        return max;
    }
    
    private static void countingSort(int[] arr, int position){
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[n];
        
        //count number of times each element appear
        for(int i = 0; i < arr.length; i++){
            count[(arr[i]/position)%10]++;
        }

        // each element stores (element at current index+element
        // at previous index) to get the actual position of the element
        for(int i = 1; i < n; i++){
            count[i] = count[i] + count[i-1];
        }
    
        // for correct placement of the numbers start from the end
        for(int i = n-1; i >=0; i--){
            output[count[(arr[i]/position)%10] - 1] = arr[i];
            count[(arr[i]/position)%10]--;
        }
        // Copy output array to input to the input for 
        // the next stage of counting sort
        for(int i = 0; i < output.length; i++){
            arr[i] = output[i];
        }
        System.out.println("Counting sort at this stage " + Arrays.toString(arr));
    }
}

Related Solutions

Java program to implement the merge sort your own and test it to sort a list...
Java program to implement the merge sort your own and test it to sort a list of names based on the frequency.
Write a Java program to implement a Single Linked List that will take inputs from a...
Write a Java program to implement a Single Linked List that will take inputs from a user as Student Names. First, add Brian and Larry to the newly created linked list and print the output Add "Kathy" to index 1 of the linked list and print output Now add "Chris" to the start of the list and "Briana" to the end of the list using built-in Java functions. Print the output of the linked list.
Implement Radix Sort using PYTHON programming language. Use one of the two options for the algorithm...
Implement Radix Sort using PYTHON programming language. Use one of the two options for the algorithm to sort the digits: Use Counting Sort or Bucket Sort. • Assume the numbers are maximum 4-digit numbers. • If using Counting Sort, you can see that your digit range is between 0 and 9 ([0…9]). • If using Bucket Sort, you will have ten buckets labeled from 0 to 9. Please add comments and explain every step carefully.
In this Java program you will implement your own doubly linked lists. Implement the following operations...
In this Java program you will implement your own doubly linked lists. Implement the following operations that Java7 LinkedLists have. 1. public DList() This creates the empty list 2. public void addFirst(String element) adds the element to the front of the list 3. public void addLast(String element) adds the element to the end of the list 4. public String getFirst() 5. public String getLast() 6. public String removeLast() removes & returns the last element of the list. 7. public String...
Language: Java Implement Merge Sort
Language: Java Implement Merge Sort
write a java program to Implement a Priority Queue using a linked list. Include a main...
write a java program to Implement a Priority Queue using a linked list. Include a main method demonstrating enqueuing and dequeuing several numbers, printing the list contents for each.
Write a program to implement linked list data structure that will have following functions: a. Append...
Write a program to implement linked list data structure that will have following functions: a. Append a node in the list b. Insert a node in the list c. Delete a node from the list d. Display list e. Find maximum value in the list f. Find how many times a value exists in the list. g. Search Portion of the code is give below. You have to write code for the items (e, f, g) Program: #include<stdlib.h> #include<stdio.h> #include<iostream>...
(Write a C# program DO NOT USE CLASS)Implement the merge sort algorithm using a linked list...
(Write a C# program DO NOT USE CLASS)Implement the merge sort algorithm using a linked list instead of arrays. You can use any kind of a linked structure, such as single, double, circular lists, stacks and/or queues. You can populate your list from an explicitly defined array in your program. HINT: You will not be using low, middle and high anymore. For finding the middle point, traverse through the linked list while keeping count of the number of nodes. Break...
Please show solution and comments for this data structure using java.​ Implement a program in Java...
Please show solution and comments for this data structure using java.​ Implement a program in Java to convert an infix expression that includes (, ), +, -, *,     and / to postfix expression. For simplicity, your program will read from standard input (until the user enters the symbol “=”) an infix expression of single lower case and the operators +, -, /, *, and ( ), and output a postfix expression.
java 2. Write a program to implement heapsort. Sort the following elements using your program. 6,...
java 2. Write a program to implement heapsort. Sort the following elements using your program. 6, 12, 34, 29, 28, 11, 23, 7, 0, 33, 30, 45
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT