Results 1 to 4 of 4

Math Help - Question on algorithm (Sorting)

  1. #1
    Member
    Joined
    Oct 2008
    From
    Singapore
    Posts
    160

    Question on algorithm (Sorting)

    Can someone guide me on this problem ?

    Use the divide and conquer approach to design an algorithm that finds both the largest and the smallest elements in an array of n integers. Show that your algorithm does at most roughly 1.5n comparisions of the elements. Assume n = 2^k.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    May 2006
    Posts
    244
    Quote Originally Posted by tester85 View Post
    Can someone guide me on this problem ?

    Use the divide and conquer approach to design an algorithm that finds both the largest and the smallest elements in an array of n integers. Show that your algorithm does at most roughly 1.5n comparisions of the elements. Assume n = 2^k.
    First what algorithm are you going to use?

    How about this:

    1. From the initial list of length n form pairs (a_{2^i},a_{2^i+1}), i=1, .. , n/2, and from these pairs form two new list, the small list of the smaller element from each pair and the large list from the larger of each pair. These now each have n/2 elements.

    2. For the small list of length n_s form pairs and form a new small list from the smaller of each pair giving a new small list of length n_s/2

    3. For the large list of length n_l form pairs and form a new large list from the larger of each pair giving a new large list of length n_l/2

    4. Repeat steps 2. and 3. untill the two lists are both of length 1

    Then the largest element in the original list is the element left in the large list and the smallest element in the original list is the element left in the small list.

    Now count the comparisons.

    .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2008
    From
    Singapore
    Posts
    160
    Quote Originally Posted by Constatine11 View Post
    First what algorithm are you going to use?
    I am planning to use mergesort to solve the problem, i am able to derive the worst case which is big oh(nlgn) based on your explanation, but i have no idea on how to show that that algorithm does at most roughly 1.5n comparisions of the elements.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2006
    Posts
    244
    Quote Originally Posted by tester85 View Post
    I am planning to use mergesort to solve the problem, i am able to derive the worst case which is big oh(nlgn) based on your explanation, but i have no idea on how to show that that algorithm does at most roughly 1.5n comparisions of the elements.
    The number of comparisons can be explicitly counted, and it does less than 1.5n comparisons with a discrepancy that goes to zero as n becomes arbitarily large.

    .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algorithm(Searching and Sorting)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 21st 2009, 11:41 PM
  2. Sorting Problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 15th 2008, 02:54 AM
  3. sorting fraction with linear time algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 11th 2008, 08:39 PM
  4. Fastest sorting algorithm
    Posted in the Discrete Math Forum
    Replies: 18
    Last Post: April 7th 2008, 08:31 PM
  5. sorting algorithm
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: November 26th 2007, 07:12 AM

Search Tags


/mathhelpforum @mathhelpforum