alright jerkies... the bubblesort...

[inkedmn]

lets see how many languages we can hack this out in...

here's python:


def swap(x, y):
return (y, x)

def bubble(l):
passes = len(l)
for i in range(passes, 0, -1):
for j in range(1, passes):
if l[j-1] > l[j]:
l[j-1], l[j] = swap(l[j-1], l[j])
return l


C++ and Java will be forthcoming :)

this shouldn't take long to write, so just do it now, mkay? ;)

[inkedmn]

Java:


class BubbleSort {

static int[] bubble(int[] nums) {
for (int j = nums.length; j > 1; j--) {
for (int i = 1; i < nums.length; i++) {
if (nums[i-1] > nums[i]) {
int tmp = nums[i-1];
nums[i-1] = nums[i];
nums[i] = tmp;
}
}
}
return nums;
}
}


:)

[inkedmn]

C++ :

(i got a TINY bit of help with this one regarding the fucntion returns pointer stuff, just FYI) :)


#include <iostream>

using namespace std;

int* bubble(int n[], int array_size) {
int temp;
for (int i = (array_size - 1); i >= 0; --i) {
for (int j = 1; j <= i; ++j) {
if (n[j-1] > n[j]) {
temp = n[j-1];
n[j-1] = n[j];
n[j] = temp;
}
}
}
return n;
}


maybe i'll try haskell...

[recluse]

Last time inkedmn entered a competition he first completed it in C++, so I thought 'Hey, this will be a good opportunity to learn Python!'. But inkedmn had already done it in Python. Now I thought 'Hey ! Inkedmn used Python, I'll use C++!'. But I was foiled again!!! Damn you inkedmn, damn you!

[darelf]

I would be interested to see a functional version (o'caml, et al)

[Strike]

With a hefty bit of thievery from http://puma.wellesley.edu/~cs231/fall01/midterm-review.pdf
here is a Haskell version


module BubbleSort where
bubblesort :: [Integer] -> [Integer]
bubblesort lst =
let (result, changed) = bsorthelper lst
in if changed
then bubblesort result
else result

bsorthelper :: [Integer] -> ([Integer], Bool)
bsorthelper [] = ([], False)
bsorthelper [a] = ([a], False)
bsorthelper (x:xs) =
let (y:ys, changed) = bsorthelper xs
in if x > y
then (y:x:ys, True)
else (x:y:ys, changed)


Throw that in a file named "BubbleSort.hs", install hugs, and in that directory run hugs and follow this session:

Prelude> :load "BubbleSort.hs"
Reading file "BubbleSort.hs":

Hugs session for:
/usr/lib/hugs/lib/Prelude.hs
BubbleSort.hs
BubbleSort> bubblesort [1, 2, 3, 4, 5]
[1,2,3,4,5]
BubbleSort> bubblesort [5, 4, 3, 2, 1]
[1,2,3,4,5]
BubbleSort> bubblesort [4, 1, 3, 5, 2]
[1,2,3,4,5]


Tar dar. I'll be working on a Scheme one in a bit, though maybe I'll try my hand at O'Caml.

[Strike]

Okay, after a bit of trial and error, I decided to do the Scheme one in a weirder way ... I did a reverse sort and then reversed the result. This worked much better than my attempts at a "normal sort", and it kinda sticks truer to the bubble sort idea (the max element bubbles down to the end for each pass) than any of the implementations I tried for the "normal" way of doing it. Anyway, here goes:


; Take the results of the "backwards" search and reverse them
(define (bubblesort lst)
(reverse (reverse-bubble-sort lst)))

;This one actually sorts backwards because it's easy to do that :)
(define (reverse-bubble-sort lst)
(if (null? lst)
'()
(let ((lst-with-max-at-head (reverse (put-max-last lst))))
(cons (car lst-with-max-at-head) (reverse-bubble-sort (cdr lst-with-max-at-head))))))

(define (put-max-last lst)
(if (null? lst)
'()
(if (null? (cdr lst))
lst
(if (< (car lst) (cadr lst))
(cons (car lst) (put-max-last (cdr lst)))
(cons (cadr lst) (put-max-last (cons (car lst) (cddr lst))))))))


----edit----
Note to self, never do the color coding by hand again. Takes forever.

[GnuVince]

Strike: for Scheme, use PrBacterio's program.

[phubuh]

It is against my morals to implement bubble sort

let rec quicksort = function
| [] -> []
| x :: xs -> let less, greq = List.partition (fun e -> e < x) xs in
quicksort less @ [x] @ quicksort greq

[augur]

Greetings,

This is my first post, and I know C++ examples have been posted, but let's take advantage of C++ features like templates and create a more generic bubble sort:
template <class TYPE>
TYPE* bubble(TYPE n[], size_t array_size)
{
for (int i = (array_size-1); i>=0; --i) {
for (int j = 1; j<=i; ++j) {
if (n[j-1] > n[j])
std::swap(n[j-1], n[j]);
}
}
return n;
}
This will work for every numeric type (char, int, float...) as well as any class that has the '>' operator defined, std::string's for example.

[jemfinch]

Originally posted by phubuh
It is against my morals to implement bubble sort

let rec quicksort = function
| [] -> []
| x :: xs -> let less, greq = List.partition (fun e -> e < x) xs in
quicksort less @ [x] @ quicksort greq


Why? Your quicksort is just as bad. Quicksort is O(n**2) on linked lists.

Jeremy

[PrBacterio]

Originally posted by jemfinch
Why? Your quicksort is just as bad. Quicksort is O(n**2) on linked lists.

Jeremy

Well the fact that quicksort, especially the incredibly naive version he posted, performs badly on immutable linked lists does not excuse implementing ANOTHER badly performing sorting algorithm operating on them, like the bubblesort. He simply should have implemented a better performing sorting algorithm, like a merge sort, instead :)

