VISVESVARAYA TECHNOLOGICAL

UNIVERSITY
“JNANA SANGAMA”, BELAGAVI- 590018,
KARNATAKA, INDIA

Design And Analysis Of Algorithms report on [BCS401]

“COUNTING BY SORTING”
Submitted in partial fulfilment of the
requirements for the award of degree of
BACHELOR OF ENGINEERING IN
COMPUTER SCIENCE AND
ENGINEERING
(DATA SCIENCE)

Submitted By
Harshil M(1AT22CD018)
Hoysala K R (1AT22CD020)

Under the Guidance of

Dr.Jyoti Metan
Associate Professor
Dept. of ISE,
ATRIA I.T.

ATRIA INSTITUTE OF TECHNOLOGY

(Affiliated to Visvesvaraya
Technological University) ASKB
Campus, Anand Nagar,
Bengaluru-560024
Department of Computer Science and Engineering
(Data Science)

CERTIFICATE
Certified that the project work entitled “COUNTING BY SORTING ”
carried out by Harshil M (1AT22CD018), Hoysala K R (1AT22CD020), are
Bonafide students of Department of Computer Science and Engineering (Data
Science), ATRIA I.T., Bengaluru, in partial fulfilment for the award of
Degree of Bachelor of Engineering in Computer Science & Engineering
(Data science) of Visvesvaraya Technological University, Belagavi, during
the academic year 2023-24. It is certified that all corrections/suggestions
indicated for Internal Assessment have been incorporated in the report
deposited in the department library. The mini project report has been approved
as it satisfies the academic requirements in respect of project work prescribed
for the said degree.

Dr.Jyoti Metan Dr. Deepak NR

Associate Professor &
Professor HOD
Department of Department of
ISE Atria I.T. CSE(DS) Atria
I.T.

External Viva
Signature with date

1. Name of Examiner

2.Name of Examiner
 DECLARATION
We Harshil M(1AT22CD018),Hoysala KR(1AT22CD020) student of 4th
semester Bachelor of Engineering, Department of Information Science and
Engineering, Atria Institute of Technology, Bengaluru, would hereby declare that
the Design And Analysis Of Algorithms animation presentation entitled
“COUNTING BY SORTING” has been carried out by us at Atria Institute of
Technology, Bengaluru, and submitted in partial fulfilment of the course
requirement for the award of degree of Bachelor of Engineering in Information
Science and Engineering of Visvesvaraya Technological University, Belagavi,
during the academic year 2023-24.
We further declare that, to the best of our knowledge and belief, the work
embodied in this report has not been submitted to any other university or
institution for the award of any other degree.

Signature of the
student

Place :Bengaluru Harshil M

Date:06.08.2024 (1AT22CD018)

Hoysala K R
(1AT22CD020)

I
 ABSTRACT

Counting and sorting are foundational operations in computer science and

mathematics, crucial for organizing and analyzing data efficiently. Counting
involves determining the number of elements in a set or collection, ranging from
simple item counts to more complex frequency analyses, where the goal is to
identify how often each distinct element appears. This process is vital in statistical
analysis, data mining, and algorithm performance evaluation. For instance, in the
Counting Sort algorithm, the frequency of each element is tallied to help sort the
data effectively. Sorting, on the other hand, arranges elements in a specified order,
typically ascending or descending. Efficient sorting is essential for data retrieval and
organization, with various algorithms each offering unique approaches. Bubble Sort,
for example, repeatedly compares and swaps adjacent elements, making it simple
but less efficient for large datasets. Merge Sort divides the data into smaller subsets,
sorts them, and then merges them, providing consistent performance. Quick Sort
selects a pivot element to partition the data into subsets and sorts them recursively,
known for its speed and practicality. Heap Sort builds a heap from the dataset and
then extracts the maximum element to construct the sorted array. Both counting and
sorting are integral to optimizing data processing, enhancing algorithm efficiency,
and managing data effectively across diverse applications.

II
 ACKNOWLEDGEMENT

I am grateful to our institution, Atria Institute of Technology, for having

provided us with the facilities to successfully complete the Design And
Analysis Of Algorithms animation presentation on Counting By Sort.

