CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 9 of 9

Thread: Parallel Counter Sort

  1. #1
    Join Date
    Sep 2015
    Posts
    13

    Parallel Counter Sort

    First of all, let me explain that counter sort is an optimized version of counting sort. Counter sort takes the highest and lowest values and then makes an array from the lowest to the highest and counts the number of times that the index of the counter array in in the sorting array. Then it creates a new array by placing the index from the counter array back in sorted order.

    Right now when I run the current code I have I get an exception:
    Exception in thread "Thread-1" java.lang.ArrayIndexOutOfBoundsException: 10
    at ParCountSor.Thread1.run(Thread1.java:48)

    So, somehow I am reach outside of my array or not stopping. I'm looking through it and could use some fresh eyes to help me figure out where I am going wrong with my sort and how I'm going through the array.

    Code:
    package ParCountSor;
    
    import java.util.Random;
    import java.util.Scanner;
    
    public class CountSort {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int i, j = 0;
    		int counter = 0;//test for how many times it runs.
            int[] data;
            Random ranGen = new Random();
            //Accept in the Command Line Parameter
            //If the parameter is correct.
           if(args.length == 2){
                   int testnum = Integer.parseInt(args[1]);//how many times it will run
           for (i = 0; i != testnum; i++){
                    int[] ranarray = new int [10];//random array to be sorted
                    int arraynumb = i;//just to tell what array is being sorted
                    	arraynumb++;//make the number more real
                    
                    System.out.println("For array " + arraynumb);
                        for (j = 0; j < ranarray.length; j++){
                        	int ran = ranGen.nextInt(301); //Randomly generates number (0 - 19)
                             System.out.print(" " + ran);
                             ranarray[j] = ran; //Random number added
                             data = ranarray;
    
                        }//for
                        System.out.println("");
                        Thread1 t1 = new Thread1(ranarray);//pass over to the thread
                		t1.start();//start the thread
    
                		try {
                			t1.join();//bring back the values from thread 1
                		} catch (InterruptedException e) {
                			// TODO Auto-generated catch block
                			e.printStackTrace();
                		}
                    counter++; //Counter + 1
           }//for
    
            System.out.println("\nSorted " +  counter + " time(s)");
            //Print out how many successful times it sorted
            }else if(args.length > 2 ) {
              System.out.println("Too many arguments supplied.");
            }
            //else too few arguments
            else{
              System.out.println("One argument expected.");
            }	
    	}
    
    }
    Thread1 class

    Code:
    package ParCountSor;
    
    	public class Thread1 extends Thread{
    		private static int[] result;
    		public int[] cArray;//half of array to search
    		public Thread1(int[] ranarray) {
    			//constructor for firstHalf and target
    			this.cArray = ranarray;//copy array
    		}
    		
    		public int findmax(){
    			int max = cArray[0];
    			for(int i = 0; i < cArray.length; i++){
    				if (cArray[i] > max){
    					max = cArray[i];
    				}
    			}
    			return max;
    		}
    		
    		public int findmin(){
    			int min = cArray[0];
    			for(int i = 0; i < cArray.length; i++){
    				if (cArray[i] < min){
    					min = cArray[i];
    				}
    			}
    			return min;
    		}
    
    		public void run(){
    			int max = findmax();
    			int min = findmin();
    			int range = max - min +1;
    			int [] counts = new int[range];
    			result = new int [cArray.length];
    			for(int i = 0; i < cArray.length; i++){
    				//counts[cArray[i]] = counts[cArray[i]]++;
    				counts[cArray[i]- min]++;
    			}
    			
    			for(int i = 1; i < counts.length; i++){
    				counts[i] = counts[i] + counts[i-1];
    			}
    			
    			for(int i = cArray.length - 1; i >= 0; i--){
    				//counts[cArray[i]]++;
    				result[counts[cArray[i] - min]--] = cArray[i];
    			}
    			
    		}//end run method
    		
    		/*public void setResult(int result){
    			this.result = result;
    		}*/
    		public int[] getResult(){
    			return this.result;
    		}
    		
    	}//end Thread1 class
    Also posted:
    http://www.dreamincode.net/forums/to...-counter-sort/

  2. #2
    Join Date
    Sep 2015
    Posts
    13

    Re: Parallel Counter Sort

    Yea I fixed those comments and added. (I do all that last, focus on making code work first, then fix comments).

    So I went back through and just redid a lot of my code finding a different model to follow, and it compiles and runs. Just bad output. Here is what I got last time.

    For array 1
    286 182 52 284 137 157 18 3 299 147
    Sorted Array:
    12 182 52 284 137 157 18 3 299 147

    Sorted 1 time(s)

    The 286 was replaced with 12. And then the rest of the array is just printed without any changes. So seems like it passes thru, doesn't sort, replace the first, and prints that out.

    CounterSort Class (Hasn't changed much)

    Code:
    package ParCountSor;
    
    import java.util.Random;
    import java.util.Scanner;
    
    public class CountSort {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int i, j = 0;
    		int counter = 0;//test for how many times it runs.
            int[] data;
            Random ranGen = new Random();
            //Accept in the Command Line Parameter
            //If the parameter is correct.
           if(args.length == 2){
                   int testnum = Integer.parseInt(args[1]);//how many times it will run
           for (i = 0; i != testnum; i++){
                    int[] ranarray = new int [10];//random array to be sorted
                    int arraynumb = i;//just to tell what array is being sorted
                    	arraynumb++;//make the number more real
                    
                    System.out.println("For array " + arraynumb);
                        for (j = 0; j < ranarray.length; j++){
                        	int ran = ranGen.nextInt(301); //Randomly generates number (0 - 300)
                             System.out.print(ran + " ");
                             ranarray[j] = ran; //Random number added
                             data = ranarray;
    
                        }//for
                        System.out.println("");
                        Thread1 t1 = new Thread1(ranarray);//pass over to the thread
                		t1.start();//start the thread
    
                		try {
                			t1.join();//bring back the values from thread 1
                		} catch (InterruptedException e) {
                			// TODO Auto-generated catch block
                			e.printStackTrace();
                		}
                    counter++; //Counter + 1
           }//for
    
            System.out.println("\nSorted " +  counter + " time(s)");
            //Print out how many successful times it sorted
            }else if(args.length > 2 ) {
              System.out.println("Too many arguments supplied.");
            }
            //else too few arguments
            else{
              System.out.println("One argument expected.");
            }	
    	}
    
    }

    Thread1 Class (Good deal of change)

    Code:
    package ParCountSor;
    
    	public class Thread1 extends Thread{
    		private int[] counts;
    		public int[] cArray;//half of array to search
    		public Thread1(int[] ranarray) {
    			//constructor for firstHalf and target
    			this.cArray = ranarray;//copy array
    		}
    		
    		public int findmax(){
    			int max = cArray[0];
    			for(int i = 0; i < cArray.length; i++){
    				if (cArray[i] > max){
    					max = cArray[i];
    				}
    			}
    			return max;
    		}
    		
    		public int findmin(){
    			int min = cArray[0];
    			for(int i = 0; i < cArray.length; i++){
    				if (cArray[i] < min){
    					min = cArray[i];
    				}
    			}
    			return min;
    		}
    
    		public void run(){
    			int max = findmax();//max value
    			int min = findmin();//min value
    			int range = max - min +1;//find the range
    			counts = new int[range];//counts array
    			
    			//make count of how many times it appears in the array
    			for(int i = 0; i < cArray.length; i++){
    				counts[cArray[i]- min]++;
    			}//end for
    			//make sure of positions in final array
    			for(int i = 1; i < counts.length; i++){
    				counts[i] += counts[i-1];
    			}//end for
    			//sort original array
    			int j = 0;
    			for(int i = cArray.length - 1; i >= 0; i--){
    				while(j < counts[i]){
    					cArray[j++] = i + min;
    				}//end while
    			}//end for
    			//print sorted array
    			System.out.println("Sorted Array: ");
    			for(int i = 0; i < cArray.length; i++){
    				System.out.print(cArray[i]+" ");
    			}//end for
    			System.out.println("");
    		}//end run method
    
    		public int[] getCounts(){
    			return this.counts;
    		}//end getResult
    		
    	}//end Thread1 class

  3. #3
    Join Date
    Sep 2015
    Posts
    13

    Re: Parallel Counter Sort

    So, working through commented out code, a section, so I know where it was changing the first value, but still doesn't want to sort the data. So question is what is wrong with my sort?

    Code:
    			//sort original array
    			int j = 0;
    			for(int i = 0; i < counts.length; i++){
    				while(j < counts[i]){
    					cArray[j++] = i + minVal;
    					counts[i]--;
    				}//end while
    Rest of my code Thread1 class code (the CountSort hasn't changed since above)

    Code:
    package ParCountSor;
    
    	public class Thread1 extends Thread{
    		private int[] counts;
    		public int[] cArray;//half of array to search
    		public Thread1(int[] ranarray) {
    			//constructor for firstHalf and target
    			this.cArray = ranarray;//copy array
    		}
    		
    		public int findmax(){
    			int max = cArray[0];
    			for(int i = 0; i < cArray.length; i++){
    				if (cArray[i] > max){
    					max = cArray[i];
    				}
    			}
    			return max;
    		}
    		
    		public int findmin(){
    			int min = cArray[0];
    			for(int i = 0; i < cArray.length; i++){
    				if (cArray[i] < min){
    					min = cArray[i];
    				}
    			}
    			return min;
    		}
    
    		public void run(){
    			int maxVal = findmax();//max value
    			int minVal = findmin();//min value
    			int range = maxVal - minVal +1;//find the range
    			counts = new int[range];//counts array
    			
    			//make count of how many times it appears in the array
    			/*for(int i = 0; i < cArray.length; i++){
    				counts[cArray[i]- min]++;
    			}//end for*/
    			for(int i =0; i < cArray.length; i++){
    				counts[cArray[i] - minVal]++;
    			}
    			/*//make sure of positions in final array
    			for(int i = 1; i < counts.length; i++){
    				counts[i] += counts[i-1];
    			}//end for*/
    			//sort original array
    			int j = 0;
    			for(int i = 0; i < counts.length; i++){
    				while(j < counts[i]){
    					cArray[j++] = i + minVal;
    					counts[i]--;
    				}//end while
    			}//end for
    			//print sorted array
    			System.out.println("Sorted Array: ");
    			for(int i = 0; i < cArray.length; i++){
    				System.out.print(cArray[i]+" ");
    			}//end for
    			System.out.println("");
    		}//end run method
    
    		public int[] getCounts(){
    			return this.counts;
    		}//end getResult
    		
    	}//end Thread1 class

  4. #4
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,325

    Re: Parallel Counter Sort

    What debugging of the code has been done? Has the code been traced to see what happens when that code is executed to determine when/why it deviates from what is expected?
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.8.2)

  5. #5
    Join Date
    Sep 2015
    Posts
    13

    Re: Parallel Counter Sort

    i've run test prints, commenting out code, i've went thru it with the debugger and it runs thru, but doesn't sort the data the way i'm need it to. i'm not sure how fair off i am because i've been looking at counting sorts (less optimized version of counter sort) and what i have is either the same or they have a few lines different from mine.

  6. #6
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,325

    Re: Parallel Counter Sort

    i've went thru it with the debugger and it runs thru, but doesn't sort the data the way i'm need it to
    In that case, tracing through the code execution with the debugger should show why the data is not being sorted properly as you'll be able to see the variable contents and the path taken through the code.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.8.2)

  7. #7
    Join Date
    Sep 2015
    Posts
    13

    Re: Parallel Counter Sort

    So mainly been cleaning up my code and testing. When I now run this, I get this as the result.

    For array 1
    261 155 13 31 203 298 13 122 237 173
    Exception in thread "Thread-0" java.lang.ArrayIndexOutOfBoundsException: 286
    at ParCountSor.Thread1.run(Thread1.java:46)

    Sorted 1 time(s)

    That 286 is the range variable that is the length of the counts array. Completely confused there. Does it think that I want the value to be 286? Am I set the size of the counts array wrong?

    Thread1 (CountSort class hasn't changed)

    Code:
    package ParCountSor;
    
    import java.util.Arrays;
    
    	public class Thread1 extends Thread{
    		private int[] counts;
    		public int[] cArray;//half of array to search
    		public Thread1(int[] ranarray) {
    			//constructor for firstHalf and target
    			this.cArray = ranarray;//copy array
    		}
    		
    		public int findmax(){
    			int max = cArray[0];
    			for(int i = 0; i < cArray.length; i++){
    				if (cArray[i] > max){
    					max = cArray[i];
    				}
    			}
    			return max;
    		}
    		
    		public int findmin(){
    			int min = cArray[0];
    			for(int i = 0; i < cArray.length; i++){
    				if (cArray[i] < min){
    					min = cArray[i];
    				}
    			}
    			return min;
    		}
    
    		public void run(){
    			int maxVal = findmax();//max value
    			int minVal = findmin();//min value
    			int range = maxVal - minVal +1;//find the range
    			counts = new int[range];//counts array
    			
    
    			for(int i =0; i < cArray.length; i++){
    				counts[cArray[i]-minVal]++;
    			}
    			int j = 0;
    			for(int i = 0; i < counts.length; i++){
    				while(counts[i] > 0){
    					counts[j++] = i + minVal;
    					counts[i]--;
    				}
    			}
    			//print sorted array
    			System.out.println("Sorted Array: " + Arrays.toString(counts));
    			
    			System.out.println("");
    		}//end run method
    
    		public int[] getCounts(){
    			return this.counts;
    		}//end getResult
    		
    	}//end Thread1 class

  8. #8
    Join Date
    Sep 2015
    Posts
    13

    Re: Parallel Counter Sort

    GOT IT! Finally got it to sort and everything. I would say the only thing it does wrong is it takes the last value of the original array and then prints that at the end. For example:

    268 31 218 114 55 73 213 276 211 195
    Sorted Array: [31, 55, 73, 114, 195, 211, 213, 218, 268, 195]


    Sorted 1 time(s)

    That 195 is just reprinted, there are not another 195 in the array. So if I could get help one last few things. Why is that last value there, and if anyone can double check my comments to make sure they make sense, that would be amazing!

    Thank you!

    My code:

    Code:
    package ParCountSor;
    
    import java.util.Random;
    
    
    public class CountSort {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int i, j = 0;
    		int counter = 0;//test for how many times it runs.
            int[] data = new int [10];
            Random ranGen = new Random();
            //Accept in the Command Line Parameter
            //If the parameter is correct.
           if(args.length == 2){
                   int testnum = Integer.parseInt(args[1]);//how many times it will run
           for (i = 0; i != testnum; i++){
                    int[] ranarray = new int [10];//random array to be sorted
                    int arraynumb = i;//just to tell what array is being sorted
                    	arraynumb++;//make the number more real
                    
                    System.out.println("For array " + arraynumb);
                        for (j = 0; j < ranarray.length; j++){
                        	int ran = ranGen.nextInt(301); //Randomly generates number (0 - 300)
                             System.out.print(ran + " ");
                             ranarray[j] = ran; //Random number added
                             data = ranarray;
    
                        }//for
                        System.out.println("");
                        Thread1 t1 = new Thread1(data);//pass over to the thread
                		t1.start();//start the thread
    
                		try {
                			t1.join();//bring back the values from thread 1
                		} catch (InterruptedException e) {
                			// TODO Auto-generated catch block
                			e.printStackTrace();
                		}
                    counter++; //Counter + 1
           }//for
    
            System.out.println("\nSorted " +  counter + " time(s)");
            //Print out how many successful times it sorted
            }else if(args.length > 2 ) {
              System.out.println("Too many arguments supplied.");
            }
            //else too few arguments
            else{
              System.out.println("One argument expected.");
            }	
    	}
    
    }

    Thread1 class

    Code:
    package ParCountSor;
    
    import java.util.Arrays;
    
    	public class Thread1 extends Thread{
    		private int[] counts;
    		public int[] cArray;//half of array to search
    		public Thread1(int[] data) {
    			//constructor for firstHalf and target
    			this.cArray = data;//copy array
    		}	
    		//find the max value in the array
    		public int findmax(){
    			int max = cArray[0];
    			for(int i = 0; i < cArray.length; i++){
    				if (cArray[i] > max){
    					max = cArray[i];
    				}
    			}
    			return max;
    		}
    		//find the minimum value in the array
    		public int findmin(){
    			int min = cArray[0];
    			for(int i = 0; i < cArray.length; i++){
    				if (cArray[i] < min){
    					min = cArray[i];
    				}
    			}
    			return min;
    		}
    		
    		//run method executes the counter sort
    		public void run(){
    			int maxVal = findmax();//max value
    			int minVal = findmin();//min value
    			int range = maxVal - minVal + 1;//find the range
    			int[] counts = new int[range];//counts array
    			//counts the number of frequencies of each value of the array
    			for(int i =0; i < cArray.length; i++){
    				counts[cArray[i] - minVal]++;
    			}
    			//data in cArray is sorted from lower to highest based on counts array
    			int j = 0;
    			for(int i = minVal; i < maxVal; i++){
    				while(counts[i - minVal] > 0){
    					cArray[j] = i;
    					j++;
    					counts[i - minVal]--;
    				}
    			}//end for
    			//print sorted array
    			System.out.println("Sorted Array: " + Arrays.toString(cArray));
    		}//end run method
    
    		public int[] getCounts(){
    			return this.counts;
    		}//end getResult
    		
    	}//end Thread1 class

  9. #9
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,325

    Re: Parallel Counter Sort

    That 195 is just reprinted,
    No. 276 in the input isn't in the output. It should be on the end where the duplicated 195 is.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.8.2)

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)