COUNTING SORT
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
seminar surveyer
Active In SP
**

Posts: 3,541
Joined: Sep 2010
#1
13-01-2011, 11:57 AM




Abstract

Counting sort is a linear time sorting algorithm used to sort items when they belong to a fixed and finite set. Integers which lie in a fixed interval, say k1 to k2, are examples of such items.
The algorithm proceeds by defining an ordering relation between the items from which the set to be sorted is derived (for a set of integers, this relation is trivial).Let the set to be sorted be called A. Then, an auxiliary array with size equal to the number of items in the superset is defined, say B. For each element in A, say e, the algorithm stores the number of items in A smaller than or equal to e in B(e). If the sorted set is to be stored in an array C, then for each e in A, taken in reverse order, C[B[e]] = e. After each such step, the value of B(e) is decremented.

Counting sort is a stable sort and has a running time of Θ(n+k), where n and k are the lengths of the arrays A (the input array) and C (the counting array), respectively. In order for this algorithm to be efficient, k must not be much larger than n.
The indices of C must run from the minimum to the maximum value in A to be able to index C directly with the values of A. Otherwise, the values of A will need to be translated (shifted), so that the minimum value of A matches the smallest index of C. (Translation by subtracting the minimum value of A from each element to get an index into C therefore gives a counting sort. If a more complex function is used to relate values in A to indices into C, it is a bucket sort.) If the minimum and maximum values of A are not known, an initial pass of the data will be necessary to find these.



Read more:
en.wikipediawiki/Counting_sort
cse.iitk.acusers/dsrkg/cs210/applets/sortingII/countingSort/count.html
personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/countingSort.htm


Reply
Annapurna pulipati
Active In SP
**

Posts: 2
Joined: Jan 2011
#2
20-01-2011, 07:17 PM

send complete seminar and presentation
Reply
seminar surveyer
Active In SP
**

Posts: 3,541
Joined: Sep 2010
#3
22-01-2011, 12:10 PM

sorry yaar
i couldn't find a complete report here. why don't you visit the links given? those should have complete details i hope.
Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK HERE

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page

Quick Reply
Message
Type your reply to this message here.


Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  Insertion Sort PPT study tips 0 363 19-02-2013, 10:15 AM
Last Post: study tips
  Seminar on Topological Sort pdf project girl 0 329 10-12-2012, 12:35 PM
Last Post: project girl
  IMPLEMENTATION OF TOPOLOGICAL SORT seminar tips 0 315 15-11-2012, 04:31 PM
Last Post: seminar tips
  Radix Sort seminar ideas 1 641 28-08-2012, 05:07 PM
Last Post: seminar flower
  Bubble Sort seminar flower 0 371 27-07-2012, 02:12 PM
Last Post: seminar flower
  Quick Sort in Java seminar flower 0 449 18-07-2012, 03:36 PM
Last Post: seminar flower
  algorithm,Analysis of INSERTION SORT,Hiring Problem,Quicksort,knapsack problem,Greedy project report helper 0 2,110 20-10-2010, 10:47 AM
Last Post: project report helper