We thank Dr. Deepak NR, HOD, CSE(DS) for providing us all the
necessary facilities for the successful completion of our Presentation.
Deadlines play a very important role in the successful completion of the
academic project on time, efficiently and effectively.

We take this opportunity to express our deep sense of gratitude to our guide
and coordinators Dr.Jyoti Metan , Associate Professor, Department of
ISE for their valuable guidance and help throughout the course of the
academic. They have always been patient with us and helped immensely in
completing the task on hand. We also thank them for their immense support,
guidance, specifications & ideas without which seminar would have been
completed without full merit.

Last but not least from the Department of Information Science and
Engineering, teaching and non-teaching staffs for their constant
encouragement, support, patience, and endurance shown during the
preparation of this report were remarkable. We also thank the management.

Finally, we thank our parents and friends for their motivation, morale
and material support.

III
CHAPTER TITLE PAGE
NO
DECLARATION I
ABSTRACT II
ACKNOWLEDGEMENT III

1 INTRODUCTION 1

2. COMPARISON COUNTING 2

3 TIME COMPLEXITY OF COUNTING SORT 3

4 DISTRIBUITION COUNTING 4

5 ALGORITHM OF COMPARISON SORT 5

6 EXAMPLE OF COUNTING SORT 6

7 CONCLUSION 7

TABLE OF CONTENTS
 LIST OF FIGURES

FIGURE TITLES PAGE NO

1.1 Example of comparison sort 2

3.1 Example of time complexity 3

4.2 Example of Distribution sort 4

5.1 Algorithm of comparison sort 5

5.2 Algorithm of Distribution sort 5

Example for comparison sort
6.1 6
Example for counting sort
6.2 6
BACKTRACKING 2023-2024

INTRODUCTION

Sorting by Counting, often referred to as Counting Sort, is a non-comparison-based sorting algorithm

that is particularly effective when dealing with integers within a limited range. Unlike comparison-
based sorting algorithms like Quick Sort or Merge Sort, Counting Sort relies on counting the
occurrences of each distinct value to determine their positions in the sorted output. This makes it both
time-efficient and space-efficient for specific scenarios.
The fundamental concept behind Counting Sort is straightforward: rather than comparing elements
directly, the algorithm counts the number of occurrences of each distinct element. It then uses this
count to place each element in its correct position in the sorted array. This approach is beneficial
when the range of the numbers (i.e., the difference between the maximum and minimum values) is
not significantly larger than the number of elements to be sorted.
Here’s a step-by-step breakdown of how Counting Sort works:
1. Determine the Range: First, identify the maximum and minimum values in the input array.
This range will dictate the size of the counting array.
2. Create the Counting Array: Create an auxiliary array, often called the counting array,
where the index represents the value from the input array, and the value at that index
represents the count of occurrences of that value.
3. Populate the Counting Array: Traverse the input array and increment the corresponding
index in the counting array for each value encountered. This step essentially builds a
frequency distribution of the input values.
4. Compute Cumulative Counts: Modify the counting array by updating it to reflect the
cumulative count. This transformation will help in placing each element in its correct position
in the sorted array.
5. Build the Output Array: Using the cumulative count information, place each element from
the original array into its correct position in the output array. This step involves iterating
through the input array and using the counting array to place elements in their sorted
positions.
6. Copy the Sorted Array: Finally, copy the sorted elements from the output array back to the
original array if needed.
Counting Sort is particularly efficient when the range of input values is not excessively larger than the
number of elements to be sorted. Its time complexity is O(n + k), where n is the number of elements
in the input array and k is the range of the input values. However, it is not suitable for sorting data
with a large range or non-integer values. Despite its limitations, Counting Sort is a valuable tool in
Dept. of CSE(DS) Page 1
Atria IT
BACKTRACKING 2023-2024

scenarios where it is applicable, providing linear time complexity and a straightforward

implementation.

COMPARISON COUNTING

