Scribd Logo
Upload

Welcome to Scribd!

  • 33 views

    Expt-16 - Implementation of Radix Sort

    Uploaded by

    Naveen Bara
    The document describes the implementation of a Radix Sort algorithm in Java. It explains that Radix Sort involves multiple passes over the data, sorting by each digit place value using a counting sort. Pseudocode is provided showing the sorting of elements according to the units place, then tens place, and so on up to the maximum digit length. An example Java implementation of Radix Sort and Counting Sort is given, along with sample output verifying that it correctly sorts an integer array.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Expt-16 - Implementation of Radix Sort

    Uploaded by

    Naveen Bara
    33 views4 pages
    The document describes the implementation of a Radix Sort algorithm in Java. It explains that Radix Sort involves multiple passes over the data, sorting by each digit place value using a counting sort. Pseudocode is provided showing the sorting of elements according to the units place, then tens place, and so on up to the maximum digit length. An example Java implementation of Radix Sort and Counting Sort is given, along with sample output verifying that it correctly sorts an integer array.

    Original Title

    Expt-16_Implementation of Radix Sort

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes the implementation of a Radix Sort algorithm in Java. It explains that Radix Sort involves multiple passes over the data, sorting by each digit place value using a counting sort. Pseudocode is provided showing the sorting of elements according to the units place, then tens place, and so on up to the maximum digit length. An example Java implementation of Radix Sort and Counting Sort is given, along with sample output verifying that it correctly sorts an integer array.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    33 views4 pages

    Expt-16 - Implementation of Radix Sort

    Uploaded by

    Naveen Bara
    The document describes the implementation of a Radix Sort algorithm in Java. It explains that Radix Sort involves multiple passes over the data, sorting by each digit place value using a counting sort. Pseudocode is provided showing the sorting of elements according to the units place, then tens place, and so on up to the maximum digit length. An example Java implementation of Radix Sort and Counting Sort is given, along with sample output verifying that it correctly sorts an integer array.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 4

    School of Computing Science and Engineering

    VIT Bhopal University

    Ex.No.16 Implementation of RadixSort

    AIM: TO PERFORM RADIX SORT

    To write and execute Java program to Implementation of Selection Sort


    Pseudocode:
    radixSort(array)
    d <- maximum number of digits in the largest element
    create d buckets of size 0-9
    for i <- 0 to d
    sort the elements according to ith place digits using countingSort

    countingSort(array, d)
    max <- find largest element among dth place elements
    initialize count array with all zeros
    for j <- 0 to size
    find the total count of each unique digit in dth place of elements and
    store the count at jth index in count array
    for i <- 1 to max
    find the cumulative sum and store it in count array itself
    for j <- size down to 1
    restore the elements to array
    decrease count of each element restored by 1

    Explanation:

    Find the largest element in the array, i.e. max. Let X be the number of digits in max.
    X is calculated because we have to go through all the significant places of all
    elements.

    In this array [121, 432, 564, 23, 1, 45, 788], we have the largest number 788. It has 3
    digits. Therefore, the loop should go up to hundreds place (3 times).
    Now, go through each significant place one by one.

    Use any stable sorting technique to sort the digits at each significant place. We
    have used counting sort for this.

    Sort the elements based on the unit place digits (X=0).


    Now, sort the elements based on digits at tens place

    Name: Naveen Bara [1] Reg. Number: 22MCA10116


    School of Computing Science and Engineering
    VIT Bhopal University

    Finally, sort the elements based on the digits at hundreds place

    Example:

    Program Code:

    public class radix{

    static void countingSort(int a[],int n,int div){

    int count[]=new int[10];

    for(int i=0;i<10;i++)
    count[i]=0;

    for(int i=0;i<n;i++)
    count[(a[i]/div)%10]++;

    for(int i=1;i<10;i++)
    count[i]+=count[i-1];

    int temp[]=new int[n];

    for(int i=n-1;i>-1;i--){
    temp[count[(a[i]/div)%10]-1]=a[i];
    count[(a[i]/div)%10]--;
    }

    for(int i=0;i<n;i++)
    a[i]=temp[i];

    Name: Naveen Bara [2] Reg. Number: 22MCA10116


    School of Computing Science and Engineering
    VIT Bhopal University
    }

    static void radixSort(int a[], int n){

    int max=0;
    for(int i=0;i<n;i++)
    if(a[i]>max)
    max=a[i];

    for(int div=1;max/div>0;div*=10){
    countingSort(a,n,div);
    }
    }
    static void printArr(int a[], int n)
    {
    for (int i = 0; i < n; ++i)
    System.out.print(a[i] + " ");
    }

    public static void main(String args[]){

    int a[]={90,69,17,29,16,10};
    int n = a.length;
    System.out.print("Before sorting array elements are - \n");
    printArr(a, n);
    System.out.print("\nAfter sorting array elements are - \n");
    radixSort(a,a.length);
    for(int i=0;i<a.length;i++)
    System.out.print(a[i]+" ");

    }
    }

    Output Screenshots:
    correct input

    Name: Naveen Bara [3] Reg. Number: 22MCA10116


    School of Computing Science and Engineering
    VIT Bhopal University

    RESULT: Implementation of Radix Sort Thus, the programs for the given problem statements has been
    executed and the results are verified successfully.

    Name: Naveen Bara [4] Reg. Number: 22MCA10116

    You might also like