4 - Non-Comparison Based Sorting
Most sorting algorithms we've discussed so far are comparison-based, meaning they sort elements by comparing them with each other. However, there's another category of sorting algorithms that don't rely on comparisons. These non-comparison based sorting algorithms can achieve better time complexity than the theoretical lower bound of O(n log n) for comparison-based sorts, but they come with their own limitations.
Counting Sort
Counting Sort is an integer sorting algorithm that works by counting the number of occurrences of each element and using that information to determine their positions in the output array.
How It Works
- Find the range of input elements (minimum to maximum).
- Create a counting array to store the count of each unique element.
- Modify the counting array to store the cumulative count (position information).
- Build the output array using the counting array.
- Copy the output array back to the original array.
Implementation
public static void CountingSort(int[] array)
{
if (array.Length == 0)
return;
// Find the minimum and maximum values
int min = array[0];
int max = array[0];
for (int i = 1; i < array.Length; i++)
{
if (array[i] < min)
min = array[i];
else if (array[i] > max)
max = array[i];
}
// Create a counting array
int range = max - min + 1;
int[] count = new int[range];
// Count occurrences of each element
for (int i = 0; i < array.Length; i++)
{
count[array[i] - min]++;
}
// Reconstruct the sorted array
int index = 0;
for (int i = 0; i < range; i++)
{
while (count[i] > 0)
{
array[index++] = i + min;
count[i]--;
}
}
}
Stable Counting Sort
The above implementation is not stable. Here's a stable version:
public static void StableCountingSort(int[] array)
{
if (array.Length == 0)
return;
// Find the minimum and maximum values
int min = array[0];
int max = array[0];
for (int i = 1; i < array.Length; i++)
{
if (array[i] < min)
min = array[i];
else if (array[i] > max)
max = array[i];
}
// Create a counting array
int range = max - min + 1;
int[] count = new int[range];
// Count occurrences of each element
for (int i = 0; i < array.Length; i++)
{
count[array[i] - min]++;
}
// Modify count array to store position information
for (int i = 1; i < range; i++)
{
count[i] += count[i - 1];
}
// Build the output array
int[] output = new int[array.Length];
for (int i = array.Length - 1; i >= 0; i--)
{
output[count[array[i] - min] - 1] = array[i];
count[array[i] - min]--;
}
// Copy the output array back to the original array
Array.Copy(output, array, array.Length);
}
Characteristics
- Time Complexity: O(n + k), where n is the number of elements and k is the range of input
- Space Complexity: O(n + k)
- Stability: Can be implemented as stable
- Limitations: Only works for integers or data that can be mapped to integers within a reasonable range
When to Use
- When sorting integers with a limited range
- When the range of input values is not significantly larger than the number of elements
- When stability is required
Radix Sort
Radix Sort extends the idea of Counting Sort to handle larger integers by sorting them digit by digit, from the least significant digit to the most significant digit.
How It Works
- Find the maximum number to determine the number of digits.
- For each digit position, starting from the least significant digit: a. Sort the elements based on that digit using a stable sort (like Counting Sort).
Implementation
public static void RadixSort(int[] array)
{
if (array.Length == 0)
return;
// Find the maximum number to determine the number of digits
int max = array[0];
for (int i = 1; i < array.Length; i++)
{
if (array[i] > max)
max = array[i];
}
// Do counting sort for every digit
for (int exp = 1; max / exp > 0; exp *= 10)
{
CountingSortByDigit(array, exp);
}
}
private static void CountingSortByDigit(int[] array, int exp)
{
int[] output = new int[array.Length];
int[] count = new int[10]; // 0-9 digits
// Count occurrences of each digit
for (int i = 0; i < array.Length; i++)
{
int digit = (array[i] / exp) % 10;
count[digit]++;
}
// Change count[i] so that it contains the position of this digit in output
for (int i = 1; i < 10; i++)
{
count[i] += count[i - 1];
}
// Build the output array
for (int i = array.Length - 1; i >= 0; i--)
{
int digit = (array[i] / exp) % 10;
output[count[digit] - 1] = array[i];
count[digit]--;
}
// Copy the output array back to the original array
Array.Copy(output, array, array.Length);
}
Handling Negative Numbers
The above implementation works only for non-negative integers. To handle negative numbers:
public static void RadixSortWithNegatives(int[] array)
{
if (array.Length == 0)
return;
// Separate negative and non-negative numbers
List<int> negatives = new List<int>();
List<int> nonNegatives = new List<int>();
foreach (int num in array)
{
if (num < 0)
negatives.Add(-num); // Make negative numbers positive for sorting
else
nonNegatives.Add(num);
}
// Convert lists back to arrays for sorting
int[] negativesArray = negatives.ToArray();
int[] nonNegativesArray = nonNegatives.ToArray();
// Sort both arrays
RadixSort(negativesArray);
RadixSort(nonNegativesArray);
// Combine the results: negatives (in reverse order and negated) followed by non-negatives
int index = 0;
for (int i = negativesArray.Length - 1; i >= 0; i--)
{
array[index++] = -negativesArray[i];
}
for (int i = 0; i < nonNegativesArray.Length; i++)
{
array[index++] = nonNegativesArray[i];
}
}
Characteristics
- Time Complexity: O(d * (n + k)), where d is the number of digits, n is the number of elements, and k is the range of a digit (typically 10)
- Space Complexity: O(n + k)
- Stability: Stable
- Limitations: Works best for fixed-length integers or strings
When to Use
- When sorting integers with a large range but a small number of digits
- When sorting strings of fixed length
- When stability is required
Bucket Sort
Bucket Sort divides the input into a finite number of buckets, each of which is then sorted individually (typically using another sorting algorithm).
How It Works
- Create a number of empty buckets (or lists).
- Distribute the elements into the buckets based on their values.
- Sort each bucket individually (using any sorting algorithm).
- Concatenate all sorted buckets to get the final sorted array.
Implementation
public static void BucketSort(double[] array)
{
if (array.Length == 0)
return;
// Create buckets
int bucketCount = array.Length;
List<double>[] buckets = new List<double>[bucketCount];
for (int i = 0; i < bucketCount; i++)
{
buckets[i] = new List<double>();
}
// Distribute elements into buckets
for (int i = 0; i < array.Length; i++)
{
int bucketIndex = (int)(array[i] * bucketCount);
// Handle edge case where array[i] = 1.0
if (bucketIndex == bucketCount)
bucketIndex--;
buckets[bucketIndex].Add(array[i]);
}
// Sort each bucket and place back into the array
int currentIndex = 0;
for (int i = 0; i < bucketCount; i++)
{
// Sort the bucket (using any sorting algorithm)
buckets[i].Sort();
// Place sorted elements back into the array
foreach (double value in buckets[i])
{
array[currentIndex++] = value;
}
}
}
Integer Bucket Sort
For integers, the distribution function needs to be adjusted:
public static void BucketSortIntegers(int[] array, int minValue, int maxValue)
{
if (array.Length == 0)
return;
// Determine the number of buckets
int bucketCount = Math.Min(array.Length, maxValue - minValue + 1);
List<int>[] buckets = new List<int>[bucketCount];
for (int i = 0; i < bucketCount; i++)
{
buckets[i] = new List<int>();
}
// Calculate the range of values per bucket
double range = (double)(maxValue - minValue + 1) / bucketCount;
// Distribute elements into buckets
for (int i = 0; i < array.Length; i++)
{
int bucketIndex = (int)((array[i] - minValue) / range);
// Handle edge case
if (bucketIndex == bucketCount)
bucketIndex--;
buckets[bucketIndex].Add(array[i]);
}
// Sort each bucket and place back into the array
int currentIndex = 0;
for (int i = 0; i < bucketCount; i++)
{
// Sort the bucket
buckets[i].Sort();
// Place sorted elements back into the array
foreach (int value in buckets[i])
{
array[currentIndex++] = value;
}
}
}
Characteristics
- Time Complexity:
- Average Case: O(n + k), where n is the number of elements and k is the number of buckets
- Worst Case: O(n²) when all elements are placed in a single bucket
- Space Complexity: O(n + k)
- Stability: Depends on the algorithm used to sort individual buckets
- Limitations: Efficiency depends on the distribution of input data and the number of buckets
When to Use
- When input is uniformly distributed over a range
- When sorting floating-point numbers between 0 and 1
- When the distribution of values is known and can be exploited
Comparison of Non-Comparison Based Sorting Algorithms
| Algorithm | Best Case | Average Case | Worst Case | Space | Stable | In-Place |
|---|---|---|---|---|---|---|
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Can be | No |
| Radix Sort | O(d * (n + k)) | O(d * (n + k)) | O(d * (n + k)) | O(n + k) | Yes | No |
| Bucket Sort | O(n + k) | O(n + k) | O(n²) | O(n + k) | Depends | No |
Where:
- n is the number of elements
- k is the range of input or number of buckets
- d is the number of digits
Performance Characteristics
- Counting Sort: Extremely efficient for small ranges of integers, but memory usage grows with the range.
- Radix Sort: Handles larger ranges efficiently by processing digits, but requires multiple passes.
- Bucket Sort: Performance heavily depends on the distribution of input data and the number of buckets.
Practical Considerations
Implementation in C#
When implementing non-comparison based sorting algorithms in C#, consider:
- Memory Usage: These algorithms typically require additional space proportional to the input size or range.
- Data Type Limitations: They're primarily designed for integers or data that can be mapped to integers.
- Range Considerations: The efficiency often depends on the range of input values.
Generic Implementation
While these algorithms are typically used for integers, they can be adapted for other types with appropriate mapping functions:
public static void CountingSortGeneric<T>(T[] array, Func<T, int> keySelector, int minKey, int maxKey)
{
int range = maxKey - minKey + 1;
int[] count = new int[range];
T[] output = new T[array.Length];
// Count occurrences of each key
for (int i = 0; i < array.Length; i++)
{
count[keySelector(array[i]) - minKey]++;
}
// Modify count array to store position information
for (int i = 1; i < range; i++)
{
count[i] += count[i - 1];
}
// Build the output array
for (int i = array.Length - 1; i >= 0; i--)
{
int key = keySelector(array[i]) - minKey;
output[count[key] - 1] = array[i];
count[key]--;
}
// Copy the output array back to the original array
Array.Copy(output, array, array.Length);
}
Usage example:
// Sort an array of custom objects by an integer property
CountingSortGeneric(employees, e => e.Age, 18, 65);
Built-in Sorting in .NET
.NET's built-in sorting methods use comparison-based algorithms, not the non-comparison based ones discussed here. However, for specific scenarios, implementing these algorithms can provide performance benefits.
Real-World Applications
Counting Sort
- Sorting students by grade (limited range of possible grades)
- Sorting products by price category (limited number of price ranges)
- Sorting ages in a demographic dataset
Radix Sort
- Sorting large integers like phone numbers or IDs
- Sorting fixed-length strings like ZIP codes or ISBN numbers
- Sorting IP addresses
Bucket Sort
- Sorting floating-point values in a known range
- Sorting data with a known distribution
- Preliminary sorting for data visualization
Conclusion
Non-comparison based sorting algorithms offer superior time complexity for specific types of data, particularly integers within a limited range. While they come with limitations regarding data types and memory usage, they can significantly outperform comparison-based algorithms in their specialized domains.
Understanding when to use these algorithms is key to optimizing performance in specific scenarios. For general-purpose sorting, comparison-based algorithms like Quick Sort remain the standard choice, but for specialized applications with appropriate data characteristics, non-comparison based algorithms can provide substantial performance benefits.
Comprehensive Example: Non-Comparison Sorting Algorithms in Practice
The following example demonstrates a practical implementation of non-comparison sorting algorithms with detailed instrumentation and visualization capabilities. This implementation is designed to be educational, showing how these algorithms work step by step and providing insights into their performance characteristics.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
namespace NonComparisonSortingAlgorithms
{
/// <summary>
/// Provides implementations and analysis tools for non-comparison sorting algorithms.
/// </summary>
public class NonComparisonSortingDemo
{
// Performance counters
private static long _operations;
private static long _memoryUsed;
// Visualization settings
private static bool _visualize;
private static StringBuilder _visualizationLog;
/// <summary>
/// Main entry point for the non-comparison sorting algorithms demonstration.
/// </summary>
public static void Main()
{
Console.WriteLine("Non-Comparison Sorting Algorithms Demonstration");
Console.WriteLine("==============================================\n");
// Demonstrate algorithm behavior with a small array
int[] smallArray = { 5, 3, 8, 4, 2, 9, 1, 7, 6 };
Console.WriteLine("Original Array: " + string.Join(", ", smallArray));
Console.WriteLine();
// Demonstrate Counting Sort
DemonstrateCountingSort(smallArray);
// Demonstrate Radix Sort
DemonstrateRadixSort(smallArray);
// Demonstrate Bucket Sort
DemonstrateBucketSort(smallArray);
// Compare with comparison-based sorting
CompareWithComparisonSorting();
// Demonstrate specialized scenarios
DemonstrateSpecializedScenarios();
}
#region Algorithm Demonstrations
/// <summary>
/// Demonstrates the Counting Sort algorithm with visualization.
/// </summary>
/// <param name="originalArray">The array to sort.</param>
private static void DemonstrateCountingSort(int[] originalArray)
{
Console.WriteLine("COUNTING SORT DEMONSTRATION");
Console.WriteLine("--------------------------");
// Create a copy of the original array
int[] array = (int[])originalArray.Clone();
// Enable visualization
_visualize = true;
_visualizationLog = new StringBuilder();
_operations = 0;
_memoryUsed = 0;
// Sort with visualization
CountingSort(array);
// Display results
Console.WriteLine("Visualization:");
Console.WriteLine(_visualizationLog.ToString());
Console.WriteLine($"Operations: {_operations}");
Console.WriteLine($"Memory Used: {_memoryUsed} bytes");
Console.WriteLine($"Sorted Array: {string.Join(", ", array)}");
Console.WriteLine();
}
/// <summary>
/// Demonstrates the Radix Sort algorithm with visualization.
/// </summary>
/// <param name="originalArray">The array to sort.</param>
private static void DemonstrateRadixSort(int[] originalArray)
{
Console.WriteLine("RADIX SORT DEMONSTRATION");
Console.WriteLine("-----------------------");
// Create a copy of the original array
int[] array = (int[])originalArray.Clone();
// Enable visualization
_visualize = true;
_visualizationLog = new StringBuilder();
_operations = 0;
_memoryUsed = 0;
// Sort with visualization
RadixSort(array);
// Display results
Console.WriteLine("Visualization:");
Console.WriteLine(_visualizationLog.ToString());
Console.WriteLine($"Operations: {_operations}");
Console.WriteLine($"Memory Used: {_memoryUsed} bytes");
Console.WriteLine($"Sorted Array: {string.Join(", ", array)}");
Console.WriteLine();
}
/// <summary>
/// Demonstrates the Bucket Sort algorithm with visualization.
/// </summary>
/// <param name="originalArray">The array to sort.</param>
private static void DemonstrateBucketSort(int[] originalArray)
{
Console.WriteLine("BUCKET SORT DEMONSTRATION");
Console.WriteLine("------------------------");
// Create a copy of the original array and normalize to [0,1) range for bucket sort
double[] array = new double[originalArray.Length];
int max = originalArray.Max();
for (int i = 0; i < originalArray.Length; i++)
{
array[i] = (double)originalArray[i] / (max + 1);
}
// Enable visualization
_visualize = true;
_visualizationLog = new StringBuilder();
_operations = 0;
_memoryUsed = 0;
// Sort with visualization
BucketSort(array);
// Convert back to integers for display
int[] result = new int[array.Length];
for (int i = 0; i < array.Length; i++)
{
result[i] = (int)Math.Round(array[i] * (max + 1));
}
// Display results
Console.WriteLine("Visualization:");
Console.WriteLine(_visualizationLog.ToString());
Console.WriteLine($"Operations: {_operations}");
Console.WriteLine($"Memory Used: {_memoryUsed} bytes");
Console.WriteLine($"Sorted Array: {string.Join(", ", result)}");
Console.WriteLine();
}
#endregion
#region Performance Comparison
/// <summary>
/// Compares the performance of non-comparison sorting algorithms with comparison-based sorting.
/// </summary>
private static void CompareWithComparisonSorting()
{
Console.WriteLine("PERFORMANCE COMPARISON");
Console.WriteLine("---------------------");
// Test with different array sizes and ranges
int[] sizes = { 1000, 10000, 100000 };
int[] ranges = { 100, 1000, 10000 };
foreach (int size in sizes)
{
foreach (int range in ranges)
{
if (range > size) continue; // Skip if range is larger than size
Console.WriteLine($"\nArray Size: {size}, Value Range: 0-{range}");
Console.WriteLine($"{"Algorithm",-20} {"Time (ms)",-10} {"Operations",-12} {"Memory (bytes)",-15}");
Console.WriteLine(new string('-', 57));
// Generate a random array
int[] randomArray = GenerateRandomArray(size, range);
// Test Counting Sort
MeasurePerformance("Counting Sort", randomArray, CountingSort);
// Test Radix Sort
MeasurePerformance("Radix Sort", randomArray, RadixSort);
// Test Bucket Sort (convert to double)
double[] doubleArray = randomArray.Select(x => (double)x / range).ToArray();
MeasurePerformance("Bucket Sort", doubleArray, BucketSort);
// Test Quick Sort (comparison-based)
MeasurePerformance("Quick Sort", randomArray, QuickSort);
}
}
Console.WriteLine();
}
/// <summary>
/// Measures the performance of a sorting algorithm.
/// </summary>
/// <typeparam name="T">The type of elements in the array.</typeparam>
/// <param name="algorithmName">The name of the algorithm.</param>
/// <param name="originalArray">The array to sort.</param>
/// <param name="sortMethod">The sorting method to test.</param>
private static void MeasurePerformance<T>(string algorithmName, T[] originalArray, Action<T[]> sortMethod)
{
// Create a copy of the original array
T[] array = (T[])originalArray.Clone();
// Reset counters
_visualize = false;
_operations = 0;
_memoryUsed = 0;
// Measure execution time
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
sortMethod(array);
stopwatch.Stop();
double milliseconds = stopwatch.Elapsed.TotalMilliseconds;
// Display results
Console.WriteLine($"{algorithmName,-20} {milliseconds,10:F2} {_operations,12} {_memoryUsed,15}");
}
#endregion
#region Specialized Scenarios
/// <summary>
/// Demonstrates specialized scenarios where non-comparison sorting algorithms excel.
/// </summary>
private static void DemonstrateSpecializedScenarios()
{
Console.WriteLine("SPECIALIZED SCENARIOS");
Console.WriteLine("--------------------");
// Scenario 1: Sorting a large array with small range of values
Console.WriteLine("\nScenario 1: Large Array with Small Range (100,000 elements, range 0-99)");
int[] largeArraySmallRange = GenerateRandomArray(100000, 100);
Console.WriteLine($"{"Algorithm",-20} {"Time (ms)",-10} {"Operations",-12} {"Memory (bytes)",-15}");
Console.WriteLine(new string('-', 57));
MeasurePerformance("Counting Sort", largeArraySmallRange, CountingSort);
MeasurePerformance("Quick Sort", largeArraySmallRange, QuickSort);
// Scenario 2: Sorting strings by length
Console.WriteLine("\nScenario 2: Sorting Strings by Length");
string[] words = {
"apple", "banana", "cherry", "date", "elderberry", "fig", "grape",
"honeydew", "kiwi", "lemon", "mango", "nectarine", "orange", "papaya"
};
Console.WriteLine("Original array: " + string.Join(", ", words));
// Sort strings by length using counting sort
int[] lengths = words.Select(w => w.Length).ToArray();
int[] sortedIndices = new int[lengths.Length];
for (int i = 0; i < sortedIndices.Length; i++) sortedIndices[i] = i;
// Use counting sort on the lengths
CountingSortIndices(lengths, sortedIndices);
// Reorder the words array
string[] sortedWords = new string[words.Length];
for (int i = 0; i < words.Length; i++)
{
sortedWords[i] = words[sortedIndices[i]];
}
Console.WriteLine("Sorted by length: " + string.Join(", ", sortedWords));
// Scenario 3: Sorting objects by integer key
Console.WriteLine("\nScenario 3: Sorting Objects by Integer Key");
// Create sample student objects
var students = new[]
{
new { Id = 5, Name = "Alice" },
new { Id = 2, Name = "Bob" },
new { Id = 8, Name = "Charlie" },
new { Id = 1, Name = "David" },
new { Id = 4, Name = "Eve" },
new { Id = 3, Name = "Frank" },
new { Id = 7, Name = "Grace" },
new { Id = 6, Name = "Hannah" }
};
Console.WriteLine("Original students: " + string.Join(", ", students.Select(s => $"{s.Name} (ID: {s.Id})")));
// Extract keys
int[] keys = students.Select(s => s.Id).ToArray();
int[] indices = new int[keys.Length];
for (int i = 0; i < indices.Length; i++) indices[i] = i;
// Sort indices by keys
CountingSortIndices(keys, indices);
// Reorder the students array
var sortedStudents = new object[students.Length];
for (int i = 0; i < students.Length; i++)
{
sortedStudents[i] = students[indices[i]];
}
Console.WriteLine("Sorted by ID: " + string.Join(", ", sortedStudents.Select(s => $"{((dynamic)s).Name} (ID: {((dynamic)s).Id})")));
Console.WriteLine();
}
#endregion
#region Array Generation Methods
/// <summary>
/// Generates a random array of integers within a specified range.
/// </summary>
/// <param name="size">The size of the array.</param>
/// <param name="range">The maximum value (exclusive).</param>
/// <returns>A random array of integers.</returns>
private static int[] GenerateRandomArray(int size, int range)
{
Random random = new Random(42); // Fixed seed for reproducibility
int[] array = new int[size];
for (int i = 0; i < size; i++)
{
array[i] = random.Next(range);
}
return array;
}
#endregion
#region Sorting Algorithm Implementations
/// <summary>
/// Implements the Counting Sort algorithm.
/// Counting Sort is an integer sorting algorithm that works by counting the number
/// of occurrences of each element and using that information to determine their positions.
/// </summary>
/// <param name="array">The array to sort.</param>
public static void CountingSort(int[] array)
{
if (array.Length <= 1) return;
// Find the minimum and maximum values
int min = array[0];
int max = array[0];
for (int i = 1; i < array.Length; i++)
{
_operations++;
if (array[i] < min)
min = array[i];
else if (array[i] > max)
max = array[i];
}
// Create a counting array
int range = max - min + 1;
int[] count = new int[range];
_memoryUsed += range * sizeof(int);
if (_visualize)
{
_visualizationLog.AppendLine($"Range: {min} to {max} (size: {range})");
_visualizationLog.AppendLine($"Creating count array of size {range}");
}
// Count occurrences of each element
for (int i = 0; i < array.Length; i++)
{
count[array[i] - min]++;
_operations++;
}
if (_visualize)
{
_visualizationLog.AppendLine($"Count array: [{string.Join(", ", count)}]");
_visualizationLog.AppendLine($"This means:");
for (int i = 0; i < range; i++)
{
if (count[i] > 0)
{
_visualizationLog.AppendLine($" Value {i + min} appears {count[i]} times");
}
}
}
// Modify count array to store position information
for (int i = 1; i < range; i++)
{
count[i] += count[i - 1];
_operations++;
}
if (_visualize)
{
_visualizationLog.AppendLine($"Cumulative count array: [{string.Join(", ", count)}]");
_visualizationLog.AppendLine($"This means:");
for (int i = 0; i < range; i++)
{
if (i == 0 || count[i] != count[i - 1])
{
_visualizationLog.AppendLine($" Values <= {i + min} end at position {count[i] - 1}");
}
}
}
// Build the output array
int[] output = new int[array.Length];
_memoryUsed += array.Length * sizeof(int);
for (int i = array.Length - 1; i >= 0; i--)
{
output[count[array[i] - min] - 1] = array[i];
count[array[i] - min]--;
_operations += 2;
if (_visualize)
{
_visualizationLog.AppendLine($"Place {array[i]} at position {count[array[i] - min]}");
_visualizationLog.AppendLine($"Output array: [{string.Join(", ", output)}]");
}
}
// Copy the output array back to the original array
Array.Copy(output, array, array.Length);
_operations += array.Length;
if (_visualize)
{
_visualizationLog.AppendLine($"Final sorted array: [{string.Join(", ", array)}]");
}
}
/// <summary>
/// Implements Counting Sort for indices based on keys.
/// </summary>
/// <param name="keys">The keys to sort by.</param>
/// <param name="indices">The indices to reorder.</param>
public static void CountingSortIndices(int[] keys, int[] indices)
{
if (keys.Length <= 1) return;
// Find the minimum and maximum values
int min = keys[0];
int max = keys[0];
for (int i = 1; i < keys.Length; i++)
{
if (keys[i] < min)
min = keys[i];
else if (keys[i] > max)
max = keys[i];
}
// Create a counting array
int range = max - min + 1;
int[] count = new int[range];
// Count occurrences of each key
for (int i = 0; i < keys.Length; i++)
{
count[keys[i] - min]++;
}
// Modify count array to store position information
for (int i = 1; i < range; i++)
{
count[i] += count[i - 1];
}
// Build the output arrays
int[] outputIndices = new int[indices.Length];
for (int i = keys.Length - 1; i >= 0; i--)
{
outputIndices[count[keys[i] - min] - 1] = indices[i];
count[keys[i] - min]--;
}
// Copy the output arrays back to the original arrays
Array.Copy(outputIndices, indices, indices.Length);
}
/// <summary>
/// Implements the Radix Sort algorithm.
/// Radix Sort is an integer sorting algorithm that sorts integers by processing individual digits.
/// </summary>
/// <param name="array">The array to sort.</param>
public static void RadixSort(int[] array)
{
if (array.Length <= 1) return;
// Find the maximum number to determine the number of digits
int max = array[0];
for (int i = 1; i < array.Length; i++)
{
_operations++;
if (array[i] > max)
max = array[i];
}
if (_visualize)
{
_visualizationLog.AppendLine($"Maximum value: {max}");
}
// Do counting sort for every digit
for (int exp = 1; max / exp > 0; exp *= 10)
{
if (_visualize)
{
_visualizationLog.AppendLine($"\nSorting by digit at position {exp} (ones, tens, etc.)");
}
CountingSortByDigit(array, exp);
}
}
/// <summary>
/// Performs Counting Sort on a specific digit of the numbers.
/// </summary>
/// <param name="array">The array to sort.</param>
/// <param name="exp">The current digit position (1, 10, 100, etc.).</param>
private static void CountingSortByDigit(int[] array, int exp)
{
int[] output = new int[array.Length];
_memoryUsed += array.Length * sizeof(int);
int[] count = new int[10]; // 0-9 digits
_memoryUsed += 10 * sizeof(int);
// Count occurrences of each digit
for (int i = 0; i < array.Length; i++)
{
int digit = (array[i] / exp) % 10;
count[digit]++;
_operations++;
if (_visualize)
{
_visualizationLog.AppendLine($"Number {array[i]} has digit {digit} at position {exp}");
}
}
if (_visualize)
{
_visualizationLog.AppendLine($"Count array: [{string.Join(", ", count)}]");
}
// Change count[i] so that it contains the position of this digit in output
for (int i = 1; i < 10; i++)
{
count[i] += count[i - 1];
_operations++;
}
if (_visualize)
{
_visualizationLog.AppendLine($"Cumulative count array: [{string.Join(", ", count)}]");
}
// Build the output array
for (int i = array.Length - 1; i >= 0; i--)
{
int digit = (array[i] / exp) % 10;
output[count[digit] - 1] = array[i];
count[digit]--;
_operations += 2;
if (_visualize)
{
_visualizationLog.AppendLine($"Place {array[i]} at position {count[digit]} based on digit {digit}");
_visualizationLog.AppendLine($"Output array: [{string.Join(", ", output)}]");
}
}
// Copy the output array back to the original array
Array.Copy(output, array, array.Length);
_operations += array.Length;
if (_visualize)
{
_visualizationLog.AppendLine($"Array after sorting by digit at position {exp}: [{string.Join(", ", array)}]");
}
}
/// <summary>
/// Implements the Bucket Sort algorithm.
/// Bucket Sort distributes elements into a number of buckets, sorts each bucket,
/// and then concatenates the results.
/// </summary>
/// <param name="array">The array to sort (values should be in the range [0,1)).</param>
public static void BucketSort(double[] array)
{
if (array.Length <= 1) return;
// Create buckets
int bucketCount = array.Length;
List<double>[] buckets = new List<double>[bucketCount];
_memoryUsed += bucketCount * IntPtr.Size; // Size of references
for (int i = 0; i < bucketCount; i++)
{
buckets[i] = new List<double>();
_memoryUsed += 16; // Approximate size of empty List<T>
}
if (_visualize)
{
_visualizationLog.AppendLine($"Created {bucketCount} buckets");
}
// Distribute elements into buckets
for (int i = 0; i < array.Length; i++)
{
int bucketIndex = (int)(array[i] * bucketCount);
// Handle edge case where array[i] = 1.0
if (bucketIndex == bucketCount)
bucketIndex--;
buckets[bucketIndex].Add(array[i]);
_operations++;
_memoryUsed += sizeof(double);
if (_visualize)
{
_visualizationLog.AppendLine($"Place {array[i]} in bucket {bucketIndex}");
}
}
if (_visualize)
{
for (int i = 0; i < bucketCount; i++)
{
if (buckets[i].Count > 0)
{
_visualizationLog.AppendLine($"Bucket {i}: [{string.Join(", ", buckets[i])}]");
}
}
}
// Sort each bucket and place back into the array
int currentIndex = 0;
for (int i = 0; i < bucketCount; i++)
{
if (buckets[i].Count > 0)
{
if (_visualize)
{
_visualizationLog.AppendLine($"Sorting bucket {i}");
}
// Sort the bucket (using insertion sort for small buckets)
buckets[i].Sort();
_operations += buckets[i].Count * Math.Log(buckets[i].Count);
// Place sorted elements back into the array
foreach (double value in buckets[i])
{
array[currentIndex++] = value;
_operations++;
if (_visualize)
{
_visualizationLog.AppendLine($"Place {value} at position {currentIndex - 1} in the output array");
}
}
}
}
if (_visualize)
{
_visualizationLog.AppendLine($"Final sorted array: [{string.Join(", ", array)}]");
}
}
/// <summary>
/// Implements the Quick Sort algorithm for comparison.
/// </summary>
/// <param name="array">The array to sort.</param>
public static void QuickSort(int[] array)
{
QuickSort(array, 0, array.Length - 1);
}
/// <summary>
/// Recursive helper method for Quick Sort.
/// </summary>
/// <param name="array">The array to sort.</param>
/// <param name="low">The starting index.</param>
/// <param name="high">The ending index.</param>
private static void QuickSort(int[] array, int low, int high)
{
if (low < high)
{
// Partition the array and get the pivot index
int pivotIndex = Partition(array, low, high);
// Sort the elements before and after the pivot
QuickSort(array, low, pivotIndex - 1);
QuickSort(array, pivotIndex + 1, high);
}
}
/// <summary>
/// Partitions the array for Quick Sort.
/// </summary>
/// <param name="array">The array to partition.</param>
/// <param name="low">The starting index.</param>
/// <param name="high">The ending index.</param>
/// <returns>The pivot index.</returns>
private static int Partition(int[] array, int low, int high)
{
// Choose the rightmost element as the pivot
int pivot = array[high];
// Index of the smaller element
int i = low - 1;
for (int j = low; j < high; j++)
{
_operations++;
// If the current element is smaller than or equal to the pivot
if (array[j] <= pivot)
{
i++;
// Swap array[i] and array[j]
int temp = array[i];
array[i] = array[j];
array[j] = temp;
_operations += 3;
}
}
// Swap array[i+1] and array[high] (put the pivot in its correct position)
int temp2 = array[i + 1];
array[i + 1] = array[high];
array[high] = temp2;
_operations += 3;
return i + 1; // Return the pivot index
}
#endregion
}
}
Step-by-Step Explanation
This comprehensive example demonstrates the implementation and analysis of non-comparison sorting algorithms in C#. Let's break it down:
-
Program Structure:
- The program is organized into a class called
NonComparisonSortingDemowith aMainmethod as the entry point. - It includes implementations of three non-comparison sorting algorithms: Counting Sort, Radix Sort, and Bucket Sort.
- It also implements Quick Sort for comparison purposes.
- The code is structured into logical regions for clarity: algorithm demonstrations, performance comparison, specialized scenarios, array generation, and algorithm implementations.
- The program is organized into a class called
-
Algorithm Visualization:
- Each sorting algorithm includes detailed visualization capabilities that show the step-by-step process.
- For Counting Sort, it shows the counting of occurrences, cumulative count calculation, and element placement.
- For Radix Sort, it shows the sorting by each digit position.
- For Bucket Sort, it shows the distribution of elements into buckets and the sorting of each bucket.
-
Performance Measurement:
- The program measures and compares the performance of each algorithm using several metrics:
- Execution time in milliseconds
- Number of operations performed
- Memory usage in bytes
- These metrics help in understanding the efficiency of each algorithm.
- The program measures and compares the performance of each algorithm using several metrics:
-
Specialized Scenarios:
- The program demonstrates scenarios where non-comparison sorting algorithms excel:
- Sorting a large array with a small range of values
- Sorting strings by length
- Sorting objects by integer key
- These scenarios highlight the practical applications of non-comparison sorting.
- The program demonstrates scenarios where non-comparison sorting algorithms excel:
Key Concepts Demonstrated
-
Counting Sort:
- Integer sorting algorithm that works by counting the occurrences of each element.
- Time Complexity: O(n + k), where n is the number of elements and k is the range of input.
- Space Complexity: O(n + k).
- Advantages: Linear time complexity, stable.
- Disadvantages: Limited to integers or data that can be mapped to integers, requires extra space.
- The example shows how Counting Sort efficiently handles arrays with a small range of values.
-
Radix Sort:
- Integer sorting algorithm that sorts numbers digit by digit.
- Time Complexity: O(d * (n + k)), where d is the number of digits, n is the number of elements, and k is the range of a digit (typically 10).
- Space Complexity: O(n + k).
- Advantages: Can handle larger ranges than Counting Sort, stable.
- Disadvantages: Limited to integers or data with fixed-length keys.
- The example shows how Radix Sort processes each digit position separately.
-
Bucket Sort:
- Distributes elements into a number of buckets, sorts each bucket, and concatenates the results.
- Time Complexity: O(n + k) average case, O(n²) worst case.
- Space Complexity: O(n + k).
- Advantages: Good for uniformly distributed data.
- Disadvantages: Performance depends on the distribution of input data.
- The example shows how Bucket Sort distributes elements into buckets based on their values.
-
Comparison with Quick Sort:
- The program compares the performance of non-comparison sorting algorithms with Quick Sort.
- It demonstrates how non-comparison sorting algorithms can outperform comparison-based sorting for specific types of data.
- The comparison highlights the trade-offs between different sorting approaches.
Performance Analysis
The example demonstrates several important performance characteristics:
-
Range Sensitivity:
- Counting Sort and Radix Sort are sensitive to the range of input values.
- When the range is small compared to the number of elements, these algorithms can be very efficient.
- When the range is large, they may require excessive memory and become less efficient.
-
Memory Usage:
- Non-comparison sorting algorithms typically require additional memory proportional to the input size or range.
- The example tracks memory usage to highlight this trade-off.
-
Operation Count:
- The example counts operations to provide a more detailed performance analysis.
- This helps in understanding the actual work performed by each algorithm.
-
Specialized Applications:
- The example demonstrates how non-comparison sorting can be applied to specialized scenarios:
- Sorting by length or other integer attributes
- Sorting objects by integer keys
- These applications highlight the versatility of non-comparison sorting.
- The example demonstrates how non-comparison sorting can be applied to specialized scenarios:
When to Use Each Algorithm
-
Counting Sort:
- When sorting integers with a limited range.
- When the range of input values is not significantly larger than the number of elements.
- When stability is required.
- Example: Sorting ages, grades, or other small-range integer data.
-
Radix Sort:
- When sorting integers with a large range but a small number of digits.
- When sorting strings of fixed length.
- When stability is required.
- Example: Sorting phone numbers, ZIP codes, or dates.
-
Bucket Sort:
- When input is uniformly distributed over a range.
- When sorting floating-point numbers between 0 and 1.
- When the distribution of values is known and can be exploited.
- Example: Sorting test scores or normalized values.