Quick sort

Discussion in 'Programmer's Corner' started by Cerkit, Feb 27, 2009.

  1. Cerkit

    Thread Starter Active Member

    Jan 4, 2009
    275
    3
    Hi. I am familiar with the Quicksort algorithm in C which can sort an array of values in ascending or descending position. Is there any way of using the quicksort to find the smallest value in an array but this time to know what position that value was in the array prior to the ordering??
     
    Last edited: Feb 27, 2009
  2. n9352527

    AAC Fanatic!

    Oct 14, 2005
    1,198
    4
    You will need a variable to keep track of the original position of the smallest value. Or an array with the same size if you need the original position of all values.
     
  3. Cerkit

    Thread Starter Active Member

    Jan 4, 2009
    275
    3
    Ok. I only need it to remember where the smallest value was in the array. How can I setup this variable??

    My initial idea was to put values after the decimal point and to be counting up gradually as the position in the array increases
    ie a set of random values [100.01,3007.02,1000.03,55.05] so that after the sort I can identify the position by looking at the values after the decimal point the only issue is that the quicksort only accepts integer values.

    Is there a simpler method?
     
  4. n9352527

    AAC Fanatic!

    Oct 14, 2005
    1,198
    4
    The easiest way is probably to do a pre-scan of the array to find the smallest value and recording the position. That will take one pass only, and can be used with any quicksort library. Another possibility is to insert the variable in the comparison section of the algorithm, it might take more time to do this, and access to the quicksort code, not a problem if you code your own.
     
Loading...