Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Skyrunner]

I am learning C++, and for fun made a bubble wrap sorting and a gnome sorting.


10000 numbers : Bubble 3.79 units of time, 24985850 swaps made.
                     : Gnome 0 units of time, 81082 swaps made.

50000 numbers : Bubble 94.22 units of time, 626088997 swaps made.
                       Gnome 0.16 units of time, 524102 swaps made.

100000 numbers : Bubble 380.88 units of time, -1802926064 swaps made?
                         Gnome 0.17 units of time, 1085957 swaps made.

...Its really astonishing, how much bubble is outclassed...

Search on Wikipedia for bubble and  gnome.

[RulerOfNothing]

This is to be expected since bubble sort takes quadratic time to sort a list and in fact is particularly bad even for quadratic-time sorts.

[Levi]

Never heard of GnomeSort before.  Kind of neat.

My favorite when I was in school was MergeSort. 

[Skyrunner]

Never heard of GnomeSort before.  Kind of neat.

My favorite when I was in school was MergeSort.

Gnome sort has a really tiny code and is easier to code than insertion but better than bubble (which is not saying much ). It also has the added benefit of freezing if you try to sort more than 1000000 numbers on a 32 bit computer.

[malloc]

Never heard of GnomeSort before.  Kind of neat.

My favorite when I was in school was MergeSort.

Gnome sort has a really tiny code and is easier to code than insertion but better than bubble (which is not saying much ). It also has the added benefit of freezing if you try to sort more than 1000000 numbers on a 32 bit computer.

Which does not have anything to do with the amount of bits on your computer, but the fact that gnomesort has a average time complexity of O(n²). This means, that it's on average 100 times harder for gnome sort to sort 1,000,000 numbers, than it is to sort 100,000 numbers.

You should consider looking into Quicksort, Mergesort and Heapsort, they all have O(n * log(n)) time complexities, but have different advantages, like Mergesort being extremely easy to thread (Compared to the other sorting algorithms), Heapsort being memory efficient, and Quicksort just being a little hard to implement efficiently.
Sorting data is very serious business in computer science.

[Darvi]

Your links both lead to the same page.

Thought I'd mention it.

[Stargrasper]

I believe the fastest sorting algorithm is supposed to be heapsort.

[Thief^]

I did this at some point too, my favourite was shell sort.

[RulerOfNothing]

I did this at some point too, my favourite was shell sort.

Heh, shell sort is my favourite sort as well.

[Stargrasper]

I suppose it's worth noting that a large number of the sorting algorithms do have a runtime of O(n log n).  Which algorithm you use depends a lot of the data you're expecting to see.

Also, I've never actually seen shell sort.  I'll have to look into it.  And I still need to figure out heapsort or I'm never going to survive some of my later classes.

[Nadaka]

You may also have occasion to use a bucket or counting sort. With the right data, you are looking at nearly O(n).