Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: Radix Sort Problem

  1. #1
    Junior Member
    Join Date
    Dec 2019
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Radix Sort Problem

    Anyones know how to implement radix sort on linkedlist in java?
    I tried and got error
    package layout;
    import java.util.Scanner;
     
    /* Class Node */
    class Node {
    	protected int data;
    	protected Node next, prev;
    	/* Constructor */
    	public Node() {
    		data = 0;
    		next = null;
    	}
    	/* Constructor */
    	public Node( int d, Node n ) {
    		data = d;
    		next = n;
    	}
    	/* Function to set link to next node */
    	public void setLinkNext( Node n ) {
    		next = n;
    	}
    	/* Funtion to get link to next node */
    	public Node getLinkNext() {
    		return next;
    	}
    	/* Function to set data to node */
    	public void setData( int d ) {
    		data = d;
    	}
    	/* Function to get data from node */
    	public int getData() {
    		return data;
    	}
    }
     
    /* Class linkedList */
    class linkedList {
    	protected Node start, end;
    	public int size;
    	/* Constructor */
    	public linkedList() {
    		start = null;
    		end = null;
    		size = 0;
    	}
    	/* Function to check if list is empty */
    	public boolean isEmpty() {
    		return start == null;
    	}
    	/* Function to get size of list */
    	public int getSize() {
    		return size;
    	}
    	public Node getNodeStart() {
    		return start;
    	}
    	public Node getNodeEnd() {
    		return end;
    	}
    	/* Function to insert element */
    	public void insertHead( int val ) {
    		Node p = new Node( val, null );
    		if ( start == null ) {
    			start = p;
    			end = start;
    		}
    		else {
    			p.setLinkNext( start );
    			start = p;
    		}
    		size++;
    	}
    	void insertTail( int val ) {
    		Node p = new Node( val, null );;
    		if ( start == null ) {
    			start = p;
    			end = start;
    		}
    		else {
    			end.setLinkNext( p );
    			end = p;
    		}
    		p.setLinkNext( null );
    		size++;
    	}
    	void Output() {
    		Node p = start;
    		while ( p != null ) {
    			System.out.print( p.getData() + " <-> " );
    			p = p.getLinkNext();
    		}
    	}
    	/* Function to convert List to a String */
    	public String display() {
    		String ListString01 = "";
    		Node ptr = start;
    		ListString01 = ListString01 + ptr.getData() + ",  ";
    		if ( size == 0 ) {
    			ListString01 = "List is empty";
    			return ListString01;
    		}
    		ptr = start.getLinkNext();
    		while ( ptr.getLinkNext() != null ) {
    			ListString01 = ListString01 + ptr.getData() + ",  ";
    			ptr = ptr.getLinkNext();
    		}
    		ListString01 = ListString01 + ptr.getData() + ",  ";
    		return ListString01;
    	}
    	void initList( linkedList List ) {
    		List.start = List.end = null;
    	}
    	int findMax() {
    		Node p;
    		p = new Node();
    		p = this.start;
    		int max = p.data;
    		while ( p != null ) {
    			if ( max < p.data )
    				max = p.data;
    			p = p.getLinkNext();
    		}
    		return max;
    	}
    	int countDigit( int n ) {
    		int count = 0;
    		while ( n > 0 ) {
    			n = n / 10;
    			count++;
    		}
    		return count;
    	}
    	int getMaxDigit() {
    		int max = this.findMax();
    		return countDigit( max );
    	}
    	void appendList( linkedList List2 ) {
    		if ( this.start == null )
    			this.start = List2.start;
    		else {
    			this.end.setLinkNext( List2.start );
    			if ( List2.start != null )
    				this.end = List2.end;
    		}
    	}
    	int getDigit( int n, int t ) {
    		long temp = 1;
    		for ( int i = 0; i < n; i++ )
    			temp = temp * 10;
    		return (int) ( ( t / temp ) % 10 );
    	}
    	void sendToBox( int n, linkedList temp[] ) {
    		Node p;
    		p = new Node();
    		p = this.start;
    		while ( p != null ) {
    			temp[ getDigit( n, p.data ) ].insertTail( p.data );
    			p = p.getLinkNext();
    		}
    	}
    	void radixSort() {
    		linkedList[] temp = new linkedList[ 10 ];
    		int i;
    		if ( this.start == this.end )
    			return;
    		for ( i = 0; i < 10; i++ )
    			temp[ i ] = new linkedList();
    		int num = this.getMaxDigit();
    		for ( i = 0; i < num; i++ ) {
    			sendToBox( i, temp );
    			for ( int j = 0; j < 10; j++ ) {
    				this.appendList( temp[ j ] );
    				initList( temp[ j ] );
    			}
    		}
    	}
    	@SuppressWarnings( "deprecation")
    	public static void main( String arg[] ) {
    		linkedList list01;
    		list01 = new linkedList();
    		int k = 10;
    		int a[] = { 12, 23, 34, 78, 91, 44, 52, 68, 79, 77 };
    		for ( int i = 0; i < k; i++ ) {
    			list01.insertHead( a[ i ] );
    		}
    		System.out.println( "oOo  m01.Output();  oOo" );
    		list01.Output();
    		System.out.println( " " );
    		System.out.println( "oOo  m01.display( );  oOo" );
    		String s01 = list01.display();
    		System.out.println( s01 );
    		list01.radixSort();
    		System.out.println( "oOo  List after sort;  oOo" );
    		String s02 = list01.display();
    		System.out.println( s02 );
    	}
    }

    Output:
    oOo m01.Output(); oOo
    77 <-> 79 <-> 68 <-> 52 <-> 44 <-> 91 <-> 78 <-> 34 <-> 23 <-> 12 <->
    oOo m01.display( ); oOo
    77, 79, 68, 52, 44, 91, 78, 34, 23, 12,
    oOo List after sort; oOo
    77, 79, 68, 52, 44, 91, 78, 34, 23, 12, 91, 52, 12, 23, 44, 34, 77, 68, 78, 79, 12, 12, 23, 23, 34, 34, 44, 44, 52, 52, 68, 68, 77, 79, 78, 77, 78, 79, 91, 91,

  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    On vacation
    Posts
    22,755
    Thanks
    53
    Thanked 2,428 Times in 2,379 Posts

    Default Re: Radix Sort Problem

    I tried and got error
    Please copy the full text of the error message and paste it here. It has important info about the error.
    If you don't understand my answer, don't ignore it, ask a question.

Similar Threads

  1. Problem with Collection sort
    By bhk in forum What's Wrong With My Code?
    Replies: 4
    Last Post: May 30th, 2013, 09:33 AM
  2. K-way merge sort problem
    By yotabytes in forum Algorithms & Recursion
    Replies: 0
    Last Post: March 7th, 2013, 09:12 PM
  3. Radix Sort
    By Ronald Spina in forum What's Wrong With My Code?
    Replies: 2
    Last Post: December 14th, 2012, 06:36 PM
  4. Radix Sort
    By Ronald Spina in forum What's Wrong With My Code?
    Replies: 6
    Last Post: December 14th, 2012, 04:31 AM
  5. Radix sort Issues??? Help
    By dadof3 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: May 13th, 2011, 01:08 PM