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 612 18
C++11 std::has_virtual_destructor 635 18
C++ program to find inorder successor in binary search tree using templates 1234 18
C++ future std::future::future (Constructor) 719 23
C++ Program to Merge Mails 611 21
C++ program for swapping two strings 436 19
C++ Program to count number of lines in a file 744 23
C++ Progam for checking prime numbers 502 15
C++ std::atomic::load 800 22
C++ Program to Find Hash of File 2042 11
C++ program to check if an array represents Inorder of Binary Search tree or not 450 19
C++ future std::future::wait_until 1079 19
C++ future std::future::valid 676 22
C++ program for merge sort 673 18
C++ program to find median of binary search tree in O(n) using templates 550 19
C++11 std::genrate with std::array 618 17
C++ program to convert Binary to decimal,octal,hex 555 19
C++ Program to Check Vowel or Not 417 20
C++ std::find_first_of with vector 750 20
C++ program to find if there is a triplet in a Balanced binary search tree that adds to zero 475 16
C++ Program to Find the Factorial of a Number 523 21
C++ Exception std::exception(Constructor) 712 13
C++ atomic std::atomic::fetch_and 636 20
Check if a Binary Tree contains duplicate subtrees of size 2 or more 892 17
C++ Program to Print the Fibonacci sequence 494 13
C++ future std::async 724 14
C++ program to check if a given binary tree is height balanced like a red-black tree 601 13
C++ program to insert an element into red black tree using template 2240 20
C++ program for Bubble sort using template 2032 13
C++11 std::genrate_n with std::vector 644 14
C++ program for copying string 386 11
C++ Program to Lowercase to Uppercase 508 15
C++ program to copy the content of the file 507 18
C++ program to count and display the number of lines not starting with the given alphabet in the file 1029 16
Finding Distance between two nodes 812 12
C++ program for removing Punctuation 81 19
C++ program to find distance between two nodes of a binary search tree using templates 460 27
C++ program for solving Quadratic equation 598 26
C++ Program to Display Powers of 2 Using Anonymous Function 486 20
C++ program to add page at the beginning of the PDF 693 14
Print root to leaf paths without using recursion 608 26
C++ Program to Display Calendar 984 29
C++11 std::genrate with std::forward_list 584 22
C++ std::find_if_not with std::deque 547 19
C++ program to query for ancestor-descendant relationship in a tree 584 13
C++ Program to Find ncR & nPr 642 21
Create loops of even and odd values in a binary tree 612 21
C++ atomic std::atomic::fetch_or 775 23
C++ program to convert kilometers to miles 544 27
C++ Program for comparing string 517 11
C++ Program to Find Factors of Number 486 24
C++ std::genrate with std::vector 614 14
C++ program to find vertical sum in binary tree 617 14
Program for shutdown or Restart PC. 584 20
C++ Program to Remove Words from Sentence 525 17
C++ program for Transpose matrix 576 22
C++ Constructor 645 20
C++ atomic std::atomic::compare_exchange_strong 669 16
Combining two sorted list and creating another sorted list 434 13
C++11 std::is_arithmetic 573 16
C++ program for adding matrices 554 20
C++ program to find check if given sorted sub-sequence exists in binary search tree 505 16
C++ Program to Convert Decimal to Binary, Octal and Hexadecimal 3706 22
C++ Program to Convert Fahrenheit to Celsius 551 21
C++ Program for finding size of string 483 24
C++ program to find a word in the file and print that line along with line number 964 19
C++ program to reverse a path in binary search tree using queue using templates 795 12
C++ Program to Remove Spaces from String 608 21
C++ Program to Shuffle Deck of Cards 6392 18
C++ is_lock_free 544 16
C++ program to convert image/images to PDF 1928 24
C++ atomic std::atomic::compare_exchange_weak 618 19
C++ program for removing vowels from a string 581 25
C++ program for swapping two variable 479 18
Find Numbers Divisible by Number 1144 17
std::find_if_not with std::deque 567 18
C++ Program to Check Reverse equal Original 536 14
C++ program to count pairs from two binary search trees whose sum is equal to a given value x 443 14
C++ program for Insertion Sort 1000 18
C++ Program to Illustrate Different Set Operations 496 20
C++ Program to One Dimension Array Program 468 20
C++ program to count the number occurance of the given charactor in a file. 59 21
C++ program to print unique words 1238 16
C++11 std::is_abstract 570 26
C++ Program to Count the Number of Each Vowel 448 16
C++ program to find all the prime number in the given interval 431 26
C++ Program to Add Digits of Number 477 18
C++ Program to Print ASCII Values 447 15
Convert a Binary Tree into Doubly Linked List in spiral fashion 618 13
C++11 std::genrate with std::deque 501 20
C++ future std::future::get 754 21
C++ program to count the number of spaces present in a file. 471 19
C++ future std::future::share 640 18
C++ atomic std::atomic::fetch_xor 594 17
C++ program to check for identical binary serach trees without building the trees 424 13
C++ program to convert hexadecimal to binary,decimal,octal 629 21
C++ atomic std::atomic::operator-- 600 14
C++ program for multiplying matrices 466 27
C++ Program to append the file 587 24
C++ program for radix sort 1354 11
C++ program to read the content from a file, count and display the number of alphabets present in it. 469 26
std::find_first_of with std::deque 503 20
C++ program to construct ancestor matrix from a given binary tree using templates 444 15
C++ program to find list of files present in the directory 506 16
C++ std::atomic::store 1016 11
C++ program to find median of binary search tree 609 26
Print all root to leaf paths with there relative positions 566 24
Convert a tree to forest of even nodes 452 17
Convert a Binary Tree to a Circular Doubly Link List 482 16
Merge Two Binary Trees by doing Node Sum 640 23
C++ program to implement linux grep command. 1518 21
C++ Program to Check Leap Year 520 15
C++11 std::genrate_n with std::list 544 28
C++ atomic std::atomic::operator++ 713 23
C++ program to count the number of word in the file 848 18
C++ Program for Counting sort 669 28
C++ program to get number of page of the pdf file 929 19
C++ Program to Check Alphabet or Not 361 12
C++11 std::genrate_n with std::array 545 18
C++ future std::future::wait_for 1372 18
C++ program for concatenate String 606 28
std::find_if_not with std::array 628 26
std::find_if_not with std::vector 627 30
C++ Program to Uppercase to Lowercase 446 18
C++ Program to Count Word in Sentence 590 11
C++ program for Subtracting matrices 407 26
C++ Program to Make a Simple Calculator 371 17
Random Number 461 14
C++ program for checking the number is even or odd 530 27
std::find_if_not with std::list 544 28
C++ Program to convert octal to binary,decimal and hex 428 11
C++ program to encrypt a PDF file 1410 13
c++ program to get size of the file 430 15
C++ program to create a doubly linked list from a ternary tree 436 27
std::find_first_of with std::list 874 20
C++ future std::future::wait 705 27
C++ Program to Display Fibonacci Sequence Using Recursion 487 16
C++ Program to Find Armstrong Number in an Interval 598 16
C++ program for Bucket Sort 3932 26
C++ std::genrate with std::list 452 18
C++ program to create a tree with left-child right-sibling representation using templates 909 20
C++ program to shuffle words of each line of the given file 1838 21
C++ atomic std::atomic::fetch_add 874 25
C++ program to find simple recursive solution to check whether binary search tree contains dead end using templates 369 15
C++ atomic_flag 677 13
Maximum spiral sum in Binary Tree 556 27
C++ atomic std::atomic::fetch_sub 617 18
C++ program to read content of multiple files and generate one output file 655 22
C++ Program to print Pattern 472 22
C++ program to Decrypt a PDF File 1274 13
C++ Program to Merge Two Files 1499 19
C++ Program for reversing the String 413 24
C++ program to merge two files 567 14
Check if leaf traversal of two Binary Trees is same? 462 20
C++ program to get a page from PDF file 940 19
C++ program for counting the character in the String 338 17
C++ Program to Check Armstrong Number 512 25
C++ program to check given array of size n can represent binary search tree of n levels or not 555 27
C++ Program to Sort Words in Alphabetic Order 508 24
C++11 std::alignment_of 511 13
C++ program to count the number of new lines present in a file. 436 16
C++ Program to Find HCF & LCM 476 20
C++ program to shuffle lines of the given file 407 12
C++ Program to Find the Size (Resolution) of a Image 1015 20
std::find_if_not with std::forward_list 563 23
C++ program to construct tree from ancestor matrix using templates 783 14
C++ std::atomic::exchange 601 19
std::find_fist_of with std::forward_list 473 15
C++11 std::extent 567 14
C++ program to merge PDF files 2335 22

Comments