Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Counting Sort

Count­ing Sort is an sort­ing algo­rithm, which sorts the inte­gers( or Objects) given in a spe­cific range.

Algo­rithm: Time Com­plex­ity O(n)

  • Take two arrays, Count[] and Result[] and given array is input[].
  • Count[] will store the counts of each inte­ger in the given array.
  • Update the Count[] so that each index will store the sum till pre­vi­ous step. (Count[i]=Count[i] + Count[i-1]). Now updated Count[] array will reflect the actual posi­tion of each inte­ger in Result[].
  • Now nav­i­gate the input array tak­ing one ele­ment at a time, Count[input[i]] will tell you the index posi­tion of input[i] in Result[]. When you do that, decrease the count in Count[input[i]] by 1. See Example




Out­put :

Orginal Array [2, 1, 4, 5, 7, 1, 1, 8, 9, 10, 11, 14, 15, 3, 2, 4]
Sorted Array : [0, 1, 1, 1, 2, 2, 3, 4, 4, 5, 7, 8, 9, 10, 11, 14, 15]

You may also like...

  • Wen­jie Cao

    Thanks,it did help me~

    • tuto­ri­al­hori­zon

      Thanks Wen­jie, good to hear that it was helpful

  • anchal dhi­man

    well explain

  • Umut Dön­mez

    ty for this code Have a nice day

    • tuto­ri­al­hori­zon

      You r welcome.

  • May

    orig­i­nal array doesn’t have a ‘0’, where sorted array has that as an extra element