From: Andy (andyfaeglasgow_at_yahoo.co.uk)
Date: 02/06/04

Date: 6 Feb 2004 03:06:57 -0800

Hi all,

I'm trying to understand quicksort better comparing comparison counts
between quicksort and selection sort etc. I understand that for
n=100, there should be about 200 comparisons when sorting a random
array, but when the array is sorted, there should be about 5000.
However, this is not coming out in the results. In the code below,
comps[2] counts comparisons for a random array and counts[3] counts
those for an identical array that has already been sorted. I suspect
they must be in the wrong place because when I run the program,
comps[2] is always about 200 and comps[3] is always a little under
500. I would be grateful for any help.

(p.s. I know that you can just use the library methods in java but I'm
trying to learn programming).

public void quickSort(int [] randomNums, int left, int right)
         int p=partition(randomNums, left, right);
         quickSort(randomNums, left, p-1);
         quickSort(randomNums, p+1, right);
   private int partition(int [] randomNums, int left, int right)
      int pivot=randomNums[left];
      int p=left;
      for(int i=left+1; i<=right; i++)
      return p;

Relevant Pages

  • Re: quick sort
    ... void quicksort; ... int partition; ... and a populateIntArray(int *array, size_t size) function such ... printIntArray, quicksort() (yes, I'd have called it something ...
  • (patch for Bash) regex case statement
    ... Following up on my previous patch for regex conditional tests, ... /* Return an array of strings; ... int dollarflag, zeropad, compareflag; ... SHELL_VAR *var; ...
  • Re: Strategy or Iterator?
    ... It would be possible to write a class that returns the variations ... GNU General Public License for more details. ... protected CombinatoricOperator(Telements, int r) { ... An integer array backing up the original one to keep track of the ...
  • (patch for Bash) regex conditional tests
    ... 'regex' are returned in array variable SUBMATCH. ... Skipping of positional parameters, array elements, string ... int dollarflag, zeropad, compareflag; ... SHELL_VAR *var; ...
  • Re: The question regarding type of pointers
    ... int day_of_year ... According to my understanding daytab is pointing to the whole daytab ... array i.e it is equivalent to p3. ... daytab is converted to a pointer to the first ...