So for a project I am working one of the parts needs sorting. This is all done in MIPS assembly language. Currently I am debating between using either Insertion or Bubble Sort. I know these two are slow compared to Merge and Quick sort but I am trying to get this is the least number of static/dynamic instructions. Which one would be more efficient in this case? I feel like there is always a trade-off between speed and memory usage. Is that true?
2
-
2Quicksort is in-place, just like insertion sort and bubble sort. Merge sort uses O(n) extra memory. See en.wikipedia.org/wiki/….Oliver Charlesworth– Oliver Charlesworth2013-07-06 02:55:53 +00:00Commented Jul 6, 2013 at 2:55
-
2don't use bubble sort. Ever. It's O(N^2) and it will come back to haunt you...Mitch Wheat– Mitch Wheat2013-07-06 02:55:55 +00:00Commented Jul 6, 2013 at 2:55
Add a comment
|
2 Answers
It highly depends on the size of the arrays you want to sort. For big arrays, simple sorting algorithms, as bubble sort tend to be very slow.
Most people don't know that because of the small code size, for small enough arrays bubble sort can be even faster than quick sort (and other "fast" sorts).
So:
If your arrays are variable size and the maximal size if pretty large - use quick sort (or similar) - or later you should explain how an assembly program is so slow. :)
If the arrays are small enough (probably up to several hundreds elements) use bubble sort and you'll have both - small code size and high performance.
In my experience, array sorting is not so common operation. Are you really, really sure, you need to sort these arrays?
1 Comment
user2507560
That was a very helpful response. Yes I do. I ended up using Insertion sort mainly because it was easier to code (at least for me) in assembly. However thank you very much for the response. It was insightful and helpful.
My recollection of insert sort is that you receive new records one at a time, so if you already have data to sort, you will need twice the size of the data - one to read from, one to write to. For any non-trivial dataset, this will probably cost more memory than the sort algorithm. Bubble sort can be done in-place (i.e. if you already have a block of data to sort, it only needs enough extra memory to store one record, or even one byte, depending on the data.
A bubble sort would also require less code to write.
As for there always being a trade-off between speed and memory (or, indeed, any two resources), that is not always the case. However, if method A is quicker and simpler, and uses less memory than method B, then B doesn't really come up for contention.
