Scribd
Upload
11 views46 pages

Sorting

The document explains the Counting Sort algorithm, a non-comparison based sorting technique that sorts by counting the occurrences of distinct key values. It details the steps involved in the algorithm, including maintaining count and output arrays, and emphasizes its time complexity of O(n+k) while noting its limitations, such as inefficiency with large value ranges and the use of extra space. Additionally, the document briefly mentions Shell Sort without providing detailed information.

Uploaded by

parasgarag123
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
11 views46 pages

Sorting

The document explains the Counting Sort algorithm, a non-comparison based sorting technique that sorts by counting the occurrences of distinct key values. It details the steps involved in the algorithm, including maintaining count and output arrays, and emphasizes its time complexity of O(n+k) while noting its limitations, such as inefficiency with large value ranges and the use of extra space. Additionally, the document briefly mentions Shell Sort without providing detailed information.

Uploaded by

parasgarag123
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 46

Sorting :

Counting Sort / Count Sort

•In this lecture, we will discuss the counting sort Algorithm. Counting sort is a
sorting technique that is based on the keys between specific ranges.

•This sorting technique doesn't perform sorting by comparing elements. It


performs sorting by counting objects having distinct key values like hashing.
Counting Sort Algorithm

The counting sort algorithm assumes that the input is relatively smaller so the algorithm is as
follows −

Step 1 − Maintain two arrays, one with the size of input elements without repetition to store
the count values and other with the size of the input array to store the output.

Step 2 − Initialize the count array with all zeroes and keep the output array empty.

Step 3 − Every time an element occurs in the input list, increment the corresponding counter
value by 1, until it reaches the end of the input list.

Step 4 − Now, in the output array, every time a counter is greater than 0, add the element at
its respective index, i.e. if the counter of ‘0’ is 2, ‘0’ added at the 2nd position (i.e. 1st index)
of the output array. Then decrement the counter value by 1.

Step 5 − Repeat Step 4 until all the counter values become 0. The list obtained is the output
list.
Working of Counting Sort:

1: Find out the maximum element say max range (k)

1 3 2 3 4 1 6 4 3
0 1 2 3 4 5 6 7 8
index

k 6

2: Initialize an array of length max+1 with all elements 0. This array is used for storing
the count of the elements in the array.

Count [ ]
3: Store the count of each element at their respective index in Count array
1 3 2 3 4 1 6 4 3
Index 0 1 2 3 4 5 6 7 8

For ( i=0; i<n; i++)


{
++ count [ a[i] ] ;
}
0 2 1 3 2 0 1
Count array
Index 0 1 2 3 4 5 6
4: Store cumulative sum of the elements of the count array. It helps in placing the
elements into the correct index of the sorted array.
0 2 1 3 2 0 1
Index 0 1 2 3 4 5 6
We are going to update this count array , just to know the actual place value in
sorted array .
0 2 1 3 2 0 1 Updated count
0 2
same + +
2 1
0 2 3 6 8 8 9

Index 0 to 6

For ( i=1; i< = k; i++)


{
count [ i ] = count [ i ] + count [ i -1] ;
}
5: Build the output array:
1 3 2 3 4 1 6 4 3
Index 0 1 2 3 4 5 6 7 8

Updated count 0 2 3 6 8 8 9

6-1=5
0 2 3 5 8 8 9
How: just scan the array from right to left ( maintain the stability property) , 3 is
there just go to the index 3 in updated count array which is 6, than do ( 6-1) 5,
becoz this is the count value not index value, put this 3 key at b[ 5].
For ( i=n-1; i>=0; i--)
{
B[-- count [ a[i] ] ] = a[ i ] ;
}

3
Array B [ ]
index 0 1 2 3 4 5 6 7 8
Sorted array
1 1 2 3 3 3 4 4 6
index 0 1 2 3 4 5 6 7 8

Time Complexity : O(n+k)

Disadvantages of Counting Sort


•Counting sort doesn’t work on decimal values.

•Counting sort is inefficient if the range of values to be sorted is very large.

•Counting sort is not an In-place sorting algorithm, It uses extra space for
sorting the array elements.
index
Shell Sort :
0 1 2 3 4 5 6 7 8
24 30 14 20 32 6 8 4 1

i j
index
Shell Sort : 0
24
1
30
2
14
3
20
4
32
5
6
6
8
7
4
8
1

You might also like