Results 1 to 8 of 8
  1. #1
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

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

  2. #2
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default

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

  3. #3
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    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.

  4. #4
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default

    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.

  5. #5
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    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 04:04 AM.

  6. #6
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default

    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.

  7. #7
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    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.

  8. #8
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    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.

Similar Threads

  1. Help about data structures and algorithms
    By herolua in forum New To Java
    Replies: 2
    Last Post: 05-21-2011, 05:57 AM
  2. Threaded algorithms
    By TerTer in forum Threads and Synchronization
    Replies: 0
    Last Post: 04-20-2010, 02:58 PM
  3. Compression Algorithms
    By kishan in forum Advanced Java
    Replies: 1
    Last Post: 09-21-2009, 09:13 AM
  4. genetic algorithms
    By nurfadhillah in forum Advanced Java
    Replies: 1
    Last Post: 10-19-2008, 04:13 PM
  5. Iterative Algorithms
    By Zosden in forum Algorithms
    Replies: 1
    Last Post: 07-05-2008, 06:29 AM

Posting Permissions

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