[phubuh]

Originally posted by jemfinch
Why? Your quicksort is just as bad. Quicksort is O(n**2) on linked lists.

But quicksort is so elegant, and probably faster (although it has the same complexity) as bubblesort in O'Caml.

[jemfinch]

Originally posted by phubuh
But quicksort is so elegant, and probably faster (although it has the same complexity) as bubblesort in O'Caml.

No O(n**2) algorithm is ever "elegant" :)

Aside from that, I've never really found quicksort to be particularly elegant; it's still O(n**2) in the worst case, and it by its very nature requires mutation, and thus can't be used functionally. I find merge sort much more aesthetically pleasing.

Jeremy

[sicarius]

Originally posted by jemfinch
No O(n**2) algorithm is ever "elegant" :)

Shouldn't the elegance of the algorithm be relative to the complexity of the problem? I'm not saying this problem in particular is complex, but blanket statements are best reserved for things that can be proven true.


--Edited to fix the quote

[PrBacterio]

Originally posted by jemfinch
No O(n**2) algorithm is ever "elegant" :)

Aside from that, I've never really found quicksort to be particularly elegant; it's still O(n**2) in the worst case, and it by its very nature requires mutation, and thus can't be used functionally. I find merge sort much more aesthetically pleasing.

Jeremy
Well the worst case for quicksort can, in practice, be avoided most of the time by using a better pivot selection method or randomizing the items before sorting.

I do agree however that in a purely functional situation, quicksort is pretty inappropriate. I do like it, however, for usage on mutable data structures, and when average, not worst-case performance is important. There is no single "best" sorting algorithm, imho.

[Strike]

Originally posted by PrBacterio
There is no single "best" sorting algorithm, imho.
Wrong, the best sorting algorithm is:
* randomize elements in lisit
* if list is sorted, we're done; if not, repeat

I mean .. look at how simple it is!

[sicarius]

Originally posted by Strike
Wrong, the best sorting algorithm is:
* randomize elements in lisit
* if list is sorted, we're done; if not, repeat

I mean .. look at how simple it is!


Ah! A man who truly knows what he is talking about! You just can't beat the Bogosort for enterprise applications. :D

[split]

Could someone tell me what O(n^2) means? I've heard about "O" before, but all I know is that is in some way related to speed of execution.

[jamessan]

It is basically a measurement of the worst-case scenario when running a program. With the example you gave, O(n^2) means that, at worst, for a given n related to the program (in this case the number of elements in the list), it will take at most n^2 amount of time to run the algorithm. This can also be used to express how much memory/space a program is going to use. Here's (http://www.nist.gov/dads/HTML/bigOnotation.html) a site with a more formal definition.

[split]

Thanks. The combination of your def. as an introduction and the dads site made it perfectly clear. Great forums, by the way.

[Flangazor]

ph3ar the bucket!


list sort( s, min, max )
list s;
typekey min, max;

{
int i;
typekey div, maxb[M], minb[M];
list head[M], t;
struct rec aux;
extern list Last;
if (s==NULL) return(s);
if (max==min) {
for (Last=s; Last->next!=NULL; Last = Last->next);
return( s );
}
div = (max-min) / M; /* Find dividing factor */
if (div==0) div = 1;
for (i=0; i<M; i++) head[i] = NULL;
/* Place records in buckets */
while (s != NULL) {
i = (s->k-min) / div;
if (i<0) i = 0; else if (i>=M) i = M-1;
t = s;
s = s->next;
t->next = head[i];
if (head[i]==NULL) minb[i] = maxb[i] = t->k;
head[i] = t;
if ( t->k > maxb[i] ) maxb[i] = t->k;
if ( t->k < minb[i] ) minb[i] = t->k;
}
/* sort recursively */
t = &aux;
for (i=0; i<M; i++) if (head[i]!=NULL) {
t->next = sort( head[i], minb[i], maxb[i] );
t = Last;
}
return(aux.next);
}

[Blag]

Give some time, and i can try to upload the solution in Euphoria, QBasic and Pascal! :D ;) :D