m2skills

Counting sort c++

Oct 13th, 2017
545
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.32 KB | None | 0 0
  1. // program to implement counting sort algorithm in c++
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. void displayList(int elementList[], int length){
  7.     for(int index = 0; index < length; index++){
  8.         cout<<elementList[index]<<" ";
  9.     }
  10.     cout<<endl;
  11. }
  12.  
  13. int* countingSort(int myList[], int length, int minElement, int maxElement){
  14.  
  15.     // finding the length, min, max of the recieved list of numbers
  16.     int element;
  17.     // creating a count list with initial values as zeros
  18.     int countList[maxElement - minElement + 1];
  19.     for (int index = 0; index < (maxElement - minElement + 1); index++){
  20.         countList[index] = 0;
  21.     }
  22.  
  23.     // counting number of times each element occurs in the list and storing the count in the coutList
  24.     for(int index = 0; index < length; index++) {
  25.         element = myList[index];
  26.         countList[element - minElement] = countList[element - minElement] + 1;
  27.     }
  28.  
  29.     // starting from the min element upto max element
  30.     // we insert values according to their count in the new list in sorted order
  31.     element = minElement;
  32.     int index2 = 0;
  33.     for (int index = 0; index < (maxElement - minElement + 1); index++){
  34.         int Count = countList[index];
  35.         for(int j = 0; j < Count; j++) {
  36.             myList[index2] = element;
  37.             index2++;
  38.         }
  39.         element += 1;
  40.     }
  41.  
  42.     return myList;
  43.  
  44. }
  45.  
  46. int main(){
  47.  
  48.     int *sortedList;
  49.     cout<<"Program to implement counting sort algorithm in C++"<<endl;
  50.     int length, element;
  51.     cout<<"Enter the number of Elements to be sorted : ";
  52.     cin>>length;
  53.     int myList[length];
  54.     cout<<"Enter the elements to be sorted : ";
  55.     for(int index = 0; index < length; index++){
  56.         cin>>element;
  57.         myList[index] = element;
  58.     }
  59.  
  60.     int minElement = myList[0], maxElement = myList[0];
  61.     for(int index = 0; index < length; index++){
  62.         if(minElement > myList[index]){
  63.             minElement = myList[index];
  64.         }
  65.         if(maxElement < myList[index]){
  66.             maxElement = myList[index];
  67.         }
  68.     }
  69.  
  70.     cout<<"\nThe list of elements before sorting is : "<<endl;
  71.     displayList(myList, length);
  72.  
  73.     sortedList = countingSort(myList, length, minElement, maxElement);
  74.  
  75.     cout<<"\nThe sorted list is : "<<endl;
  76.     displayList(sortedList, length);
  77. }
Add Comment
Please, Sign In to add comment