How can i determine bucket sort of array speed limit and counting sort of array speed limit? I need to find out what's certain speed for certain numbers.

A

Answer 1

[Balavignesh]

Hi Marina,

It is my understanding that you would like to determine the speed limit of sorting algorithms like Bucket Sort and Counting Sort for arrays of different sizes in MATLAB. This can be done using tic and toc functions to measure the elapsed time.

This is the speed test of bucket sort.

bucket_sort_speed_test();

Bucket Sort Execution Times:
Array Size: 100, Time: 0.001920 seconds
Array Size: 1000, Time: 0.001119 seconds
Array Size: 5000, Time: 0.001431 seconds
Array Size: 10000, Time: 0.002588 seconds
Array Size: 50000, Time: 0.012550 seconds
Array Size: 100000, Time: 0.025511 seconds

function bucket_sort_speed_test()
    % Define array sizes to test
    array_sizes = [100, 1000, 5000, 10000, 50000, 100000];
    num_tests = length(array_sizes);
    bucket_sort_times = zeros(1, num_tests);
    
    for i = 1:num_tests
        % Generate random array of given size
        array = randi(100, 1, array_sizes(i));
        
        % Measure the execution time of Bucket Sort
        tic;
        sorted_array = bucket_sort(array);
        bucket_sort_times(i) = toc;
    end
    
    % Display the results
    disp('Bucket Sort Execution Times:');
    for i = 1:num_tests
        fprintf('Array Size: %d, Time: %.6f seconds\n', array_sizes(i), bucket_sort_times(i));
    end
end

function sorted_array = bucket_sort(array)
    % Find maximum value in the array
    max_value = max(array);
    
    % Initialize buckets
    num_buckets = max_value + 1;
    buckets = cell(1, num_buckets);
    
    % Distribute elements into buckets
    for i = 1:length(array)
        index = array(i) + 1; % MATLAB indexing starts at 1
        buckets{index} = [buckets{index}, array(i)];
    end
    
    % Concatenate buckets
    sorted_array = [];
    for i = 1:num_buckets
        if ~isempty(buckets{i})
            sorted_array = [sorted_array, buckets{i}];
        end
    end
end

Speed test of counting sort:

counting_sort_speed_test();

Counting Sort Execution Times:
Array Size: 100, Time: 0.001372 seconds
Array Size: 1000, Time: 0.000718 seconds
Array Size: 5000, Time: 0.000286 seconds
Array Size: 10000, Time: 0.000374 seconds
Array Size: 50000, Time: 0.001927 seconds
Array Size: 100000, Time: 0.002342 seconds

function counting_sort_speed_test()
    % Define array sizes to test
    array_sizes = [100, 1000, 5000, 10000, 50000, 100000];
    num_tests = length(array_sizes);
    counting_sort_times = zeros(1, num_tests);
    
    for i = 1:num_tests
        % Generate random array of given size
        array = randi(100, 1, array_sizes(i));
        
        % Measure the execution time of Counting Sort
        tic;
        sorted_array = counting_sort(array);
        counting_sort_times(i) = toc;
    end
    
    % Display the results
    disp('Counting Sort Execution Times:');
    for i = 1:num_tests
        fprintf('Array Size: %d, Time: %.6f seconds\n', array_sizes(i), counting_sort_times(i));
    end
end

function sorted_array = counting_sort(array)
    % Find maximum value in the array
    max_value = max(array);
    
    % Initialize count array
    count = zeros(1, max_value + 1);
    
    % Count occurrences of each element
    for i = 1:length(array)
        count(array(i) + 1) = count(array(i) + 1) + 1;
    end
    
    % Build sorted array
    sorted_array = [];
    for i = 1:max_value + 1
        if count(i) > 0
            sorted_array = [sorted_array, repmat(i - 1, 1, count(i))];
        end
    end
end