O(n) sorting algorithm

Question

Here's a very horrible sorting algorithm that only works on integers ranging from 0 to size. I wouldn't use such an algorithm on a large set of data or one with large numbers in it because it would require so much memory. That consider, wouldn't this algorithm technically run in O(n) time?

Thanks

#include <iostream>
#define size 33

int main(){

    int b[size];

    int a[size] = {1,6,32,9,3,7,4,22,5,2,1,0};

    for (int n=0; n<size; n++) b[n] = 0;

    for (int n=0; n<size; n++){
        if (size <= a[n]) throw std::logic_error("error");
        b[a[n]]++;
    }

    int x = 0;
    for (int n=0; n<size; n++){
        for (int t=0; t<b[n]; t++){
            a[x] = n;
            x++;
        }
    }

    for (int n=0; n<size; n++) printf("%d ",a[n]);
}

Pretty much yes. Read here: en.wikipedia.org/wiki/Bucket_sort — Tomasz Plaskota
– Tomasz Plaskota, Commented Sep 22, 2016 at 15:37
Why is it horrible? For the right sort of problem, it can be very efficient. — Martin Bonner supports Monica
– Martin Bonner supports Monica, Commented Sep 22, 2016 at 16:32

Angew is no longer proud of SO · Accepted Answer · 2016-09-22 15:34:52Z

2

You're showing a variation on radix sort. Along with bucket sort, these algorithms are prime examples of sorting not based on comparison, which can offer better complexity than O(n logn).

Do note, however, that your implementation is actually O(n + size).

answered Sep 22, 2016 at 15:34

Angew is no longer proud of SO

172k18 gold badges377 silver badges478 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

nishantsingh · Accepted Answer · 2016-09-22 15:34:41Z

1

It is O(n). More specifically it is O(n+k) where n is the number of elements in input array and k is the range of input in your case size. You are just keeping counts of all elements which occur in the array. And then you just store them in increasing order as many times as they occur in the original array. This algorithm is called count sort.

answered Sep 22, 2016 at 15:34

nishantsingh

4,6826 gold badges29 silver badges54 bronze badges

Collectives™ on Stack Overflow

O(n) sorting algorithm

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related