amanraj1608 / dsa-implementation Goto Github PK

Overview:

Our repository currently offers a variety of sorting algorithms, such as bubble sort, insertion sort, merge sort, quick sort, and selection sort. However, an important sorting algorithm that is missing from our collection is Counting Sort. Counting Sort is known for its efficiency in scenarios where the range of input values is known and relatively small compared to the number of elements to be sorted. It operates in linear time complexity, making it one of the fastest sorting algorithms for such scenarios.

Proposal:

This issue proposes the addition of Counting Sort to our repository's collection of sorting algorithms. By incorporating Counting Sort, we can provide users with a more comprehensive suite of sorting options and showcase the versatility of different sorting techniques.

Tasks:

1. Implement Counting Sort: Write an implementation of Counting Sort in C++, Python, Java, or any other language supported by our repository. Ensure that the implementation adheres to best practices and follows a clear, understandable coding style.

2. Documentation: Provide comprehensive documentation for the Counting Sort implementation. This documentation should include details about the algorithm's time complexity analysis, use cases, and any limitations or considerations for its usage. Clear and concise documentation will help users understand when and how to use Counting Sort effectively.

3. Testing: Write test cases to verify the correctness and performance of the Counting Sort implementation. Thorough testing is essential to ensure that the algorithm behaves as expected and performs efficiently across various input scenarios.

4. Integration: Integrate the Counting Sort implementation into our repository's existing sorting algorithms module. Ensure consistency in code style and organization to maintain the overall quality of the codebase.

5. Update Documentation: Update relevant documentation files, such as README.md, to reflect the addition of Counting Sort. Provide usage instructions for users, including examples demonstrating how to use Counting Sort in their projects.

Expected Outcome:

By addressing this issue, we aim to enhance the functionality and completeness of our repository's sorting algorithms collection. The addition of Counting Sort will empower users with another valuable tool for efficient data sorting, further solidifying our repository as a comprehensive resource for sorting algorithms.

Contributors are encouraged to take on this task and contribute their implementation of Counting Sort to our repository. Let's collaborate to expand and improve our sorting algorithms library!

C++ Implementation:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void countingSort(vector<int>& arr) {
    int maxElement = *max_element(arr.begin(), arr.end());
    int minElement = *min_element(arr.begin(), arr.end());

    int range = maxElement - minElement + 1;
    vector<int> count(range), output(arr.size());

    for (int i = 0; i < arr.size(); i++) {
        count[arr[i] - minElement]++;
    }

    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }

    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i] - minElement] - 1] = arr[i];
        count[arr[i] - minElement]--;
    }

    for (int i = 0; i < arr.size(); i++) {
        arr[i] = output[i];
    }
}

int main() {
    vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
    countingSort(arr);

    cout << "Sorted array: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}