Definition:
Comparison counting involves tracking and summing the number of comparisons made
between elements during the sorting process. Comparison Counting involves tallying the
number of comparisons performed between elements during the execution of a sorting
algorithm. It is a crucial metric for analyzing and understanding the efficiency of
comparison-based sorting algorithms. In essence, it quantifies the number of times pairs of
elements are compared to determine their relative order.
Purpose :
It helps in evaluating and comparing the efficiency of different sorting algorithms based on the
number of comparisons they perform is to evaluate the efficiency of comparison-based sorting
algorithms by quantifying the number of element comparisons they perform. This metric helps in
analyzing the algorithm's performance, understanding its time complexity, and comparing different
sorting algorithms based on their operational efficiency.
Example

Figure 1.1 Example of comparison counting

Dept. of CSE(DS) Page 1

Atria IT
BACKTRACKING 2023-2024

Time Complexity of Counting Sort

Time Complexity:
TOh(et+imke) complexity of the counting sort algorithm is O(n+k), where n is the size of the
input array and k is the range of the input values. This makes it a highly efficient algorithm,
especially when the range of input values is small compared to the size of the input array.

Space Complexity:
The space complexity of the counting sort algorithm is also O(n+k), as it requires an
additional array to store the count and cumulative frequency of the input elements.

Stable Sorting :
Counting sort is a stable sorting algorithm, which means that it preserves the relative order of
elements with equal values. This property can be important in certain applications where the
original order of the elements needs to be maintained.

Figure 3.1 Time complexity

Dept. of CSE(DS) Page 1

Atria IT
COUNTING BY SORT 2023-2024

DISTRIBUITION COUNTING

Definition :
Counting sort is a non-comparative integer sorting algorithm that operates by counting the
occurrences of each unique value in the input array. It then uses these counts to determine the
position of each element in the sorted output array. This method is efficient when the range
of input values is limited compared to the number of elements, making it suitable for sorting
large datasets with a small range of values.

Purpose :
Distribution counting sort aims to efficiently sort integers or categorical data by
leveraging the frequency of each value. It works by counting the occurrences of each
value in the input and then using these counts to determine the final position of each
element in the sorted output. This method is particularly useful when the range of
possible values is small compared to the number of elements, ensuring fast sorting
performance.

Example :

FIGURE 4.1

Dept. of CSE(DS) Page 4

Atria IT
COUNTING BY SORT 2023-2024

Algorithm of Comparison and Distribution Counting

Figure 5.2 Algorithm of distribution sort

Dept. of CSE(DS) Page 5
Atria IT
COUNTING BY SORT 2023-2024

Figure 6.1 example of counting by sort

Figure 6.2 example of counting sort

Dept. of CSE(DS) Page 6

Atria IT
COUNTING BY SORT 2023-2024

CONCLUSION

In conclusion, counting and sorting are fundamental processes that underpin much of data
management and analysis in computer science. Counting provides the necessary groundwork
for understanding the frequency and distribution of data elements. By tallying occurrences, it
enables more informed decisions about how to process and analyze data. This initial step is
particularly critical in algorithms like Counting Sort, where the frequency of each element
dictates the arrangement of the sorted output. The ability to accurately count and track
occurrences ensures that the subsequent sorting process is both efficient and effective,
allowing for reliable data organization.

Sorting, as a complementary process, refines the organization of data by arranging elements

into a specified order, typically ascending or descending. This ordered arrangement is
essential for various applications, including search operations, data retrieval, and efficient
processing. Different sorting algorithms, such as Quick Sort, Merge Sort, and Heap Sort,
each offer unique advantages and are suited to different types of datasets and scenarios. For
instance, Quick Sort is renowned for its speed and efficiency with large datasets, while
Merge Sort guarantees predictable performance and stability. The choice of sorting algorithm
can significantly impact the performance and scalability of data processing tasks.

Ultimately, the interplay between counting and sorting enhances data management by
providing a structured approach to handling large volumes of information. Counting lays the
foundation by quantifying the data elements, while sorting organizes them in a way that
optimizes access and processing. Together, these operations support a wide range of
applications, from simple data analysis to complex algorithmic solutions. Their integration
ensures that data is not only accurately represented but also efficiently manipulated,
facilitating more effective decision-making and problem-solving across various domains.
Thus, mastering both counting and sorting is essential for anyone involved in data-intensive
fields, ensuring that data handling is both precise and efficient.

Dept. of CSE(DS) Page 7

Atria IT
COUNTING BY SORT 2023-2024

Dept. of CSE(DS) Page 8

Atria IT