1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE! I'm afraid this question isn't quite suitable for CS.SE in its current form. First, "What can you tell me about it?" is too open-ended; we want focused, answerable technique questions, not open-ended calls to discussion or subjective questions. See our help center. Second, code is off-topic here; please replace code with ideas, concise pseudocode, and proofs of correctness. Third, sorting is a topic that has been extremely well-studied. What research have you done? Have you studied other sorting algorithms? (continued) $\endgroup$ – D.W. Mar 11 '16 at 8:38
  • 1
    $\begingroup$ Have you read other questions here in the sorting tag? Have you read Wikipedia and Knuth on sorting? We expect you to do a significant amount of research before asking, and to show us in the question what research you've done. This helps you frame a more focused question, helps us give you better answers, and helps others who may have a similar problem and may happen upon your question. See cs.stackexchange.com/help/how-to-ask. Can you think of any way to edit the question to improve it and address this feedback? $\endgroup$ – D.W. Mar 11 '16 at 8:39
  • $\begingroup$ Sorry but anyone who isn't fluent in C++ who sees things like std::vector<std::vector<int>> presorted(range+1); and sorted.push_back(foo); has no idea what's going on. $\endgroup$ – David Richerby Mar 11 '16 at 9:15
  • $\begingroup$ Describe your algorithm, have your source code include comments (doxygen?). $\endgroup$ – greybeard Mar 11 '16 at 9:49
  • $\begingroup$ Thank you! and sorry for the low quality post. I have tried to improve it (added a description of the algorithm as well as an example of how would it work). $\endgroup$ – Reethok Mar 11 '16 at 10:14
5
$\begingroup$

What you have come up with is a sligthly less memory efficient version of counting sort.

This algorithm works in $\mathcal{O}(n + range)$ time where $n$ is the number of elements in the vector $unsorted$ and $max$ and $min$ are as defined in your program.

Your implementation uses $\mathcal{O}(n + range)$ memory. You can make it more memory efficient by just keeping track of how many times the same number in the vector 'unsorted' occurs rather than maintaining a vector with repeated instances of the same element i.e.

vector<int> presorted(range+1);
for(int i = 0; i < unsorted.size(); i++)
     presorted[unsorted[i] - min]++

It will now use only $\mathcal{O}(range)$ memory.

Yes you are correct, this method might potentially use up a lot of memory if the difference between the smallest and largest elements of the vector is too great.

For those who are not fluent in C++:

  1. OP is finding the smallest and largest elements of the unsorted array $max$ and $min$ respectively.
  2. He is initializing an array of size $max - min$ and creating an empty linked list in each position of the array (in this code it is the vector of vector of integers $presorted$).
  3. Then each element of $unsorted$ is added as a new node in the linked list at $presorted[unsorted[i] - min]$. In a random access computational model this operation will take $\mathcal{O}(1)$ time and hence each element of $unsorted$ is added to its appropriate bucket in constant time.
  4. Then he is just iterating in the array of linked lists and compressing it to the final array $sorted$ which is the final output.
$\endgroup$
  • 1
    $\begingroup$ Thank you! I tried to google the idea of the algorithm (i googled something like value as index sorting) but couldn't find anything. $\endgroup$ – Reethok Mar 11 '16 at 10:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.