What sorting algorithm is this?

The algorithm iterates over the collection once, storing the highest value and the lowest value. Then it makes an array with a size that is the range from the lowest number to the highest. The last step is to iterate over the array again and assign each value to it's index.

It only executes twice to sort any array but it scales nightmarishly with large ranges (it would make an array of length 1 million to sort the values 1 and 1 million), and it doesn't handle duplicates. It won't crash if there are duplicates, it'll just only store 1.

I came up with this in high school for a project where we sorted a small collection of numbers that were between 1 and 1000, so it worked there. Is this an actual sorting algorithm that exists? It's no bogosort but it's still awful and some friends at college got a good laugh out of it.

 

You haven't actually described a sort algorithm, just the generation of an array with too many indexes.

 

The idea is you make an array that covers the range of the numbers so when you assign the value its index then everything is sorted. Then you trim off every index that wasn't assigned a number and you'll have your array of values in order.

given the number 5, 7, 1, 3, 4 in that order, the algorithm will make an array that has indices array[1], array[2], array[3], array[4], array[5], array[6], array[7] with initial values of something outside of the range, like 0 or -1. Then iterate over the newly created array and if your original collection has that number, assign the array index you're on to that number. I think I was using a list so it seemed like less code since there was a .contains function, but that probably performs like a nested for loop now that I think about it.

Anyway, after it ran you'd have 1, 0, 3, 4, 5, 0, 7. Then count the numbers outside of the range, in this case it's 0 and there are 2 of them. I think I'm misremembering something, but the general idea is there.

 

Sounds like a slightly strange version of a "counting sort". Your complexity should be O(n + k) where n is your list length and k is your maximum value, but I think it can be made to be more space efficient than to simply allocate an arbitrarily large second array. But it's been a while since I've done much with sorting algorithms.

 

As mentioned your algorithm just describes array assignment, it assumes fully sequential int values with no duplicates or gaps, the closest match might be a hashmap rather than a sorting algorithm, while a good hashmap would handle all cases unlike your simplified algorithm.

 

You give it a collection of random numbers and you get back a collection of those numbers in order. Is that not sorting? It uses assignment to sort the numbers by assigning them to their index in an array. Then you remove the values that are out of the range of your collection.

It's not about performance or efficiency, it was just a funny memory from high school with no real application beyond a small collection of numbers that need to be sorted.

It doesn't expect the initial collection to be sequential.

 

Basically you've made an ordered associative array with a size equal to the range of values being stored. Sorting is more a side effect because you're treating the values as the keys.

 

You've just described counting sort. I thought I was the first to come up with it too when I figured it out! But alas, its a common sorting method, just memory inefficient.

 

This is kind of pointless isn't it? In order to have an array say from 0..99 and to be able to fill it with numbers whose index is the same as their value, you might as well just have a for loop which assigns a number to each array element adding 1 to it in each loop. It's completely useless for sorting anything other than a list of numbers where every number is present only once, and then it's even more useless because you already know what the results is going to be and might as well just fill the array with a loop and totally ignore the source values. Or am I missing something?

 

Why would you EVER use such a method

 

Exactly!

It's just what I thought up in high school when we were asked to sort some numbers. The teacher wanted to see if we were familiar with anything already. Maybe it was just a cruel joke on the students.

It's often hard to find the point in doing arbitrary school work You can't ignore the source values because you're supposed to be sorting a collection of numbers given to you.

If the question was, "sort a collection containing the numbers 9, 2, 1, 4, 10" then at the age you are in your 2nd year of high school you're probably not going to give an amazing answer.

 

Reading that caused me to momentarily space whilst remembering stuff from high school. I think after modifying what I started with a couple times, my teacher informed me that I had made a counting sort. I did change the index thing to count how many values were there after I realized it couldn't handle duplicates.

I wonder what I've forgotten in the process of remembering that.

 

Okay BFGames. You have to, without using an existing sort (e.g. library or internet), figure out a way to sort a shuffled deck of cards in the next 3 mins, including implementation, without flaw, as efficiently as possible.

Though you lose the ability to store complex data - e.g. references to objects rather than just the number itself. This can be addressed by using lists etc. - albeit with the associated drawbacks.

 

Ohhh. That could be an interesting case to use this on. Cards are unique and there aren't too many. Nice!

 

Are my 3 minutes up? If i know i only have to sort a deck of cards and nothing else, i can just pre-define each cards index in a sorted deck