This repository contains implementations of sorting algorithms along with their optimized versions and .txt files containing the execution time of the sorting algorithms for random lists with 10,000 elements.
This file contains 100 lists with random integers (from 0 to 10,000) so that the tests for each sorting algorithm can be done with the same lists, ensuring consistency for future algorithms that will be implemented.
In logarithmic scale:
Counting Sort is an efficient, non-comparative sorting algorithm suitable for ordering a collection of data where the elements belong to a known and limited range of values. The algorithm counts the occurrence of each value and uses these counts to determine the exact position of each element in the sorted list.
- Identify the minimum and maximum values: First, the minimum and maximum values in the list are found to determine the range of values.
- Initialize the counting array: A counting array is created with a size adequate to store the count of each distinct value.
- Count the occurrences: The frequency of each value in the original list is counted and these counts are stored in the counting array.
- Update the original list: The linked list is updated with the sorted elements using the counting array.
Suppose we have a linked list of numbers [4, 2, 2, 8, 3, 3, 1] and we want to sort it using Counting Sort.
First, identify the minimum and maximum values in the list:
Minimum value: 1
Maximum value: 8Create a counting array with size 8 (from 1 to 8), initialized with zeros:
Count = [0, 0, 0, 0, 0, 0, 0, 0]Count the frequency of each value in the original list:
Original list: [4, 2, 2, 8, 3, 3, 1]
Count: [1, 2, 2, 1, 0, 0, 0, 1]Use the counting array to update the elements in the linked list:
Sorted list: [1, 2, 2, 3, 3, 4, 8]