Sorting Algorithms

• 07-27-2011, 01:49 AM
fam2315
Sorting Algorithms
I am studying algorithms in my data structures class, and have the following question

How many comparisons are necessary to find the largest and smallest of a set of n distinct elements?

It seems incomplete, as I thought that the computational complexity represented the number of comparisons, but this value varies from algorithm to algorithm.
• 07-27-2011, 02:11 AM
Junky
This is a search question not a sorting question. It depends if the elements are already sorted or not. If they are sorted then the smallest would be the first element and the largest would be the last element: O(1). Whereas if the elements were unsorted then you would have to look at every element to find the smallest or largest: O(n).
• 07-27-2011, 03:26 AM
fam2315
As a follow on, can the number of comparisons and interchanges made by a particular sorting algorithm be derived from the computational complexity? I have to figure out the number of comparisons made by a few algorithms if the order is sorted or reversed, and I was thinking that maybe I could derive that from the complexity. My thinking is that if I have a Simple Insertion sort, which has a computational complexity of On^2 in best average and worst case, so I would say that the number of comparisons is n^2 regardless of the order of the data, but I'm unsure of what is meant by interchanges.
• 07-27-2011, 03:35 AM
Junky
The number of comparisons and swaps made during a sort depends upon 2 things, the algorithm and how "sorted" the elements already are. By this I mean sorting 1,2,4,3,5 will only takes 1 swap whereas sorting 3,2,5,1,4 will take numerous swaps. As a result I doubt you can apply a formula to determine how many swaps/comparisons are made.
• 07-27-2011, 03:39 AM
fam2315
would you be willing to help me with a few more? I honestly am not sure about this one

Show that if c is the smallest number greater than or equal to n+(log2n)-2, c comparisons are necessary for finding the largest and second largest elements of a set of n distinct elements.

I used as an example a set of 16 numbers, Then c is 18, so we need 18 comparisons to find the largest item, and I would guess you would have to do the same on the n-1 remaining items?
• 07-27-2011, 04:35 AM
Junky
• 07-27-2011, 04:43 AM
fam2315
no, I never said 'give me the answer', and furthermore, I put down what I thought was a step in the right direction...I was just asking one last question, but If you don't know, that's fine.

And btw, this is an online resource :-)
Thanks anyway.
• 07-27-2011, 05:55 AM
pbrockway2
Quote:

I used as an example a set of 16 numbers, Then c is 18, so we need 18 comparisons to find the largest item,
No. You can always find the largest with 15 comparisons by starting with any element and comparing the rest with the largest-found-so-far. What you are told to show is that 18 comparisons are enough to find the largest and second largest.

Quote:

and I would guess you would have to do the same on the n-1 remaining items
That would require 35 or 36 comparisons to find the largest two. (or 29 if you accept my comment above). Which is somewhat larger than 18.