Type 1:
The first type that you describe is not actually sorted in the form of a bucket. It actually counts the count of sort or key index. Although he was considering the option of sorting the bucket. The reason is because you are actually just counting the occurrences of each key, rather than storing the keys themselves in buckets.
Link: http://en.wikipedia.org/wiki/Counting_sort
Link: http://www.cs.princeton.edu/courses/archive/spr13/cos226/demo/51DemoKeyIndexedCounting.pdf
Space: O (1)
we can customize buckets for every possible item,
Isn't that contrary? Are you going to declare buckets for every possible element and still hold O (1) ?;)
If you want the algorithm to be stable, you also cannot overwrite the input array. Therefore, in practice, you need the space n + k for:
- An output array of length 'n' (the same size as your input array)
- 'k' buckets
If you check the pseudocode to count the sort, you will notice that the last loop goes through the input array again to see where each element should go. By doing this in the order that they appear in the input array, you get a stable look.
PS: Keep in mind that you don't necessarily sort integers. If the input is an array of characters between AZ, you can also use this algorithm.
Type 2:
Thus, the fastest way to sort would be to select 151 linked lists (let's call them buckets) and put the data structure of each person in a bucket depending on his age:
This may be the easiest way, because you can find the bucket you need quite simply, but it is not necessarily the fastest way;). Another possibility, for example, is to create baskets every 10 years.
00 - 09
10 - 19
20 - 29
...
And when you want to insert something into a bucket, you can do:
- Binary search in the bucket (e.g. LinkedList) to find the desired position.
- Insert item
Thus, you also do not need to sort the buckets after that, because everything is already sorted. Not to say that this is a good idea, just pointing to this opportunity .;)
Questions:
1) Simply put; This is linear sorting because if sorting requires linear time. Both type 1 and type 2 accept O (n + k). Since ladle sorting does not use comparisons between elements like quicksort, bubblesort, ... is not tied to O (n log n). Keep in mind that O-notation does not give any guarantee of speed; it gives a guarantee of growth rate. If your input size doubles from "N" to "2N", your linear time algorithm will do better with it than, for example, an O (n ^ 2) algorithm similar to sorting bubbles .;)
2) Insertion sorting is really effective for small arrays and basically the reason it is selected. + the fact that it is stable. Because if you do not use a stable algorithm to sort the buckets themselves, the whole algorithm (sorting the bucket) will not be stable.
3) It's hard to say. It depends on the data, in my opinion. If you need to sort 1 million 32-bit integers, you are not going to create 2 ^ 32 buckets for them. In this case, it would be nice to look at other algorithms (for example, sorting LSD Radix), which would basically generate 9 codes (1 for each digit).