1. Member Join Date
Feb 2011
Posts
78
Rep Power
0

## 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.  Reply With Quote

2. ## 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).  Reply With Quote

3. Member Join Date
Feb 2011
Posts
78
Rep Power
0

## 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.  Reply With Quote

4. ## 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.  Reply With Quote

5. Member Join Date
Feb 2011
Posts
78
Rep Power
0

## 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?
Last edited by fam2315; 07-27-2011 at 05:04 AM.  Reply With Quote

6. ##   Reply With Quote

7. Member Join Date
Feb 2011
Posts
78
Rep Power
0

## 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.  Reply With Quote

8. Moderator   Join Date
Feb 2009
Location
New Zealand
Posts
4,716
Rep Power
18

## 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.

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.  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•