Join 131,724 Programmers for FREE! Get instant access to thousands of experts, tutorials, code snippets, and more! There are 2,307 people online right now. Registration is fast and FREE... Join Now!
In a topic www.wikipedia.org about sorting algorithm they say that "Whether or not they are a comparison sort. A comparison sort examines the data only by comparing two elements with a comparison operator."
My question is "What if I use to compare more than two elements to sort, is it still classified as a comparison sort?"
if more than two things how would it be classified?
Quantum? At the very least, theoretical.
Let's say I have three numbers, 5,4,3. I wish to sort them. Even though I have three items, when I compare, I still only compare two elements. The sort by hand would look something like this:
CODE
Starting list. Pos Value 0 5 1 4 2 3
Compare Pos0 to Pos1, if Pos0 is larger than Pos1, swap them. Pos Value 0 4 1 5 2 3
Compare Pos1 to Pos2, if Pos1 is larger than Pos2, swap them. Pos Value 0 4 1 3 2 5
Compare Pos0 to Pos1, if Pos0 is larger than Pos1, swap them. Pos Value 0 3 1 4 2 5
It may intuitively feel that you can compare more than two items at once, but when you break it down to individual operations, you're really doing it by pairs.
Hi guys can you help me.. What are the different advantage of using a sorting algorithm. Can you give me all its advantage from buss world to computer science world? Who benefits most when sorting algorithm is used??
Dunno if I understand you right but one huge benefit of sorting is when you operate on a huge set of data. Let's say you have 1,000,000,000 distinct numbers that you need to operate on. A good example is if you wanna find out if some (let's say 1,000) numbers are in that set.
If the numbers are not sorted, in worst case you'll have to go through approx. 1,000,000,000 * 1,000 numbers before you can give the answer.
If the numbers are sorted you only have to go through log(1,000,000,000) * 1000 numbers before you can give the answer which is substantially less (It's actually 30*1,000 = 30,000). The sorting would take some time (30*1,000,000,000) though but it's still much much faster.
That was really abstract but I guess anyone understands that handling 30,000,000,000 numbers is faster than handling 1,000,000,000,000 numbers
This post has been edited by Gloin: 12 Oct, 2008 - 05:53 PM
Let's say I have a value that I'm looking for in a sorted list. I start in the middle of the list and compare what I find there to my value. There are three possible outcomes of this one action. I find the value, I find a value larger than my value, or I find a value smaller than my value. Because the list is in order, I can now effectively ignore half my list.
This is the same as a number guessing game, which is why it's often offered to CS students as a problem. Pick a number between 1 and 100. Is it 50? Higher or lower? If you say lower, my next guess is 25. If you then say higher, my next guess is 32. In a list of 100 ordered values, it will never take more than eight guesses to find the answer. If I double the list size to 200, the effort it takes to find the number only increases by 1, and so on.
Hmm... don't know if that make more or less sense.
Dunno if it does but maybe after reading both our posts some ideas will start to form. What we're both referring to is one of the most well known (likely the most well known) algorithms that exist today, the binary search algorithm.
It lets you search through a set of n sorted values to find a specific value in logarithmic time. It's an extremely useful algorithm.
8 Oct, 2008 - 08:41 AM
| 