C++ Program for Counting sort














































C++ Program for Counting sort




Description:-The Counting sort is one of the stable sort algorithm in which two object having
equal key do appear in the same order in sorted resultant output as they relatively were in
the input unsorted array. Counting sort is a technique based on the keys lying in between 
any specific range. This sorting counts number of objects which are having different key 
values and then thereby calculates position of each of the object in output.

Time Complexity:O(n+k)

#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <iterator>

//countingSort sort function
template<typename T,size_t len>
static void countingSort(std::array<T,len>& items) {

//Range for counting array
const unsigned int RANGE = 255;
std::vector<T> count(RANGE,0);

//Counting each elements numbers of time they appered
for(unsigned int i = 0; i < len ; ++i) {
++count[items[i]];
}

//Modifiying each count such that each element at each index stors the sum of previous counts
for(auto it = std::next(count.begin()) ; it != count.end() ; it = std::next(it)) {
*it += *(std::prev(it));
}

//Ouput variable where the sorted element will be stored
std::array<T,len> output;
for(unsigned int i = 0; i < len ; ++i) {
output[count[items[i]] - 1] = items[i];
--count[items[i]];
}

//copying variable to the original array
std::copy(output.begin(),output.end(),items.begin());

}

template<class T>
inline void printElement(const T& items,const std::string& heading) {
std::cout << heading <<std::endl;
//Printing Element to standart output
std::copy(items.begin(),items.end(),
std::ostream_iterator<typename T::value_type>(std::cout," "));
std::cout << std::endl;
}
int main() {
std::array<float,10> elem = {9.2,6.4,2.33,1.0,23.23,4.99,6.53,7.01,4.0,3.2};

printElement(elem,"Unsorted array:");
countingSort(elem);

printElement(elem,"Sorted Array:");

}

Output:
Unsorted array:
  9.2 6.4 2.33 1 23.23 4.99 6.53 7.01 4 3.2
Sorted Array:
  1 2.33 3.2 4 4.99 6.53 6.4 7.01 9.2 23.23
 


More Articles of Hatim Master:

