A month ago today, I posted what’s turned out to be by far the most commented-on article on this site: Are you one of the 10% of programmers who can write a binary search?. The gist of it was that Jon Bentley, in his book Programming Pearls [amazon.com, amazon.co.uk], had found in many seminars that when professional programmers are given a high-level description of the binary-search algorithm and a couple of hours to write code that implements it, only one in ten of the offered solutions are free of bugs. An amazing number of you attempted the challenge — somewhere around 500 — and the results seemed to show a correctness rate somewhere between 10% and 50%.
Now we’re going to try the same exercise with one of the simplest of sorting algorithms: selection sort. (No Wikipedia link for now, because you might see information that you don’t want to see yet.)
Please be sure to read the rest of this article before running off and programming!
What is selection sort?
It’s just about the simplest of the various algorithms for putting a list in order, which makes it a great subject for this kind of exercise. The idea is that you find the smallest element and stash it down at the bottom of the array; then the next smallest element, and stash that down in the next lowest position; and so on, until all the elements are in order.
I’ve left this description fairly informal on purpose: I don’t want to specify formal preconditions, invariants and whatnot, partly to encourage you to do that work for yourselves, and also because stating these things formally would require me to use a specific representation for the array, and different representations are appropriate in different programming languages.
Selection sort is pretty dumb: like bubble sort and insertion sort, it’s O(n^2), which makes it slow for big arrays. (If you don’t know what O(n^2) means, don’t worry, I’ll talk about that in a follow-up article.) You probably don’t want to use selection sort in real programs. But it’s nice and easy to think about, so hopefully we’ll get plenty of right-first-time solutions. (Disclosure: my own routine had two bugs. Rats. I was too impatient to run it.)
The rules
Much as for the binary search challenge:
- Use whatever programming language you like. Don’t bother making it generic for multiple types unless that’s trivial in your language — sorting a list of int is just fine. We’re interested in algorithms here, not APIs.
- Your routine can sort an existing array in place, or return a sorted copy. Either is fine.
- No pasting or otherwise copying code. Don’t even look at other sorting code until you’re done.
- I need hardly say, no calling a library sort function, or otherwise cheating! Calling a library minimum function is borderline, as it solves half the problem for you — let your conscience by your guide.
-, but …
- NO TESTING until after you’ve decided your program is correct. The reasons for this rule are explained in an earlier post, Testing is not a substitute for thinking.
- Do not get all clever and write a quicksort/heapsort/shellsort instead: the exercise is to write a selection sort.
- Finally, the most important one: if you decide to begin this exercise, then you must report — either to say that you succeeded, failed or abandoned the attempt. Otherwise the figures will be skewed towards success.
I’ll post some ideas about a test-suite in a subsequent article — I don’t have anything particularly clever in mind, but it’s best not to show you a test suite now because, again, it’s best if you figure out for yourself which cases need testing to give a good level of confidence in the code.
Oh, and if you haven’t already read the binary-search followup articles, you may find it useful to read about invariants (to persuade yourself that your code gives the right answer), bound functions (to show that it doesn’t get into an endless loop) and preconditions and postconditions (to see that the problem it solves is the right one).
How to submit your code
Post a comment on this article containing your code, and stating whether it succeeded when you first ran it. Best is to paste the code right into your comment, enclosed in a {source}…{/source} sequence, but using square brackets rather than curlies. If you’re not confident that you can do this right, then use a service like pastebin.com, pastebay.com or gist.github.com, and post the URL in a comment.
Either way, please state what language you are using.
(We had an amazing amount of trouble with this last time: many people used curly brackets around their {code}…{/code} tags rather than square brackets. Folks: USE SQUARE BRACKETS instead of curlies — the only reason I’ve not used them right here is that WordPress helpful interprets them if I do.)
For full instructions on posting source code in WordPress comments, see the WordPress support page on Code » Posting Source Code.
That’s all, folks: let’s go!
Horribly inefficient, but seems to work for random, reverse ordered, empty, arrays with duplicated values, and single element arrays.
In retrospect, I’m not sure if the problem requires an in place sort or not, so I may be cheating.
Similarly not in-place.
I love these.
Not tested, just compiled.
Hm. I used the name “raIterator” to imply that the iterator should be random-access (like in the binary sort problem), but really, this will work just fine with a sequential-access iterator.
Oh well.
OK, I had a moment so I’ll give this one a crack. Fifteen minutes start to finish. C99 because of the variable-sized array. No standard libs. No testing.
I forgot to do swap using Temp var and directly assigned smallest value to current index :-|
Time taken ~15mins
[cont. edit] so it worked in 2nd try.. after using temp.
is there any punishment ? :-S
In place is fine, and is what I had in mind; but returning a sorted equivalent array is also fine.
I’ll tweak the article to clarify that.
I could make it not destructive with a simple array copy. I chose not to do inline sorting because that would have greatly increased the chance of me making a subtle mistake. :)
Worked perfect on all types of int arrays and empty arrays on first test. Should work with anything that implements __gt__ and __lt__.
Just to use the language that everyone loves to hate (and it seems to work):
Corey Porter, I’m not sure if it isn’t cheating a bit to use a min function, as it does half of the problem for you. (Obviously doesn’t count as cheating in your case since you did it before I’d spelled that out.) I’ll tweak the rules to make that clearer.
Used C++ for this. I made a stupid typo and forgot the * in if (*k > *biggest), so it didn’t sort at all the first run through.
Tested zero, 1, all minvalue, all maxvalue, random arrays and it worked on the first try. There is the possibility of unnecessary swaps when there are duplicate values, but it is correct AFAIK.
[Code]
static void Sort(int[] array)
{
int x = 0;
while (x = array.Length) { throw new ApplicationException(); }
for (int x = start; x < array.Length; x++)
{
if (array[x] <= lowestValue) { lowestIndex = x; lowestValue = array[x]; }
}
return lowestIndex;
}
[/Code]
Whoops, got the tag wrong, second try:
[Source]
static void Sort(int[] array)
{
int x = 0;
while (x = array.Length) { throw new ApplicationException(); }
for (int x = start; x < array.Length; x++)
{
if (array[x] <= lowestValue) { lowestIndex = x; lowestValue = array[x]; }
}
return lowestIndex;
}
[/Source]
Compiled but completely untested (makes me nervous). Took about 15 minutes. It’s an iteration/recursion hybrid using Common Lisp:
In-place, horribly inefficient (scans the unsorted portion twice as often as it needs to). Failed first time round, as I missed off the ‘, i)’ – shameful.
My conscience was happy with the use of ‘min’ though, since a) I’d coded it before the rules changed, and b) the ‘trick’ is calling ‘min’ over the correct sub-sequence.
The code (Java):
Does it work? Perfectly! Do I pass? No.
See, I made one mistake. One little mistake. Those three lines where I swap values? I used the variable name “index” instead of “input”. I didn’t catch this until I pasted my code into Eclipse (I wrote it in Notepad). Once that was fixed, it worked perfectly.
But my testing harness didn’t. That took two runs. My little function to print out the arrays had two simple bugs in it, stupid bugs. The kind that are easily caught when you run the program. The kind you don’t make when you actually think about what you’re writing.
Tested with null input, one number input, sorted input, descending sorted input, and mixed input.
Failed with:
Three bugs:
1. Failed to include the starting point in the search for the smallest remaining value.
2. Forgot to test for a need to swap.
3. Used inner instead of smallest as index when swapping.
Passes with:
My test cases:
I wrote this iteratively, not recursively. It took me 5 minutes to write, and then 10-15 minutes careful hand-testing to persuade myself it was correct. I then formally tested it against an empty array, a 1 element array a 2 element array, a 3 element array and a 10-element array. I think the algorithm can be shown to be provably correct (in terms of bounds, invariants, etc) with no more than 3 elements in the array: i.e. if it is provably correct for 0..3 elements, then it is true for 0..n.
Here’s the code
I’m happy to say it passed all the tests!
Whew, yeah. A little nervous actually hitting run, and I had to do an experiment to remind myself how to work with C++ arrays.
void selection_sort(int *array, size_t size) {
size_t i, k = 0, idx;
int tmp;
for (k = 0; k < size; ++k) {
idx = k;
for (i = k+1; i < size; ++i)
if (array[i] < array[idx])
idx = i;
if (idx != k){
tmp = array[k];
array[k] = array[idx];
array[idx] = tmp;
}
}
}
Here is my try in python:
I spent on it less than 10 minutes (I didn’t measure exactly). This code is the first attempt. It seems to work fine… Hopefully I didn’t overlook something. Unfortunately it does not look very pythonic ;)
Whoops, forgot to include: it passed my quick set of tests when I ran it
David Gladfelter, have a third try, but this time make your source tags all lower-case. If you also repeat the notes from your first try, I’ll delete the first two (and this message) so only your good one remains. (I can’t fix it up for you because in the absence of correct source tags, WordPress eats sequences beginning with less-than.)
Heh I managed to fail, forgot the array indices I think.
I wrote mine in C, it sorts in place.
Straight-up naive recursion, in Scheme:
I’m waiting to see the Haskell solutions.
Wasn’t sure what the pitfalls are for this algorithm. Function worked first time. The one part that gave me pause was also commented on in earlier comments — whether better to test if swap needed (would seem to depend on whether input is well-sorted or poorly-sorted). I assumed poorly:
I could probably make it “more clever” with some work and better ruby syntax, but it seems “clever enough”. Doesn’t choke on null arrays, singleton arrays, negative values or other similar things. Note that the value swap is only safe because ruby specifically turns that syntax into something safe.
Here’s my take in ruby – passed all the tests, took around 15 minutes.
Process:
Write code and notes.
Fix syntax errors.
Describe why the code ought to be correct.
Submit here.
Test?
(Reformatting the text from the current “source code comment” is not part of this process.)
Hopefully, WordPress will format OCaml sensibly as F#… (And with luck, the big pile of texts-as-comment will look OK…)
I didn’t do the binary search one primarily because I didn’t understand or agree with your “no testing” rule. I’m joining in now, after reading the explanation and agreeing with it.
I must say, I think selection sort is significantly easier than binary search, though I don’t know why. I’m fairly certain that I’d make all the usual mistakes if I were to write a binary search, but writing selection sort would come fairly easy even without the invariant comments in my code ahead. Though they did help me organize my thoughts when I wrote the code.
Please don’t judge the comments: it’s after 1am in my timezone and I should be sleeping, not coding.
Compiled and tested, failed miserably: I reversed the test in the middle, which means all my arrays are sorted in reverse order. I won’t blame the hour for this, I could have just as easily made this mistake wide awake. It’s just, this particular bit of code (find the minimal element) is so idiomatic that I write it without thinking, and therefore get it wrong with probability 50%.
Missed out last time because I started hacking at it before I finished reading the article, so glad to give it a try now. Submission is a python function that accepts a list of ints as it’s only parameter. Also, typing solution directly into comment. If you plan on making a habit of this, you might want to look into, automated programming contest software. I seem to recall that they have some kind of system where you can define your own challenges, along with test suites, etc..
Coded in C, sorts an array in-place. Wrote it, eyeballed to convince myself it was correct, but wasn’t quite brave enough to submit without running through a few simple tests.
@Mike Taylor/Corey Porter:
That’s Haskell, and the “min” function is the kind which takes two values and returns the smaller, i.e. something like “x < y ? x : y" in C.
Using that with fold *does* make things simple, but that's just Haskell… (Though we could do something very similar with a combination of std::min and std::accumulate in C++… And, of course, the elegant solutions in Haskell won't sort in-place…)
Untested. Hope I don’t regret this:
These exercises are pretty fun, by the way.
Great. Line 42 of my solution is wrong. It needs to be:
min is returning an index that’s counted from the beginning of the chunk of the array it’s looking at, not the entire array, so the swap wasn’t given the correct index. Whoops.
Arild, its fascinating to see which programming languages hide which parts of the complexity. I can’t really justify this, but I feel that using a min() function that finds the smallest value in an array is (just) cheating, whereas a function that only chooses the lesser of two values is legitimate; and of course when the language lets you fold that along an array, you end up where you started. Bottom line seems to be that doing it in a more spelled-out-element-by-element array would just not be idiomatically correct Haskell. So I’m fine with the solution posted.
(I have GOT to learn Haskell.)
I did this in Ruby, and had a stupid error on my first try. The algorithm was right, but I was choosing the wrong array element because I used a bunch of one-character variable names and got mixed up. On second try, it worked:
Here’s an in-place JavaScript implementation. I haven’t tested it much, but it seems to work.
About 7 minutes to write, 3 typos fixed as I tried to compile it. Wrote it together with 3 dumb test vectors & it worked from the first try.
std::vector& ssort(std::vector& v)
{
typedef std::vector::iterator iter;
for (iter front = v.begin(); front != v.end(); ++front)
{
// find smalles element in the remaining part of the array
iter peek = front;
for (iter t = front + 1; t != v.end(); ++t)
if (*t < *peek)
peek = t;
// move smallest element to it's place
std::swap(*peek, *front);
}
return v;
}
Yuck. That site ate angle brackets off C++ stl vector.
Worked first time (except for syntax errors). About 6 minutes elapsed time.
I just noticed that all the solutions (including mine) iterating over elements a[0]..a[n], where n is the last element should really iterate to a[n-1]. This is because by the time a[n-1] is processed, a[n] must be in its correct place, so it does not need to be examined. Does this count as a bug, Mike?
In O’Caml. Didn’t take too long; though I struggled to figure out how to word my invariant(s). So I won’t be surprised if it fails…
(* selection sort *)
let sort arr =
let len = Array.length arr in
for i = 0 to len – 1 do
let min_pos = ref i in
for j = i+1 to len – 1 do
min_pos := if arr.(!min_pos) < arr.(j)
then !min_pos else j;
done;
let temp = arr.(i) in
arr.(i) <- arr.(!min_pos);
arr.(!min_pos) <- temp
done
Here’s a Clojure version; worked first time. Like rphan, I chose not to do the sort in place (partly) to avoid subtle errors. That’s also more in the spirit of Clojure — partly to avoid subtle errors.
Note there’s a core function ‘min’ that does the same thing as ‘selmin’. Tested with 0- to 4-length inputs, some including duplicated values.
Er, not quite true about Clojure ‘min’, which takes the minimum of its arguments, while my ‘selmin’ takes a single collection argument and returns the minimum of the collection. So (selmin coll) is equivalent to (apply min coll).
I knew you’d want to know…
Dang; boundary condition got me. In Java:
The bug is that Integer.MIN_VALUE will not be properly detected, as curVal > curMax, not >=. The fix was easy enough; I had to add an additional else if clause:
I can post my test suite, if desired. Mostly just checking 0 len, 1 len with min and max int, multiple min and max int, multiple other digits, etc.
In-place sort array of 32-bit integers, x86 assembler. Had one bug – the off by one error I mentioned in a previous post.
;————————————–
; assume: esi = *a, ecx = sizeof(a)
;————————————–
cmp ecx, 2
jl _l3
dec ecx
mov edi, esi
_l1: mov ebx, ecx
mov eax, [edi]
mov edx, edi
_l2: add esi, 4
cmp eax, [esi]
jl @F
mov eax, [esi]
mov edx, esi
@@: dec ebx
jnz _l2
cmp edx, edi
je @F
push [edi]
mov [edx], eax
pop eax
mov [edi], eax
@@: add edi, 4
mov esi, edi
dec ecx
jnz _l1
_l3:
My first language is Java, so I wrote the following code first:
But I’m also learning Haskell, so I gave that a shot as well. It’s astounding how small the Haskell code is compared to the Java, and I even wrote my own min function! The delete might be too powerful: it removes the first occurrence of an item that it can find in a list.
Both were written first and then tested. They seem to work, but I haven’t done any formal analysis to prove that!
Argh; after quickly looking at the other solutions, I realized how terrible mine was. Here’s a Java in-place solution that I got right in one try. I had skimmed over the other solutions here first, so it’s not a fair submission.
Took much longer to write the tests (which I did after finishing) than to write the function (which only took 2-3 minutes). C++.
Code includes test cases which I did not run until I was satisfied that the program was correct. It is, at least according to my test cases, which are probably far from complete. Code works, 13 LOC Python, ~5 minutes.
Took about 30 minutes and, since I am at work and so without facilities, I wrote it in Notepad and I haven’t even compiled it, so I am fully braced for failure. Anyway, here goes:
Quick Python version. No type checking as it should be able to support anything that can be made into a list using list().
Having now looked at some of the others I’ve realised that I misunderstood “stash it down at the bottom of the array” to be at the highest index rather than the lowest, so I have rewritten accordingly and also renamed “lowest” as “smallest” to avoid confusion with “lower”.
Still not compiled, so for all I know it doesn’t even run, but hey, ho, what can you do?
Count this as a fail, because I mixed up i and j in the swap the first time around, and had to try it out a few times to catch it.
I didn’t try to do exhaustive testing, just relied on random numbers for a range of array sizes. The testing could easily be harder than the algorithm itself for this kind of challenge. I was pretty confident of my code before I ran it and all tests passed, but I don’t discount the possibility that I missed an edge condition. Python source:
An in-place sort in Ruby. I favoured simplicity over efficiency, and testing was very brief.
@ Arild/Mike Taylor/Corey Porter:
Okay, I cry “uncle” at Corey’s haskell solution. Is this readable once you’re used to the Haskell syntax? and what is the run-time for Corey’s implementation? (I have Real World Haskell, but it’s a hard slog)
Here’s mine, with pre-conditions, post-conditions, and invariants specified. I was really lazy, and haven’t even tested that it compiles, but fingers crossed!
BTW, it’s in Java
Nope, didn’t compile because I forgot types in the method signature. Again, compiling
I made a really stupid error on my first try, but I basically had it right. I think this exercise was actually quite a bit easier than the binary search bit.
This is my corrected version in C#:
This is the original, erroneous part of the code (which retains the value of lowerValue and lowerIndex from the last run of the loop, and so fails):
time: about 20 min.
didn’t run it before submitting, tried it now – seems to work with empty array, 1 element array, random content, reverse sorted and all same values. any other testcases I missed?
JavaScript, failed. The bug has nothing to do with algorithm though, I got “splice” syntax wrong. No amount of thinking about border conditions and invariants could fix this. I don’t believe in these things at all, you have to think, that’s all. You have to visualize the algorithm.
Less than 10 minutes in C99. The code doesn’t handle 0 sized arrays (as my tests bore out) but it works on arrays of 1 or more elements.
Personally, I don’t consider a 0-element array as being valid, but that’s me …
Well it’s Perl again, I know and it works. The key phrase I think here is ‘stash’, in my case I swap the current first value with the lowest level value in the array and then move up the first value pointer.
Also… the first time I thought I was finished I foolishly had missed out line 12, which is kind of one of the more important ones in the whole thing. So it’s a failure due to sloppiness.
And possibly due to terrible code as well.
Perl.
I abandoned last night and tried again today, and not because the problem but my lack of knowledge with Perl arrays.
So I failed.
Sean Conner wrote:
A couple of people said this in the binary-search exercise, too. I find it utterly bewildering. Of course an empty set is a perfectly good set. It’s just as valid a set as an empty string is a valid string: how would we feel about a strlen() function that didn’t work on empty strings?
Or think about the ls command that lists files in the working directory, sorted: what would we think of such a program if it didn’t work in empty directories, due to the sort routine not working on empty arrays?
FORTRAN and C:
I was not really clear on the concept and added a few enhancements to the C version, and for a while it appeared to be O(n), but then it became slower than the FORTRAN version.
The C version was going to work but then I changed this:
if (…) continue;
to this
if (…) continue;
continue;
so it didn’t work the first time.
The FORTRAN version worked the first time, but by then I had looked at some of the other postings so it doesn’t count, then I broke it, now it’s working again.
Oh yeah, that last post () includes a test harness.
fixed a comment typo: new URL:
Brian wrote:
Brian, if you write an O(n) search routine, then go straight to the Nobel Prize committee!
:-)
@Mike: yeah, tell me about it.
No testing, just thinking. Ran perfectly first time. Then ran again with various types of arrays, empty, etc. Took about an hour. Each draft produced another problem in my mind.
Seems to be working on the first try.
Tested on empty, one element, sorted, reverse sorted and random arrays (checking against library’s qsort).
[/code]
void ss(int *array, const int size){
int current;
for(current = 0; current < size; current++){
int pos_min, i;
pos_min = current;
for(i=current+1; i<size; i++){
if(array[i] < array[pos_min]){
pos_min = i;
}
}
if(pos_min != current){
int min = array[pos_min];
array[pos_min] = array[current];
array[current] = min;
}
}
}
[/code]
Sorry about that. Second try:
Holy s***…
It looks like the blog is rejecting my comments when I use a certain email address. I’m trying another one now, so if the other post shows up eventually, please excuse the double post.
Wrote my version in Haskell and it worked perfectly the first time. No testing.
this one’s in php… on the first try, it correctly sorted this one: 4, 2, 15, -6, -50, 0, 0, 4, 2, 13, -23, -23, -23, 66, 6
Python: (essentially the same as “rphan”, but mine is bit uglier)
Worked on first try without any bugs. Seems to work on empty arrays, duplicates, random arrays.
Wrote it in a few minutes, then I carefully walked myself through the code, before I did some informal reasoning about the invariants and bounds of the two loops.
(Invariants: all values in ret_arr is always smaller than the ones in array, and min[1] is smaller than all values previously iterated over in the current run of the for-loop. “Boundness”: the while loop reduces array with each run, and the for loop iterates over array without adding anything to the list it iterates over.)
I do have to admit that I didn’t consciously consider the case of the empty array. Maybe I’m just used to writing loops that terminate on empty array in python. Not very idiomatic python though, and there’s some weirdness that i blame on lack of sleep.
(Great challenge, even though it wasn’t that hard. Keep up the good work and the interesting articles!)
Here’s the algorithm. Seems I got it right on the first try, but I must admin I spent more time on getting my invariants right than on coding out the algorithm. This one’s pretty simple, and I’m not sure the invariants helped me a lot here…
Seemed to run fine first go against an pretty simple test set.
I used C#. After spending a few minutes planning on paper, I got to it. Wrote the function, read it through a few times, then tested it. I’m happy to report that it worked first time :)
This was a very interesting exercise :)
My version is in OCaml, whic I thought would be useful. I did not do intensive testing once it compiled, even if it took me a lot of time (partly because I am an OCaml beginner).
Anyway, I know my version does not handle long list because one of my function is not tail-recursive, but as I discovered that during testing, it was too late :).
After looking at what a few other people did, I changed the line:
to
No need to test a value against itself. One optimisation so far.
Tried in Go. infinite loop because of a typo (j/i). it’s inefficient but should work for random, sorted, empty lists ..
Python – untested
I think Vince has a good point about the first loop having to only go as far as the second to last element in the array. Made that change in my code, it still passes all the tests, but now in one less iteration. That brings my optimisations up to two :)
@Vince, I don’t think that should count as a bug. The algorithm still does exactly what it’s supposed to. I’d call it an optimisation.
Well I completely failed on my first try, doh!
I hope this one is better.
In-place update seemed easiest, and so:
Worked as far as I can tell.
In Perl:
This took about 8–10 minutes to write and it seemed to run correctly on first blush, which is definitely not what I expected, since I am very much the sort of person who puts out junk as a first draft then carefully refines it into something slightly less broken.
It also seems okay according to the limited test harness I wrote after the fact (which took me another 10 minutes, yeesh):
I haven’t tried with anything but integers.
I tried to solve this using Haskell (a language I’m trying to learn, so probably not the best Haskell-ness in my code). I kind of think it should work, but I’m not sure.
selectionsort [] = []
selectionsort (a:as) = selhelper [] a as
selhelper [] min [] = min:[]
selhelper (a:as) min [] = min : selhelper [] a as
selhelper pre min (a:as)
| min <= a = selhelper (a:pre) min as
| otherwise = selhelper (min:pre) a as
[\source]
my Python naive implementation:
I failed the exercice, as I wrote
instead of
when it ran it the first time.
For the record: I spent about 15 minutes on it. I’m not familiar with invariants.
The code only was run with:
I’ve posted a few times on this blog using my real name, but I think that receiving fame or shame for your code might bias the result of the experiment, so I encourage everyone to post anonymously.
My test case consisted of 1000 runs each of arrays of sizes up to 1000 items. I used the result of the GCC standard C library qsort as a reference, and as a sort of double check for the integer comparison routine I supplied to the qsort I also checked so each item in both arrays was not smaller than the previous.
I had 1 typo, but on the second compile the code passed all tests, so I’m confident the implementation is bug free:
Java. Seemed to work.
Written in C with VCC extensions, see [link][/link].
Never ran it but the verifier says it works so it has to be correct :-)
* wrote it in emacs, without the doctests, about 10 minutes to be happy
* ran it once to check syntax… OK
* tested on paper for with zero, one, two, and three elements … fixed one bug (the inner range was too short by one, because i lazily typed out that loop with the same upper bound as the outer loop). Also made a trivial optimization (j can starts at i+1, although it works fine if it starts at i).
* wrote doctests, ran them, all passed.
5 minutes, works without bugs for empty sets, sets with duplicate entries, reversed sets, ordered sets, partly ordered sets. simple recursive algorithm:
Which reminds me. If you find a bug by testing on paper, does that count as success or failure? :)
Paul Winkler asked:
That’s success, because you found the bug by thinking about the code rather than just throwing it at the computer and seeing whether it stuck. (That’s assuming that when you did run it, it passed the tests, of course!)
Let me preface this by saying, “you bastard!” You can’t just post challenges like this, you’re ruining lives! I was supposed to be meeting friends in town. I’ll have to make up some excuse now. So I’ve mentally stepped through my code and I am very confident that it is correct. I haven’t tested it. Here’s hoping it’s correct. It took me 15 minutes. Bring on the shame! Oh, the shame!
(Before anyone says “that’s a list, not an array”, just like last time, I think the algorithm’s the same. And I don’t know Haskell arrays, I don’t think it would be representative for me to use a library I’m not familiar with in this challenge.)
Bahaha, I just tested it. Perfection! *Cackles maniacally* Now I’m going out for coffee. Ciao! Not this time, Mike! Stick to reviewing Buffy. ;-P
Didn’t work the first time because I didn’t follow the invariant I wrote. I said I x(i) has to be the min value. If not then find the min value and swap it with x(i) so that x(i) has the min value. Except the code I wrote to find the min value was incorrect. (I’m doing in-place. So I did x(j) < x(i). Instead of the correct x(j) < x(k) where k is the index to the last min value found.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <limits>
#include <ctime>
#include <cstdlib>
#include <cmath>
using namespace std;
//hackish isSorted test.
bool isSorted(int x[], size_t L)
{
for(size_t i=0; i < L-1; i++)
{
if(x[i] > x[i+1])
return false;
}
return true;
}
void printArray(int x[], size_t L)
{
cout << "{";
for(size_t i=0; i < L-1; ++i)
{
cout << x[i] << ",";
}
cout << x[L-1] << "}" << endl;
}
/**
*This function will sort an array of ints,in place, and in ascending order.
*
* I while C body not C and I
*Really informal invariant.
*
* Let i be the current index. Let j = i+1. The following invariances must ALL hold (AND relation):
* let x be the array. Let x(i) denote the value of array at i.
* I1) i <= L.
* I2) j <= L.
* I3) k < L.
* SO that (informally):
(i <= L AND j <= L AND k < L) while( i < L and j < L and k < L) outer loop, inner loop (i = L and j = L and k < L)
* Very very informal
*
* I4) x(i) must contain the minimum value of the array. If not, then find the minimum value in rest of the array and swap that with x(i), so that x(i) contain the minimum value of the array.
*/
void SelectionSort(int x[], size_t L)
{
assert(x!=0 && "Null array.");
assert(L>0 && "Array length is 0.");
for(size_t i=0; i < L; ++i)
{
size_t k = i; //k is used to remember the index for the min. value.
for(size_t j=i+1; j < L; ++j)
{
if(x[j] < x[k]) //Did we find a new min. value?
{
k = j; //remember where we found this.
}
}
if(k>i) //we found a new min. value.
swap(x[i],x[k]); //swap them. I4 says x(i) must contain the min. value. Which is true at this pointer.
}
}
int testSort(int x [], size_t L)
{
SelectionSort(x,L);
if(isSorted(x,L))
{
cout << "Sorted!" << endl;
return 1;
}
else
{
cout << "Not sorted!" << endl;
return 0;
}
}
static const int LO_R = -10000;
static const int HI_R = 10000;
static const int RANGE = HI_R-LO_R;
int RandomInt()
{
return LO_R + int(RANGE*rand()/(RAND_MAX + 1.0)); //Not good rand()!
}
void fillRandArray(int x[], size_t L)
{
for(size_t i = 0; i < L; ++i)
{
x[i] = RandomInt();
}
}
static const size_t RANDOM_COUNT = 20000;
int main(int argc, char* argv[])
{
srand(unsigned(time(0)));
int maxLimit = numeric_limits<int>::max();
int minLimit = numeric_limits<int>::min();
int TA [] = {6,5,4,3,2,1,0,-1};
int TA1 [] = {maxLimit,0,-23,minLimit};
int TA2 [] = {minLimit};
int TA3 [] = {0,0,0,0,0,0,0};
int THE_RANDOM_BABY[RANDOM_COUNT];
int numPassed = 0;
size_t L = size_t(sizeof(TA) / sizeof(int));
numPassed += testSort(TA,L);
L = size_t(sizeof(TA1) / sizeof(int));
numPassed += testSort(TA1,L);
L = size_t(sizeof(TA2) / sizeof(int));
numPassed += testSort(TA2,L);
L = size_t(sizeof(TA3) / sizeof(int));
numPassed += testSort(TA3,L);
for(int i=0; i < 6; i++)
{
fillRandArray(THE_RANDOM_BABY,RANDOM_COUNT);
numPassed += testSort(THE_RANDOM_BABY,RANDOM_COUNT);
}
cout << "Total passed should be 10! Passed: " << numPassed << endl;
return 0;
}
Non-recursive, a bit verbose but seems to work.
For fun, I decided to do another implementation in perl. This one is inline and as terse as I could make it (also for fun). Though I’m sure some super perl monk could probably write it with even less code.
It was scary running this for the first time, but luckily everything seemed to work!
One bug found in test suite – boundary condition for input only holding MAXINT. Sigh.
@Paul Hubbard: I tend to think you should either sort the input array in-place, or leave it alone. Deleting all elements is a rather surprising side effect :)
Seems to work though, except that you deliberately don’t handle zero-length arrays. You could remove the asserts to fix that.
I’ve tested this with only the one array in the code (and only after deciding that my first draft would also be the final version ;-) ) but I think I have thought through all the edge cases…
@Paul Winkler – yes, I think you’re right on both counts. Deleting the input is really not what a caller would expect!
It’s odd, but for these sorts of things I always go back to plain C.
First time setting up invariants, bound function and pre/postconditions. I’m not sure I did it right but the function seem to do what it should…
Praying that the source-bracketed source shows up as source…
Got it nearly right the first time – input with MAXINT in it resulted in an endless loop.
perl, just because it’s quickest for me to code.
takes an array ref and sorts in-place.
seems to work in the tests I ran it through (after completing coding, naturally): an array with 100 random ints, an array with 100 of the same int, an array with 100 ints already in sorted order, an array with a single element and an empty array.
Here’s a shot at in place:
Compiled, and tested with n==0, n==1, descending, ascending, and duplicate values. Worked first time, though my “is_sorted()” function used for testing had a bug (>= vs >).
Seems to work with single, random, sorted and co. array.
Any way, may be buggy but it was always fun to quick write some c89 codes like that, back of the day. More!
This time my first try worked! Inherently simpler algorithm than binary search, I guess, or maybe I was just more careful. Here’s my answer in PLT Scheme:
If using “min” with more than two arguments is cheating, then replace “(apply min l)” with “(foldl min (car l) (cdr l))”.
Ah well, I just realized my solution only works with exact numbers, because of inexact contagion in min. Change remq to remv and it works for all numbers. (And that last line was indented with a tab, which for some reason WordPress converts to 4 spaces instead of 8.)
Fail. Turns out remv doesn’t work either for lists containing inexact numbers; you have to use “(remove m l =)”. Or just redefine min with “(define (min x y) (if (< x y) x y))" and remq works in the original solution. Sigh.
Here goes nothing…
Doug Orleans: Sounds like Scheme isn’t the language for you, eh?
Pingback: What does it take to test a sorting routine? « The Reinvigorated Programmer
Doug Orleans, that’s a real shame. Your Scheme version of selection sort was my favourite of all the submissions so far, and a nice advertisement for how concise and elegant Lisp can be.
Language: JavaScript / ECMAScript
Damnit! Had 2 bugs, guess it was just late… I added code that reverses the end result by mistake and IN that code I had a bug that caused an endless loop.
Loving this series by the way! Had never written a selection sort or binary search before, languages or frameworks take care of that for me usually.
WAS:
SHOULD HAVE BEEN:
In Java:
Here’s another C++/STL version. Succeeds on all the edge cases I could think of.
I passed by the skin of my teeth. My initial draft had a pretty serious bug, and just before I was about to hit Run, I noticed it and rewrote.
@Arild
Thanks for helping with the clarification. And yeah, it’s fun what sort of complexity you can avoid if you just ignore one of the performance constraints. (O(1) additional space in this case.)
@mdhills
It’s O(N^2) time just like all the others, but it’s definitely not O(1) additional space like a proper selection sort is. I think there are definitely a few conceptual hurdles to being able to read haskell (or ml, etc.) code — pattern matching, the way the particular language says “cons,” etc. — but once you get your head around it works out pretty well. (Although I still have trouble reading point-free code….)
Here it is in C. Seems to work, though admittedly not tested particularly exhaustively (couldn’t think of edge cases beyond the empty array and an array with multiple values the same).
My in place python solution. This worked the first time and passed all the tests I could think of. I did spend a lot of time thinking it through (I failed the binary search test.)
I’ve put mine up at along with test cases derived from the next post.
Worked perfectly first time: I have redeemed myself!
I wrote that on my iPhone the other night… and quickly verified that it compiles (forgot a semicolon) this morning.
That said no testing, no reading, so the code is likely to be wrong…
That’s C/C++ code.
Sigh, once again, with code tags. Ruby, in place:
It sorted correctly the first time I ran it:
Pingback: Select Sort « Åke i exil
I noticed nobody used the old xor trick to swap the element values. Probably just as well :)
Haskell:
Now that I’m committed to the above code, I’ll go test it and report back, as per the rules. (Time passes.)
I tested it and it works on the empty list but messes up precisely in that elements are sorted in reverse order. The correct code is
‘maximum’ instead of ‘minimum’. Count me as another coder who can’t write correct code the first time around (even if the fix took < 10ms).
Failure.
php:
I noticed nobody tried the old trick-sort trick.
The result [i]is[/i] a sorted array ;)
But I had one error: the first range was range(n-1) initially
:’-(
Eventually I’ll catch one of these on a day when I’m writing in ruby, but today we get JavaScript.
Shorter version:
Appears to be correct based on comparison of 1e8 randomly populated arrays. Wish I could have participated in the last one, but I didn’t see the “don’t test until finalized” instruction until it was too late :P
C++. I think it works fully (at first), but I’ll have to read the follow-up article to know for sure ;)
My python function worked the first time it was executed:
I came late to the game but here is my untested entry, it should work fine. It’s C#
Ok, just after posting i saw my stupid error caused by the swap, here is the corrected version:
I guess i should not rush in this kind of things.
Jeff Dege pointed out:
That’s because I explicitly addressed it it both the earlier precondition/postcondition article and the followup on how to test a sort routine.
Preconditions and postconditions are irrelevant to the issue of whether a trick sort meets the stated requirements.
A trick sort would clearly have failed the tests you described in your follow-on post.
But if you read the actual requirements you provided in this post, you don’t explicitly state that the resulting sorted output must contain the same elements as the unsorted input. You simply assume it. Which most folks do, when they express this problem.
Which is why it’s so common for the trick sort to be a correct solution for the problems of this sort – vague or incomplete requirements.
As for the complaints about the readability of Haskell, well, consider APL. The link is APL code for a quicksort, not a selection sort, but it clearly demonstrates that APL maintains its reputation for opacity:
Late, but better than never? Tested on some obvious boundaries and a few “normal” arrays and it works for those. Point out where I’m wrong though. Looking forward to reading the follow up.
It’s C by the way… and I just noticed that the selection_sort function doesn’t properly return anything, and should probably be returning void anyway, so there’s that.
Finally, because I forgot to say it before because it seemed so obvious…
These posts are gold. If you did nothing but post this kind of stuff (including some future post on asymptomatic growth) I would keep reading.
I wrote mine in Common Lisp, with maximum recursion in mind, and I cons a lot :). It passed my tests first time:
Here’s an array version in Common Lisp that uses the iterate library:
I had one bug – using shiftf instead of rotatef, which made ‘swapping’ elements clobber one of the values, so I guess for this one, I kindof fail. For one thing, I feel a lot less comfortable writing functions with indices into arrays rather than recursion (the indices remind me of my study in numerical maths – shudder).
I did it! (at least according to my testing).
It doesn’t change the array in-place it creates a new one, and it modifies the input. So while it works I think that it’s not O(n^2) (because Python list entry deletion is O(n)).
Language: Java
Time Taken: around 20 minutes.
Granted, it is not the shortest possible solution, but each method in there is pretty readable and clear, so this gives me a certain confidence that this might work.
(Just stuffed some values in it, and I got some -1 somewhere. Splendid.)
In Ruby:
! for the Ruby-idiom of showing in-place operations. I didn’t feel like making a new array.
For the non-Rubyists:
Requires an array, but size shouldn’t matter, nor contents, as long as they’re comparable (include Comparable module and define method).
Oops, is there a way to edit? No?
~2 minutes, tested after wrote, worked on all I passed it.
@Vince: that reminds me of this, the XOR’d doubly-linked-list with a single pointer:
I realize this is a few days late, but hey – it was fun to do.
Compiled and ran correctly the first time (including the test code).
Total time about 20 minutes. Language is Perl.
#!/usr/bin/perl
use strict;
use warnings;
my $success = 1;
foreach my $type_of_list qw(random empty flat only_one sorted reversed flat_at_start flat_at_end only_two_sorted only_two_reversed) {
my $items = list_of_values($type_of_list);
my $selection_sorted_items = selection_sort($items);
if (not correctly_sorted($selection_sorted_items, $items)) {
$success = 0;
print “Failure: $type_of_list list\n”;
}
}
if ($success) {
print “Success\n”;
}
exit;
##########################################
# Performs a selection sort on the passed list of values
sub selection_sort {
my $values = shift;
my $sorted_values = [];
my @remaining_values = @$values;
while (0 < @remaining_values) {
my $lowest_value = shift @remaining_values;
foreach my $entry (@remaining_values) {
if ($entry < $lowest_value) {
my $scratch_value = $lowest_value;
my $lowest_value = $entry;
$entry = $scratch_value;
}
}
push (@$sorted_values, $lowest_value);
}
return $sorted_values;
}
##########################################
# Returns 1 if the list is correctly sorted, 0 if not
sub correctly_sorted {
my ($items_list, $raw_list) = @_;
return 0 unless (@$items_list == @$raw_list);
my $last_value;
foreach my $entry (@$items_list) {
if ((defined $last_value) && ($entry < $last_value)) {
return 0;
}
$last_value = $entry;
}
return 1;
}
##########################################
# Returns a test list of integer values
sub list_of_values {
my $list_type = shift;
if ($list_type eq 'empty') {
return [];
} elsif ($list_type eq 'only_one') {
return [1];
} elsif ($list_type eq 'only_two_sorted') {
return [1,2];
} elsif ($list_type eq 'only_two_reversed') {
return [2,1];
} elsif ($list_type eq 'flat') {
return [2,2,2,2,2,2,2];
} elsif ($list_type eq 'flat_at_start') {
return [2,2,2,2,2,2,1];
} elsif ($list_type eq 'flat_at_end') {
return [1,2,2,2,2,2,2];
} elsif ($list_type eq 'random') {
return random_list(20,-32768,32767);
} elsif ($list_type eq 'sorted') {
my $sorted_list = [ sort {$a $b} random_list(20,-32768,32767) ];
} elsif ($list_type eq ‘reversed’) {
my $sorted_list = [ sort {$b $a} random_list(20,-32768,32767) ];
} else {
die(“Unimplemented test list type: $list_type\n”);
}
}
##########################################
# Returns a random list of integer values
sub random_list {
my ($n,$min_value,$max_value) = @_;
my $range = $max_value – $min_value + 1;
my $values_list = [];
for my $counter (1 .. $n) {
push(@$values_list, int(rand($range)) + $min_value);
}
return $values_list;
}
Oops. Looks like I failed. :( After extending my tests to check that the sorted lists do in fact have all the numbers in the original lists, it does not in all cases.
Now to figure out my mistake…
Ah. Line 33. I typoed a ‘my’ at the start of the line.
here’s mine. failed the first time because i started writing it one way (with the variable min holding on to the value of the smallest element, rather than the index of it), and i forgot to update the swapping code when i made that change. woops :P
i also accidentally tossed in a semi-colon on one line because i’ve been coding in java all week at work.
Failed the first time. Forgot “defined”.
I believe I succeeded! It worked against all the test cases assuming that I tested them correctly. I’m fairly happy since this is my first Ruby program that actually does something. Although, I’m sure it could be better.
In addition I really do feel that selection sort is easier than binary search but that could be because the binary search already got me thinking more.
Around 40mins in python because the tv is on :)
Using python.
The first time I was printing the results stupidly, but the actual sort function worked just fine.
prints the expected:
0
5
6
6
7
8
8
9
10
21
37
38
67
73
2938
I fail due to choosing an unfamiliar language/style combination: I tried to do it statefully in Haskell. I wrote my sort on paper during a boring meeting, so I couldn’t look up Haskell’s
Array(of which I couldn’t remember the names of basic operations) and
ST(which I had confused with something much simpler), so I didn’t finish converting pseudocode into valid Haskell. Had I done so, it would still have failed its tests, because in the selection step, I was obliviously searching the original array instead of the modified array.
Incidentally, because this was Haskell, I felt compelled to write the selection as a pair of folds with
enumFromToinstead of explicit recursion. The folds were shorter but seemed to me harder to verify, because their base cases were less explicit.
Took me about 30 minutes to write and mentally verify the solution (Visual Studio 2010 with R# 4.5). Language of choice was C# 3.
Algorithm –
Full program –
The initial implementation passed all my tests so I would say I succeeded :-).
PHP version, tested with empty, single element and multi elment arrays, including duplicated entries. Output was checked against the one produced by the library function sort. Seems to work fine. Time was around 15 minutes.
Sorry rphan your first try is wrong, what if all the integers are negative? You should always pick a pivot in the array/
Pingback: The long-overdue serious attempt at The Silmarillion, part 3: that was awesome! « The Reinvigorated Programmer
My implementation in Clojure:
I realized after running a couple quick tests that the filter will remove duplicate entries. So I guess I fail :(
(ssort [4 3 4 2 2 1 3]) would return (1 2 3 4)
In-place sort in C++. Right first time if my test cases are to be believed (and if I understood the algorithm description). Tested: (1) empty array, (2) one element, (3) already-sorted array, (4) array with duplicates. Hope my code formats correctly…
I haven’t tested it very carefully, but it seems to work.
Java implementation. First try.. failed.
Total failure.Great insuccess! :-D
I have forgotten a “=” (I have put a < in place of <= ) what a shame!
My final Java code is:
my complete test-suite is:
There are no excuse, I have failed
What a shame.
P.s: I have posted the “working” code
P.s2: I have implemented an in-place selection sort.
@Pontus
it looks like your solution/code is wrong it doesn’t manage the last array’s element! (IMHO)
Sorry for my being late but I’ve just seen the article and I hope to be still in time for posting.
It took me about 30/40 minutes to write and test on paper. C code. Worked on first try. No bugs.
I loved Doug Orleans’s Scheme solution (since I grepped for all Scheme solutions before submitting mine, just to see if anyone used my approach), though, it’s one I’d never have written: I’m too big on tail calls, and converting Doug’s solution to tail calls would probably have doubled its length.
Here’s my solution, which is vector-based rather than list-based. It works with empty vectors, singleton vectors, as well as “3 1 4 1 5 9 2 6 5 3 5″. :-P
Like my solution for binary search, you can pass in a custom predicate, so by using > you can sort by descending order, for example. (Then, after such sorting, use the same predicate for doing the binary search.)
None of the SRFI 1 nor SRFI 43 functions I used are particularly magical (not anything like finding the minimum element of a vector :-P); they just allow me to use things like reduce, iota, and vector-swap! without having to write them myself. :-P
P.S. It goes without saying that (just like my binary search submission) I have not changed the program since testing it, and it does work first time. :-P
The program works with PLT/Racket. You will need to adjust the SRFI loading lines if you’re using a different implementation, as well as the syntax for optional parameters (if your implementation supports it).
Refactored version that doesn’t look quite so scary (what with 4 levels of nested functions in the original). :-P
I must confess, I left out returning the array from the subroutine. So I DID sort the array on the first try …. the local array. I didn’t return it and so I printed the original unsorted array in the end.
So I claim a solid algorithm … just a fault interface :)
Man! There were several bugs in my first trial. One of which was just a name error, but another one was more of the logical kind. I think you should have chosen between in-place sorting and creating a new sequence, since the former is obviously more tricky — reason why I chose it, very arrogantly ;-). Below python code, refactored and tested (seems to work for empty seq, singleton, all elements equal, reverse order, random elements including duplicates):
I’m rather interested in your tests (also did the binary search one, and had this one correct at once). But I guess what they measure is a bit weird: not the ability to produce correct code, but the ability to produce correct code at once, without any test; which is not in my sense a sensible measure of programmer capacity. Hope I’m clear.
More precisely, these tests are biased. What I mean is there are various kinds of programmers, and there are good ones of every kind (see also your own post “the hacker, the architect and the superhero”). A common distinction is between “engineering” and “exploring” programmers. The latter start coding as soon as they have a clear enough “model” (mental image) to produce something hopefully useful, then *monitor* what the code actually does via feedback output, and update their model in accordance. The former first refine their model until they are rather sure it’s accurate, both in general outline and details, then only start coding with the presumption it should be correct. An interesting point is that for engineers a bug is just this, say a failure, while for explorators a bug is a useful source of information, if not of discovery.
I enjoy the exploratory coding style; not because it’s trendy (recent programming methodologies all support it), simply it fits my way. Above all, I find it more efficient in the long run, since it lends to learning new things. But your tests indeed favor the engineer style, don’t they?
Excellent point about different between engineers and explorers, spir; but don’t you think that even we natural explorers would be better programmers if we exercised our engineering muscles a bit as well? Like the way a natural musician can still improve his technique by practising scales. On this subject, see my earlier post Testing is not a substitute for thinking (binary search part 3).
“…don’t you think that even we natural explorers would be better programmers if we exercised our engineering muscles”
Yes, indeed, I fully agree. Especially since, in any discipline, it’s often easier and faster to improve our weaknesses than to improve our strengths, or even to mainain them. (again, hope I’m clear)
Thanks for giving me another motivation for putting in practice, and not only studying, methods like those introduced in later posts of yours (invariants, pre/post-conditions, etc) :-) I’m often confused in designing or implementating the kind of apps requiring a level of abstraction (that seems to fly) over my capacity; such tools may help, not only in having things right, but most importantly in better understanding key points.
Sorts list in-place. Seems to work on every test case I tried. Took 15 min to write & worked right the first time (I love Python); but I really had to reason about the end points of both loops. I also enjoyed your post on the invariants, pre/post-conditions.
Perl. Took about 15 minutes, and seemed to work the first time out, at least on everything I’ve thought to test it on (in order, reversed, random, empty).
Pingback: Another Challenge Met | Effluvium
It took me about an hour to think through this carefully. I decided to use PHP (which I’m still learning) and try to do it as much as possible in terms of functional programming. It seemed to work when I tested it. :-)
Untested.
Tested – looks like it works.
Here’s my attempt in Haskell. I passed, but initially I did miss out the recursive call to selection…I caught it before I ran the code, but only because I was going over it again. Normally I would have just run it.
Also, after looking over the other Haskell solutions this one looks like the first one not to use library functions. It’s definitely simpler if you use them…
Written in AutoIt 3 (because it’s neat)
The code seems to work correctly since the first try. It definitely took me longer though–20 – 30 min. Then I had to sleep so I had the opportunity to look over it again the next day. Didn’t make changes though.
I also write a PrintElements function to print out the array contents before I wrote the Selection sort itself. That one I *did* test (and did have to debug a little). (AutoIt has library code for this but it outputs to MsgBox and I wanted the output to go to the console window instead.)
I’m concerned that my code has three loops ( While, For, For ) whereas the other entrants seem to get by with just two. Oh well.
About Binary Search: I wasn’t there for that contest, but I ran into the situation described all on my own: many months back, for whatever reason, I wanted to implemented that cool binary search I’d learned in college and much to my dismay I found that, yeah, it ain’t nearly as easy as it seemed back in class. So I’m confident that if I *had* entered it, my coding would have taken a *long*, long time.
—
Furry cows moo and decompress.
This time I managed to hold off from reading the comments before giving my own attempt a shot (I sadly ended up “cheating” on the binary sort test).
A simplistic implementation in Python – written, then ran once on a few test cases which all turned out all right. Realized that I don’t check that I’m actually comparing numbers just after testing though, so I reckon it’s a bit flawed.
Your series of posts about the 10% programmers was a real eye-opener. Many thanks!
Python, failed first time. Took about 10 mins.
Purely-functional version of selection sort in Scala with iterative behavior and using persistent collections.
fumbled…..
my very first test with an empty array gave rise to an outright ArrayIndexOutOfBoundsException!!!
(coding in Java)
This mistake is gross, indeed…. I can’t but feel a little ashamed.
Nice blog, Mike!
Thanks, Marco, and kudos for coming out with an honest account of your attempt! Your comment is #200 on this article, which is pretty good going.
Yep, more than a year and a half old and still steamin’ ;-)
You know, I’m reading the blog’s archives like some sort of serial novel (got in a couple of days ago, looking for a nice explanation of the differences between ‘functional’ and ‘imperative’…) and I must say that what I like more is the lack of all the fruitless criticisms I found in my peregrinations round the net (both on your side and on the commenters’ (more or less :-))
And I can’t wait to see if in the end you manage to tame the Schemer of A Thousand Parantheses… ssssst don’t spoil the surprise :-D ahah.
Oh dear, better get to bed I suppose………………………
Yes, it’s been delightful in running this blog to have got such constructive, insightful comments so very much of the time. (There are a few exceptions, really, but they are literally one or two percent of all comments.)
I’m delighted that you’re enjoying going through the old material. I’ve been toying desultorily with the idea of compiling a bunch of TRP articles into a book, since mostly they are (by design) not “timely” but deal with pretty universal themes. With that in mind, it’s encouraging to know that the old material is still interesting to people.
As guessed from names, selection-sort! is destructive, and selection-sort returns the sorted string.
I did as for the binary search, the algorithms are tested, but not modified after testing. You may find bugs though, because I only tested that the code was not lame, not for edge cases.
P.S. code is tail-optimized. Correct me if anyone sees they are not and please tell me why.
P.P.S. “(lt” means “(less-than-sign”, where less-than-sign is the less than sign (OMG it’s ascii 0x3C damn you wordpress).
(defun minInList(l)
(labels ((keep-score (lRest last-ind)
(if (null (cdr lRest))
(if (lt (car lRest) (nth last-ind l))
(- (list-length l) 1)
last-ind)
(keep-score (cdr lRest)
(if (lt (car lRest) (nth last-ind l))
(- (list-length l) (list-length lRest))
last-ind)))))
(keep-score l 0)))
(defun selection-sort (lInit)
(let ((lResult lInit))
((lambda () (labels ((min-as-car (lRest)
(if (null (cdr lRest))
lResult
(progn
(rotatef (car lRest) (nth (minInList lRest) lRest))
(min-as-car (cdr lRest))))))
(min-as-car lResult))))))
(defun selection-sort! (lInit)
(labels ((min-as-car (lRest)
(if (null (cdr lRest))
T
(progn
(rotatef (car lRest) (nth (minInList lRest) lRest))
(min-as-car (cdr lRest))))))
(min-as-car lInit)))
I failed miserably. Even after I have thought about the invariant of the algorithm, I still couldn’t get it right the first time.
package random;
public class SelectionSort {
public static void main(String[] args){
int[] a = {3,7,1,2,5,0,9};
sort(a);
for (int e:a){
System.out.print(e);
}
}
public static void sort(int[] arr){
int i =0;
while (i < arr.length-1){
int min = i+1;
for (int j = i+1; j arr[j]){
arr[min] = arr[j];
}
}
swap(arr, min,i+1);
i++;
}
}
public static void swap(int[] arr, int p1,int p2){
int tmp = arr[p2];
arr[p2] = arr[p1];
arr[p1] = tmp;
}
}
A function written in Python:
I didn’t participate in the challenge, but I actually had cause to write a selection sort recently in real code. If you want to sort nodes on a graph, such that the next node in the array has some property relative to the ones before it (has the most connections to the previous elements in the array, in my case), the only sort function that will work that I can think of is selection sort.