Programming Forums > Application Development > C

nnxion · Jun 15th, 2005, 10:58 AM

Quote:

Originally Posted by DaWei

I would use binary search. Bear in mind that the number of elements affects the efficiency opposite to the way it affects a sort, too. It's better to combine multiple sets and search the large set than it is to search the smaller sets.

For grins, you could fill the array with values generated by an exponential function and watch the linear interpolation search go to hell in a handbasket. An exponential interpolation would do well though. An example of an interpolative search is the way most people look up a word in the dictionary. The data are amenable, so that's what we use.

It just happens to be that every time I open a dictionary I land on the right page. No I wish, but I do pretty good most of the time with a deviation of a couple pages

.

On topic: Here are some sorting methods (also found here.)

Stable

Bubble sort � O(n2)
Cocktail sort (bidirectional bubble sort) � O(n2)
Insertion sort � O(n2)
Bucket sort � O(n); requires O(k) extra memory
Counting sort � O(n+k); requires O(n+k) extra memory
Merge sort � O(n log n); requires O(n) extra memory
In-place merge sort � O(n2)
Binary tree sort � O(n log n); requires O(n) extra memory
Pigeonhole sort � O(n+k); requires O(k) extra memory
Radix sort � O(n�k); requires O(n) extra memory
Gnome sort � O(n2)

Unstable
Selection sort � O(n2)
Shell sort � O(n log n) if best current version used
Comb sort � O(n log n)
Heapsort � O(n log n)
Smoothsort � O(n log n)
Quicksort � O(n log n) expected time, O(n2) worst case; generally believed to be the fastest known sort for large, random lists
Introsort � O(n log n)
Patience sorting � O(n log n + k) worst case time, requires additional O(n + k) space, also finds the longest increasing subsequences

Impractical sort algorithms
Bogosort � O(n � n!) expected time, unbounded worst case.
Stupid sort � O(n3); recursive version requires O(n2) extra memory
Bead Sort � O(n) or O(vn), but requires specialized hardware
Pancake sorting � O(n), but requires specialized hardware

What I'm not getting is why quicksort is not stable.

DaWei · Jun 15th, 2005, 11:11 AM

Because two identical records won't necessarily wind up in the original order. By identical, I mean identical insofar as the key. The remainder of the record could exhibit differences. Jean Jones and Bob Jones, for example, sorted on last name.

nnxion · Jun 15th, 2005, 12:50 PM

I still don't quite get what you're saying. Jean Jones and Bob Jones are not compared in full then?

By the way I learned a lot from this which has some nice information on searching, sorting, graphs, hashing etc.

DaWei · Jun 15th, 2005, 2:30 PM

Quote:

Jean Jones and Bob Jones are not compared in full then?

Not always. Consider a large database being sorted on one or a few fields. The rest of the data (fields) are still there. Sometimes one wants them to maintain their previous order within the sort, sometimes one doesn't care. Rather than sort on a primary field and a secondary field, one could sort on first name, THEN sort on last name, and achieve the same results IF the sort was stable.

EverLearning · Jun 15th, 2005, 2:42 PM

@nnixon: even if two entries are totally identical they still get switched around with respect to each other, you can see it from animation on the site you linked.

Jun 15th, 2005, 11:11 AM	#22
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	Because two identical records won't necessarily wind up in the original order. By identical, I mean identical insofar as the key. The remainder of the record could exhibit differences. Jean Jones and Bob Jones, for example, sorted on last name. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Jun 15th, 2005, 12:50 PM	#23
nnxion Programming Guru Join Date: Jun 2005 Location: elemental plane Posts: 1,429 Rep Power: 5	I still don't quite get what you're saying. Jean Jones and Bob Jones are not compared in full then? By the way I learned a lot from this which has some nice information on searching, sorting, graphs, hashing etc. __________________ "Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for." -- Socrates

Jun 15th, 2005, 2:42 PM	#25
EverLearning Hobbyist Programmer Join Date: May 2005 Location: Indiana Posts: 130 Rep Power: 4	@nnixon: even if two entries are totally identical they still get switched around with respect to each other, you can see it from animation on the site you linked. __________________ got math? yumm... "All men by nature desire to know" -Aristotle, Metaphysics Last edited by EverLearning; Jun 15th, 2005 at 4:24 PM. Reason: sorry, English

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C

interpolation search on a million