Name Views Likes
Check if removing an edge can divide a Binary Tree in two halves 716 18
C++11 std::has_virtual_destructor 758 18
C++ program to find inorder successor in binary search tree using templates 1399 18
C++ future std::future::future (Constructor) 823 23
C++ Program to Merge Mails 717 21
C++ program for swapping two strings 521 19
C++ Program to count number of lines in a file 887 23
C++ Progam for checking prime numbers 578 15
C++ std::atomic::load 942 22
C++ Program to Find Hash of File 2914 11
C++ program to check if an array represents Inorder of Binary Search tree or not 511 19
C++ future std::future::wait_until 1251 19
C++ future std::future::valid 755 22
C++ program for merge sort 869 18
C++ program to find median of binary search tree in O(n) using templates 629 19
C++11 std::genrate with std::array 685 17
C++ program to convert Binary to decimal,octal,hex 640 19
C++ Program to Check Vowel or Not 502 20
C++ std::find_first_of with vector 895 20
C++ program to find if there is a triplet in a Balanced binary search tree that adds to zero 544 16
C++ Program to Find the Factorial of a Number 620 21
C++ Exception std::exception(Constructor) 793 13
C++ atomic std::atomic::fetch_and 733 20
Check if a Binary Tree contains duplicate subtrees of size 2 or more 1066 17
C++ Program to Print the Fibonacci sequence 602 13
C++ future std::async 868 14
C++ program to check if a given binary tree is height balanced like a red-black tree 667 13
C++ program to insert an element into red black tree using template 2669 20
C++ program for Bubble sort using template 2623 13
C++11 std::genrate_n with std::vector 715 14
C++ program for copying string 456 11
C++ Program to Lowercase to Uppercase 590 15
C++ program to copy the content of the file 603 18
C++ program to count and display the number of lines not starting with the given alphabet in the file 1229 16
Finding Distance between two nodes 962 12
C++ program for removing Punctuation 81 19
C++ program to find distance between two nodes of a binary search tree using templates 547 27
C++ program for solving Quadratic equation 694 26
C++ Program to Display Powers of 2 Using Anonymous Function 608 20
C++ program to add page at the beginning of the PDF 796 14
Print root to leaf paths without using recursion 670 26
C++ Program to Display Calendar 1213 29
C++11 std::genrate with std::forward_list 669 22
C++ std::find_if_not with std::deque 631 19
C++ program to query for ancestor-descendant relationship in a tree 735 13
C++ Program to Find ncR & nPr 752 21
Create loops of even and odd values in a binary tree 716 21
C++ atomic std::atomic::fetch_or 883 23
C++ program to convert kilometers to miles 631 27
C++ Program for comparing string 604 11
C++ Program to Find Factors of Number 554 24
C++ std::genrate with std::vector 688 14
C++ program to find vertical sum in binary tree 705 14
Program for shutdown or Restart PC. 658 20
C++ Program to Remove Words from Sentence 643 17
C++ program for Transpose matrix 668 22
C++ Constructor 777 20
C++ atomic std::atomic::compare_exchange_strong 747 16
Combining two sorted list and creating another sorted list 497 13
C++11 std::is_arithmetic 666 16
C++ program for adding matrices 624 20
C++ program to find check if given sorted sub-sequence exists in binary search tree 613 16
C++ Program to Convert Decimal to Binary, Octal and Hexadecimal 5088 22
C++ Program to Convert Fahrenheit to Celsius 656 21
C++ Program for finding size of string 551 24
C++ program to find a word in the file and print that line along with line number 1277 19
C++ program to reverse a path in binary search tree using queue using templates 859 12
C++ Program to Remove Spaces from String 686 21
C++ Program to Shuffle Deck of Cards 8120 18
C++ is_lock_free 627 16
C++ program to convert image/images to PDF 2347 24
C++ atomic std::atomic::compare_exchange_weak 739 19
C++ program for removing vowels from a string 696 25
C++ program for swapping two variable 565 18
Find Numbers Divisible by Number 1267 17
std::find_if_not with std::deque 654 18
C++ Program to Check Reverse equal Original 588 14
C++ program to count pairs from two binary search trees whose sum is equal to a given value x 498 14
C++ program for Insertion Sort 1110 18
C++ Program to Illustrate Different Set Operations 589 20
C++ Program to One Dimension Array Program 591 20
C++ program to count the number occurance of the given charactor in a file. 59 21
C++ program to print unique words 1479 16
C++11 std::is_abstract 641 26
C++ Program to Count the Number of Each Vowel 508 16
C++ program to find all the prime number in the given interval 517 26
C++ Program to Add Digits of Number 558 18
C++ Program to Print ASCII Values 544 15
Convert a Binary Tree into Doubly Linked List in spiral fashion 728 13
C++11 std::genrate with std::deque 581 20
C++ future std::future::get 865 21
C++ program to count the number of spaces present in a file. 561 19
C++ future std::future::share 753 18
C++ atomic std::atomic::fetch_xor 676 17
C++ program to check for identical binary serach trees without building the trees 464 13
C++ program to convert hexadecimal to binary,decimal,octal 737 22
C++ atomic std::atomic::operator-- 698 14
C++ program for multiplying matrices 522 27
C++ Program to append the file 711 24
C++ program for radix sort 1647 11
C++ program to read the content from a file, count and display the number of alphabets present in it. 517 26
std::find_first_of with std::deque 580 20
C++ program to construct ancestor matrix from a given binary tree using templates 517 15
C++ program to find list of files present in the directory 583 16
C++ std::atomic::store 1206 11
C++ program to find median of binary search tree 729 26
Print all root to leaf paths with there relative positions 652 24
Convert a tree to forest of even nodes 546 17
Convert a Binary Tree to a Circular Doubly Link List 564 16
Merge Two Binary Trees by doing Node Sum 721 23
C++ program to implement linux grep command. 2234 21
C++ Program to Check Leap Year 598 15
C++11 std::genrate_n with std::list 641 28
C++ atomic std::atomic::operator++ 808 23
C++ program to count the number of word in the file 1032 18
C++ Program for Counting sort 791 28
C++ program to get number of page of the pdf file 1212 19
C++ Program to Check Alphabet or Not 420 12
C++11 std::genrate_n with std::array 645 18
C++ future std::future::wait_for 1587 18
C++ program for concatenate String 668 28
std::find_if_not with std::array 719 26
std::find_if_not with std::vector 715 30
C++ Program to Uppercase to Lowercase 517 18
C++ Program to Count Word in Sentence 683 11
C++ program for Subtracting matrices 465 26
C++ Program to Make a Simple Calculator 433 17
Random Number 531 14
C++ program for checking the number is even or odd 651 27
std::find_if_not with std::list 635 28
C++ Program to convert octal to binary,decimal and hex 534 11
C++ program to encrypt a PDF file 1692 13
c++ program to get size of the file 502 15
C++ program to create a doubly linked list from a ternary tree 508 27
std::find_first_of with std::list 983 20
C++ future std::future::wait 791 27
C++ Program to Display Fibonacci Sequence Using Recursion 583 16
C++ Program to Find Armstrong Number in an Interval 683 16
C++ program for Bucket Sort 4228 26
C++ std::genrate with std::list 521 18
C++ program to create a tree with left-child right-sibling representation using templates 1204 20
C++ program to shuffle words of each line of the given file 2051 21
C++ atomic std::atomic::fetch_add 1014 25
C++ program to find simple recursive solution to check whether binary search tree contains dead end using templates 447 15
C++ atomic_flag 771 13
Maximum spiral sum in Binary Tree 613 27
C++ atomic std::atomic::fetch_sub 689 18
C++ program to read content of multiple files and generate one output file 748 22
C++ Program to print Pattern 556 22
C++ program to Decrypt a PDF File 1565 13
C++ Program to Merge Two Files 1699 19
C++ Program for reversing the String 513 24
C++ program to merge two files 679 14
Check if leaf traversal of two Binary Trees is same? 546 20
C++ program to get a page from PDF file 1059 19
C++ program for counting the character in the String 409 17
C++ Program to Check Armstrong Number 609 25
C++ program to check given array of size n can represent binary search tree of n levels or not 632 27
C++ Program to Sort Words in Alphabetic Order 599 24
C++11 std::alignment_of 601 13
C++ program to count the number of new lines present in a file. 583 16
C++ Program to Find HCF & LCM 582 20
C++ program to shuffle lines of the given file 555 12
C++ Program to Find the Size (Resolution) of a Image 1682 20
std::find_if_not with std::forward_list 636 23
C++ program to construct tree from ancestor matrix using templates 857 14
C++ std::atomic::exchange 684 19
std::find_fist_of with std::forward_list 566 15
C++11 std::extent 676 14
C++ program to merge PDF files 2873 22

Comments