m2skills

Counting sort java

Oct 13th, 2017
554
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.91 KB | None | 0 0
  1. /**
  2.  * Created by MOHIT on 01-10-2017.
  3.  */
  4. // program to implement counting sort algorithm in java
  5. import java.util.Scanner;
  6.  
  7. public class counting_sort {
  8.     public static Scanner sc = new Scanner(System.in);
  9.  
  10.     public static void main(String arg[]){
  11.  
  12.         int[] myList;
  13.         int length, element;
  14.  
  15.         System.out.println("Program to implement counting sort algorithm in C++");
  16.         System.out.print("Enter the number of Elements to be sorted : ");
  17.         length = sc.nextInt();
  18.         myList = new int[length];
  19.  
  20.         System.out.println("Enter the elements to be sorted : ");
  21.         for(int index = 0; index < length; index++){
  22.             element = sc.nextInt();
  23.             myList[index] = element;
  24.         }
  25.  
  26.         int minElement = myList[0], maxElement = myList[0];
  27.         for(int index = 0; index < length; index++){
  28.             if(minElement > myList[index]){
  29.                 minElement = myList[index];
  30.             }
  31.             if(maxElement < myList[index]){
  32.                 maxElement = myList[index];
  33.             }
  34.         }
  35.  
  36.         System.out.println("The list of elements before sorting is : ");
  37.         displayList(myList, length);
  38.  
  39.         myList = countingSort(myList, length, minElement, maxElement);
  40.  
  41.         System.out.println("The sorted list is : ");
  42.         displayList(myList, length);
  43.     }
  44.  
  45.     // function that prints list of elements
  46.     static void displayList(int elementList[], int length){
  47.         for(int index = 0; index < length; index++){
  48.             System.out.print(elementList[index] + " ");
  49.         }
  50.         System.out.println("\n");
  51.     }
  52.  
  53.     // function that sorts and returns the sorted list
  54.     static int[] countingSort(int myList[], int length, int minElement, int maxElement){
  55.  
  56.         // finding the length, min, max of the recieved list of numbers
  57.         int element;
  58.         // creating a count list with initial values as zeros
  59.         int[] countList = new int[maxElement - minElement + 1];
  60.         for (int index = 0; index < (maxElement - minElement + 1); index++){
  61.             countList[index] = 0;
  62.         }
  63.  
  64.         // counting number of times each element occurs in the list and storing the count in the coutList
  65.         for(int index = 0; index < length; index++) {
  66.             element = myList[index];
  67.             countList[element - minElement] = countList[element - minElement] + 1;
  68.         }
  69.  
  70.         // starting from the min element upto max element
  71.         // we insert values according to their count in the new list in sorted order
  72.         element = minElement;
  73.         int index2 = 0;
  74.         for (int index = 0; index < (maxElement - minElement + 1); index++){
  75.             int Count = countList[index];
  76.             for(int j = 0; j < Count; j++) {
  77.                 myList[index2] = element;
  78.                 index2++;
  79.             }
  80.             element += 1;
  81.         }
  82.         return myList;
  83.     }
  84. }
Add Comment
Please, Sign In to add comment