Help with bubblesort.

quote:

---

Original post by caffeineaddict
i''m trying to use bubble sort to sort 2 different arrays with different types of data, one array has names, and the other has numbers, i sort the names first since i want them in alphabetic order...

---

ok wait a min, is there any reason you''re not group the two pieces of data together using struct or class?

---

--{You fight like a dairy farmer!}

Store the info in a structure, and sort based on the keys (strings in your case). Or, look into using any presupplied dictionaries/associative arrays. If you're using C++, consider std::map. It's hella fast, and SGI's hash_map is even faster. Those offer searching by key (string), as well as sorting.

Also, consider using Selection Sort, Insertion Sort, Merge Sort, or Quick Sort (some Google terms for you). All are more efficient than Bubble Sort, and about as easy to implement. I find a merge sort to be much simpler - and far more elegant - than a bubble sort.

Basically, unless you have to write a sort (special purpose, or some rule), use whatever's supplied. Do not fall prey to NIH (not invented here) syndrome.

[edited by - ze_jackal on November 17, 2003 4:34:30 PM]

I had need to sort some parallel arrays before, and the prospects are not good.

Since you''re writing your own sort, make it a template function, and when-ever you swap elements in the first array, swap the same elements in the second one.

I snarfed the STL qsort and doctor''ed it up to do this.

I did find a parallel iterator which claimed it could be used with std::sort, but I was using MSVC6 at the time, so nothing worked.

Thanks for the replies. I''ve changed it over to use a struct, but need to make a function to swap integers, then i should be done, thanks again.

template<typename T>
void swap(T& a, T& b)
{
    T temp = a;
    a = b;
    b = temp;
}

Or you could just use std::sort().

Bubble sort and similar are O(N^2)...merge sort(quick sort) is O(NlogN). Quick sort is implemented in std (and also in C). Why bubble?

After i converted it over to structures I got it working quite well, i''d never used them before and found them to be quite enjoyable to use. I think i will migrate over to more OOP code in my programs, it seems much more flexible, i''ve just been diehard C this whole time :-p

struct is a C keyword...

Yeah, i know struct is a C keyword, i just meant the style, it''s a bit like oop, well, maybe just a little more structured programming is what i''m looking for.

quote:

---

Original post by blizzard999
Bubble sort and similar are O(N^2)...merge sort(quick sort) is O(NlogN). Quick sort is implemented in std (and also in C). Why bubble?

---

Both merge sort and quick sort are horrendous on small inputs. Who knows, he may have bizarre data that makes quick sort O(N^2) It's entirely possible bubble sort is faster for his application.

---

[My site|SGI STL|Bjarne FAQ|C++ FAQ Lite|MSDN|Jargon]
Ripped off from various people

[edited by - wild_pointer on November 19, 2003 10:43:27 AM]

quote:

---

Original post by caffeineaddict
After i converted it over to structures I got it working quite well, i''d never used them before and found them to be quite enjoyable to use.

---

Wait until you start using classes - you''re going to have a blast!

---

"Absorb what is useful, reject what is useless, and add what is specifically your own." - Lee Jun Fan

quote:

---

Original post by blizzard999
Bubble sort and similar are O(N^2)...merge sort(quick sort) is O(NlogN). Quick sort is implemented in std (and also in C). Why bubble?

---

on partially sorted data bubble sort is quicker, inversely on reverse sorted data bubble sort is hideously slow (even slower than on random data)

you cant always use those rules in the real world

quote:

---

Original post by Narcist

on partially sorted data bubble sort is quicker, inversely on reverse sorted data bubble sort is hideously slow (even slower than on random data)

you cant always use those rules in the real world

---

It depends...I dont see why one should reimplement an algorithm everytime he need it! However it is possible to ''optimize'' a quick sort with pointers instead of value-copy...obviosly if the array to be sorted is VERY short a bubble sort can be faster. But It''s not possible to think about optimizations before writing working code! And qsort is ready to be used!

Well, it works quick enough for my purposes for now, and the list that needed sorting was fairly short(12 elements) so it wasn''t bad.

quote:

---

Original post by wild_pointer

quote:

---

Original post by blizzard999
Bubble sort and similar are O(N^2)...merge sort(quick sort) is O(NlogN). Quick sort is implemented in std (and also in C). Why bubble?

---

Both merge sort and quick sort are horrendous on small inputs. Who knows, he may have bizarre data that makes quick sort O(N^2) It''s entirely possible bubble sort is faster for his application.

---

nope, the O-thing(dont remember how its called now) is the worst case, so nothing with O(n^2) for quicksort... (what about bottom-up-heapsort? wasnt it O(n) ???)


T2k

quote:

---

Original post by T2k

nope, the O-thing(dont remember how its called now) is the worst case, so nothing with O(n^2) for quicksort... (what about bottom-up-heapsort? wasnt it O(n) ???)


T2k

---

the "O-thing" is not the worse case, it's an upper bound. Quick sort is O(N^2) in the worse case - in the average (and best) case it's O(NLogN).

The only linear sort I know of is bucket sort, which isn't practical in most cases.

---

[My site|SGI STL|Bjarne FAQ|C++ FAQ Lite|MSDN|Jargon]
Ripped off from various people

[edited by - wild_pointer on November 19, 2003 5:44:02 PM]

Big-O represents the complexity of an algorithm as the data set goes to infinity . Quick Sort''s worst case is indeed O(n²); it''s best/average case is O(n*log(n)). Merge Sort has O(n*log(n)) in best/worst/average case, but has 2n memory requirement (which can be troublesome). Bubble, Selection, and Insertion are O(n²) best-case.

For small data sets bubble, selection, and insertion are often faster than quick and merge (although if the set is numeric, a radix sort can be hella fast). Those algorithms (quick/merge) are very good on large datasets however.

There are no hard and fast rules as to what constitutes ''large'', and odds are that sorting that small an array is a negligible speed impact anyway. In this case, whatever is quickest and least error-pronbe to implement wins. std::sort and qsort are your friends here.

I'm not sure where on earth you get O(n^2) best case for bubble sort, on already sorted data bubblesort would be O(n) (scan through it once, make no changes so drop out early) - if there is only one item out of line then it would be O(2n), O(n^2) is worst case for bubble sort.

[edited by - Narcist on November 20, 2003 3:51:13 AM]