1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

plz help

Discussion in 'C' started by rahul_2550, Mar 20, 2007.

  1. rahul_2550

    rahul_2550 New Member

    Joined:
    Mar 20, 2007
    Messages:
    5
    Likes Received:
    0
    Trophy Points:
    0
    Hi everyone,
    I am trying to write a program on improving quicksort using insertion sort for small number of inputs.
    Here is the actual question:
    The running time of quicksort can be improved in practice by taking advantage of the fast running time of insertion sort when its input is “nearly” sorted. When quicksort is called on a subarray with fewer than k elements, let it simply return without sorting the subarray. After the top-level call to quicksort returns, run insertion sort on the entire array to finish the sorting process. How should k be picked? (Hint: This algorithm runs in O(nk + n lg(n/k)) expected time).



    i)Implement a quicksort algorithm with the above modifications. The implementation needs to work only for integer numbers (no need to do it for general objects). Use #define parameters for k

    #define n_value 500 //arbitrarily chosen

    ii)Generate a test integer data, compute the program run times for various k values and plot. Find the approximate k value for which the program run times are short. Present your findings along with your programs. Run the same experiment for several large n values. The test results would be independent of the data chosen.

    iii)Conclude how the k can be chosen (for optimum performance of the algorithm) from a practical point of view?

    If anyone can provide the code I would really appreciate it . Thanks a lot.
     
  2. DaWei

    DaWei New Member

    Joined:
    Dec 6, 2006
    Messages:
    835
    Likes Received:
    5
    Trophy Points:
    0
    Occupation:
    Semi-retired EE
    Location:
    Texan now in Central NY
    Home Page:
    No thanks. I think people should attempt to solve their own problems if they're getting grades or dollars for it. When the attempt fails, then we're here to help.

    I'd also suggest you read the "Before you make a query" thread. It suggests that your problem and solutions to it might be helpful to future readers, provided that you choose a sensible subject line.
     
  3. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,285
    Likes Received:
    364
    Trophy Points:
    83
    Dont you ask the same question to yourself that would you answer to such a thread.
     

Share This Page