I had an idea for a sorting algorithm wich is very fast, but can (potentially) use a lot of memory. I'm not a Computer Science student/graduate, only a self-taught programmer so I don't know how to evaluate it's viability. Also, I would like to know if it has already been documented and under what name.
Algorithm:
- Get an unsorted array
- Iterate through it, and find the highest and lowest value stored in it
- Determine "range" (highest - lowest)
- Make a 2 dimensional array
presorted
,
in which the first dimension's size is "range" + 1 - For each element in array "unsorted"
- Add the current element into presorted[current_element_value - lowest]
- Make array "sorted", and add each element of
presorted
's second dimension, ignoring the empty first dimensions. - return the sorted array
An example using said algorithm would be the following:
unsorted[] = {5, 8, 2, 4, 6, 8, 2, 0, 4, 5, 6, 3, 3, 2, 1}
After iterating through it once, we get:
lowest: 0
highest: 8
range = highest - lowest = 8
Make 2 dimensional array presorted,
consisting of range+1 arrays:
presorted[0] = {}
presorted[1] = {}
presorted[2] = {}
presorted[3] = {}
presorted[4] = {}
presorted[5] = {}
presorted[6] = {}
presorted[7] = {}
presorted[8] = {}
Next we add the elements, first element of unsorted is 5.
5 - lowest (0) is 5
presorted[0] = {}
presorted[1] = {}
presorted[2] = {}
presorted[3] = {}
presorted[4] = {}
presorted[5] = {5}
presorted[6] = {}
presorted[7] = {}
presorted[8] = {}
After doing this which each element:
presorted[0] = {0}
presorted[1] = {1}
presorted[2] = {2, 2, 2}
presorted[3] = {3, 3}
presorted[4] = {4, 4}
presorted[5] = {5, 5}
presorted[6] = {6, 6}
presorted[7] = {}
presorted[8] = {8, 8}
Now, we simply create an empty array called "sorted",
to which we add all the elements
of non-empty arrays in presorted:
sorted = {0, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 8, 8}
This is the C++ source code for it
std::vector<int> Sort(std::vector<int> &unsorted)
{
int min = unsorted[0];
int max = unsorted[0];
int range;
std::vector<int> sorted;
for (int i = 0; i < unsorted.size(); i++)
{
if (unsorted[i] > max)
max = unsorted[i];
if (unsorted[i] < min)
min = unsorted[i];
}
range = max - min;
std::vector<std::vector<int>> presorted(range+1);
for (int i = 0; i < unsorted.size(); i++)
presorted[unsorted[i] - min].push_back(unsorted[i]);
for (int i = 0; i < presorted.size(); i++)
{
if (!presorted[i].empty())
{
for (int k = 0; k < presorted[i].size(); k++)
sorted.push_back(presorted[i][k]);
}
}
return sorted;
}
Is this algorithm viable?
I think it could be used in certain scenarios (when range is not too big) and it has the advantage that you can determine if it's appropriate to use it with simply iterating once through the unsorted list.
I'll do some tests and report back.
std::vector<std::vector<int>> presorted(range+1);
andsorted.push_back(foo);
has no idea what's going on. $\endgroup$