Member Avatar for nabil1983

Does anyone know the code to show the critical count for a quick sort algorithm.
Basically my cd database is almost finished.
What i need to do is show a critical count for the quicksort


quicksort for my database

void q_sort (struct CdRecords array [], int count)
{
quick_sort(array,0,count-1);
}
void quick_sort (struct CdRecords array [], int left, int right)
{
int i, j;
char *x;
struct CdRecords temp;

i = left; 
j = right;

x = array[(left+right)/2].Genre;

do {
		while(strcmp(array[i].Genre,x)<0 && i<right) i++;
		while(strcmp(array[i].Genre,x)>0 && j>left) j--;
		if(i<=j) {
			temp = array[i];
			array[i] = array[j];
			array[j] = temp;
			i++; j--;
			
			}
			
			}while(i<=j);
			
		if(left<j) quick_sort(array, left, j);
	  	if(i<right)quick_sort(array, i, right);
	}

i used a naive sort and was able to show a critical count for that as shown below:

void naive_sort (struct CdRecords array [], int arraySize, int * count)
 {
   for (int pass = 0; pass <= arraySize - 2; pass++)
    { for (int counter = 0; counter <= arraySize - 2-pass; counter++)
       {
        *count = *count + 1; // count critical operations
        if (strcmp(array[counter].Artist,array[counter+1].Artist)>0)
	   swap (&array[counter], &array[counter+1]);
       }
    }
 }

// Exchange a given pair of values in an array
void swap (struct CdRecords * v1, struct CdRecords * v2)
  {
    struct CdRecords temp;
    temp = *v1;
    *v1 = *v2;
    *v2 = temp;
  }

critical count for naive sort

void sort_critical_count(struct CdRecords cdDB[],int choice)
{
     int count = 0;
     naive_sort (cdDB, datasize, & count);
     if(choice == 5)
        printf("\nCritical count is : %d\n",count);
     else
        printf("Array has been sorted");
     printf("Press Enter To Continue");
     fflush(stdin);
     getch();
}

neone know how i can implement this for the quicksort coding shown above !!
Also does neone know how u can output data ontoa excel spreadsheet??

apreciate all help!!
u all been a great help in recent days!!

  • 2 Contributors
  • 5 Replies
  • 305 Views
  • 23 Hours Discussion Span
  • Latest Post Latest Post by nabil1983

Dani AI

Generated

Short answer: count the operations that matter (comparisons and/or swaps) and increment a counter each time they occur inside the partitioning work. was right that the partition step does most of the work; passing an int *count through the recursive calls is preferable to a global because it keeps the code testable and thread-safe.

Instrumenting idea (keep it tiny and local): wrap the comparator so every strcmp increments the counter, then call that wrapper from the partition code. Example wrapper:

static inline int cmp_counted(const char *a, const char *b, int *count) {
    (*count)++;
    return strcmp(a, b);
}

Use that wrapper wherever comparisons happen. Also restructure inner while loops so the index/bounds check is evaluated before calling the comparator (this ensures no out-of-bounds strcmp calls and lets each comparison be counted explicitly).

A couple of important fixes for the code posted by : the second inner loop in the original routine reuses the left-side index where the right-side index should be used, and both inner loops evaluate strcmp before checking array bounds. Swap the order of the tests (check index bounds first) and make sure the right index is compared on the right side of the partition loop. Those changes prevent crashes and ensure the counter reflects every attempted comparison.

For exporting results to Excel, write a CSV and escape double quotes inside fields by doubling them. A small helper to write a quoted field:

void write_csv_field(FILE *f, const char *s) {
    fputc('"', f);
    for (; *s; ++s) {
        if (*s == '"') fputc('"', f);
        fputc(*s, f);
    }
    fputc('"', f);
}

Call this for each field, separate with commas, add \n for each record, and always check fopen for NULL. Finally, run the sort on identical input sequences (or seeded random data) when measuring, and record whether the counter counts comparisons, swaps, or both so experiments remain comparable.

Recommended Answers

All 5 Replies

Member Avatar for Narue

>Does anyone know the code to show the critical count for a quick sort algorithm.
Use a global variable, and realize that all of the work is done in the partitioning step of the algorithm. Beyond that, it's pretty simple to add a critical counter to quicksort.

>Also does neone know how u can output data ontoa excel spreadsheet?
Well, you could meander over to www.wotsit.org and try to actually output an xls file...or you could take the easier route and output a comma delimited file, then import it into Excel.

Member Avatar for nabil1983

Use a global variable, and realize that all of the work is done in the partitioning step of the algorithm.

or you could take the easier route and output a comma delimited file, then import it into Excel.

is there any example i can see for comma delimited file and could you explain the use of the Global Variable and Partitioning Step...
IM in a learning stage of C, but need info on these asap..

Edited by Dani because: Formatting fixed
Member Avatar for nabil1983

sorry mate ignore the partition and global variable quetion in my last post..
i just need to know aboutt comma delimmited files, how do i do it im quite confused on this one....

Member Avatar for Narue

>i just need to know aboutt comma delimmited files, how do i do it im quite confused on this one....
It's pretty straightforward. Open a file and write the values to it, separated by commas:

FILE *out = fopen ( "somefile", "w" );

while ( !done ) {
  /* Do something with counter */

  fprintf ( out, "%d", counter );

  if ( !done )
    fputc ( ',', out );
}

fclose ( out );

Format the file as necessary to get the spreadsheet that you want.

Member Avatar for nabil1983

I've tried that but for some reason it dont work. The program im working on is in the last Post i put. 'Finally Almost Finished 2 Problems!!'
Take a look there , cuz i got two vital problems in there. I've spent days and hours on this project and just these few things are giving me the problem.

I apreciate the help u've already given!!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.