Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    DS JAVA_lab-radix Sort

    Uploaded by

    janakirampilli70

    Copyright:

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

    DS JAVA_lab-radix Sort

    Uploaded by

    janakirampilli70
    4 views2 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    4 views2 pages

    DS JAVA_lab-radix Sort

    Uploaded by

    janakirampilli70

    Copyright:

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

    94 Lab Manual Data Structures through Java

    Heap h = new Heap(arr.length); // create a Heap

    // Build heap by repeated insertions


    for(int i = 0; i < arr.length; i++)
    h.insert(arr[i]);

    // delete and copy heap’s top item


    for( int i = arr.length-1; i >= 0; i-- )
    arr[i] = h.remove();

    System.out.println("\nSorted array: ");


    h.displayHeap(arr);
    }
    }

    Output:
    Sorted array:
    [0] [1] [2] [3] [4] [5] [6]
    10 20 30 40 50 60 70

    Radix Sort
    This sorting algorithm is known as least-significant-digit-first radix sorting. Radix sorting is practical
    for much larger universal sets. Radix sorting can be used when each element of the universal set can be
    viewed as a sequence of digits (or letters or any other symbols).
    An implementation of radix sort follows. The integer radix is assigned a value 10 and integer
    maxDigits is also assigned the maximum number of digits for the maximum element of the array.
    This algorithm does not depend on comparison of array elements. For each array element, two
    operations are performed:

    (1) To get the significant digit (m) of the number, the array element is divided by the divisor, and
    division modulo radix(10).
    (2) This array element is inserted in the mth queue.

    In each pass, all array elements are added to the queues, and then the elements are deleted from all
    the queues and stored back to array. The method requires additional space for queues. The ten queues
    are implemented by linked lists using java.util.LinkedList class.

    Program 9(g): Radix sort

    class RadixSortDemo
    {
    public static void main(String[] args)
    {
    int[] a = { 3305, 99, 52367, 125, 10, 12345, 7, 35, 7509, 3, 345 };

    radixSort(a, 10, 5);

    System.out.println("Sorted list: ");


    9. Sorting 95

    for(int i = 0; i < a.length; i++ )


    System.out.print( a[i] + " ");
    }

    static void radixSort(int[] arr, int radix, int maxDigits)


    {
    int d, j, k, m, divisor;
    java.util.LinkedList[] queue
    = new java.util.LinkedList[radix];

    for( d = 0; d < radix; d++ )


    queue[d] = new java.util.LinkedList();

    divisor = 1;

    for(d = 1; d <= maxDigits; d++) // Pass: 1, 2, 3, . . .


    {
    for(j = 0; j < arr.length; j++)
    {
    m = (arr[j]/divisor) % radix;
    queue[m].addLast(new Integer(arr[j]));
    }

    divisor = divisor*radix; // 1, 10, 100, ...

    for(j = k = 0; j < radix; j++)


    {
    while( !queue[j].isEmpty())
    arr[k++] = (Integer)queue[j].removeFirst();
    }
    }
    }
    }

    Output:

    Sorted list:
    3 7 10 35 99 125 345 3305 7509 12345 52367

    Binary Tree Sort


    When we traverse a binary search tree in inorder, the keys will come out in sorted order. In tree sort,
    We take the array to be sorted, use the method buildTree() to construct the array elements into a
    binary search tree, and use inorder traversal to put them out in sorted order.

    Program 9(h): Binary Tree Sort

    class BSTNode
    { int data;
    BSTNode left;
    BSTNode right;
    BSTNode( int d ) // constructor
    { data = d; }
    }

    You might also like