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 program using Java language that is- Implement Stack with a linked list, and demonstrate...
write a program using Java language that is- Implement Stack with a linked list, and demonstrate that it can solve the Tower of Hanoi problem. Write implementation body of method “infixToPrefix(String[] e)” of class ArithmeticExpression to convert infix expressions into prefix expressions.
IN JAVA LANGUAGE Linked List-Based Queue Implementation Implement Queue using a Linked List. Use the language...
IN JAVA LANGUAGE Linked List-Based Queue Implementation Implement Queue using a Linked List. Use the language library LinkedList Queue methods will call the LinkedList methods You can use string as the object Instead of using an array, as the QueueLab did, here you will use a Linked List from your language's library. Implement all the methods of Stack : enqueue(), dequeue(), size(), printQueue(), etc, using calls to the linked list methods that correspond to the actions need. In the array...
IN JAVA LANGUAGE Linked List-Based Stack Implementation Implement Stack using a Linked List Use the language...
IN JAVA LANGUAGE Linked List-Based Stack Implementation Implement Stack using a Linked List Use the language library LinkedList Stack methods will call the LinkedList methods You can use string as the object Instead of using an array, as the StackLab did, here you will use a Linked List from your language's library. Implement all the methods of Stack : push(), pop(), size(), printStackDown(), etc, using calls to the linked list methods that correspond to the actions need. In the array...
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...
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.
Language: Java Implement Merge Sort
Language: Java Implement Merge Sort
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>...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT