Results 1 to 8 of 8
Thread: Sorting Algorithms
 07272011, 01:49 AM #1Member
 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.
 07272011, 02:11 AM #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).
 07272011, 03:26 AM #3Member
 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.
 07272011, 03:35 AM #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.
 07272011, 03:39 AM #5Member
 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 n1 remaining items?Last edited by fam2315; 07272011 at 04:04 AM.
 07272011, 04:35 AM #6
Are you trying to get me to answer all your homework questions? How about you read your notes, textbook, online resources and formulate your own answers to the questions. Write them down and hand them in.
 07272011, 04:43 AM #7Member
 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.
 07272011, 05:55 AM #8Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,708
 Rep Power
 13
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 n1 remaining items
Similar Threads

Help about data structures and algorithms
By herolua in forum New To JavaReplies: 2Last Post: 05212011, 05:57 AM 
Threaded algorithms
By TerTer in forum Threads and SynchronizationReplies: 0Last Post: 04202010, 02:58 PM 
Compression Algorithms
By kishan in forum Advanced JavaReplies: 1Last Post: 09212009, 09:13 AM 
genetic algorithms
By nurfadhillah in forum Advanced JavaReplies: 1Last Post: 10192008, 04:13 PM 
Iterative Algorithms
By Zosden in forum AlgorithmsReplies: 1Last Post: 07052008, 06:29 AM
Bookmarks