Member Avatar for nabil1983

Hey after spending a few hours trying to understand why my quick sort is not owrking, i've tried calling the q_sort() and quick_sort() but with no luck......
below is how i had it from the start for less confusion,, can someone tell me why it isnt working...
i've checked the layout in a couple of books also and it seems fine for a structure sort algorithm.

Ancient Dragon u said something about the count in q_sort() not being right but when i change i end up with compile errors.....??..

//(Database Management System(DBMS), user interface and report generator for results. 
//Also a diagnostic tool that allows access to the database metrics. 
//This is to show the efficiency of the sort algorithms used.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <io.h>
#include <conio.h>
//******************************************************************************************//

//Structure

struct CdRecords
	{	
 		char Artist[20];
		char Album[20];
		char Year[8];
		char Label[20];
		char Genre[20];
	};
//******************************************************************************************//

void naive_sort (struct CdRecords array [], int arraySize, int * count);
void swap (struct CdRecords * v1, struct CdRecords * v2);

void write_records(struct CdRecords cdDB[]);
void write_file(struct CdRecords cdDB[]);	
void read_file(struct CdRecords cdDB[]);
void delAlbum(struct CdRecords cdDB[]);

void sort_critical_count(struct CdRecords cdDB[], int choice);
void record_search(struct CdRecords cdDB[]);

void quick_sort (struct CdRecords array [], int left, int right);
void q_sort (struct CdRecords array [], int count);

void init_list(struct CdRecords cdDB[]);
int find_free(struct CdRecords cdDB[]);



const int datasize = 20;
// file pointer
FILE * fp;


//******************************************************************************************//
void init_list(struct CdRecords cdDB [])
{
	//int i;					//TO CONTROL LOOP FOR CLEARING STRUCTURE
	//for (i=0;i<datasize; i++)
	//	cdDB[i].Artist[0] = '\0';	//SET THE TITLE TO NULL	
	memset(cdDB,0,datasize*sizeof(struct CdRecords));
	//TO CLEARING STRUCTURE
		//SET THE TITLE TO NULL
}
//******************************************************************************************//
//FIND FREE SLOT TO ADD NEW ENTRY

int find_free(struct CdRecords cdDB[])
{
	int i;
	char test;				//FIELD TO CHECK FOR A VALUE IN TITLE
	for(i=0; i<datasize; i++){
		test = cdDB[i].Album[0];	//STORE TITLE IN TEST FIELD

		if (test=='\0'){		//IF TEST FIELD IS NULL THERE IS AN EMPTY SLOT		
			return i;		//RETURN THE SLOT NUMBER
	}

	}

	return -1;				//IF NO FREE SLOTS FOUND RETURN -1
}
//******************************************************************************************//

void sort_critical_count(struct CdRecords cdDB[],int ch)
{
     system("CLS");
	 int count = 0;
	 int nRows = find_free(cdDB);
     naive_sort (cdDB,  nRows, & count);

     //naive_sort (cdDB, datasize, & count);
	 
	 					//if(ch==3){
	 					//q_sort (cdDB, count);
						// }
     if(ch == 5)
        printf("\nCritical count is : %d\n",count);
     else
        printf("Array has been sorted");
     printf("Press Enter To Continue");
     fflush(stdin);
     getch();
}	

//******************************************************************************************//

void write_records(struct CdRecords cdDB[])
{	
	system("CLS");     	
    int i;    
	char ch;
	ch=1; 
	i=0; 
	int slot;				// INTEGER TO LOCATE FREE SPACE IN STRUCTURE
		char s[80];				// CALL THE FIND_FREE FUNCTION AND RETURN VALUE IN FIELD - SLOT
		slot = find_free(cdDB);
		
		if (slot==-1){				//IF SLOT = -1 THEN THE STRUCTURE IS FULL
	  		printf("Database Full");
		return;
	}
    //input Data from the keyboard
    //go through record 
    //write to disk using formatted output		
   // for (i=0;i<datasize;i++)
			
   // {	
			

       printf("Enter the Artist: \n");
       //scanf("%s",cdDB[i].Artist);
	   gets(cdDB[slot].Artist);
	   gets(cdDB[slot].Artist);
	   printf("Enter the Album: \n");
	   //scanf("%s",cdDB[i].Album);
	   gets(cdDB[slot].Album);
	   printf("Enter Label name: \n");
	   //scanf("%s",cdDB[i].Label);
	   gets(cdDB[slot].Label);
	   printf("Enter Year: \n");
	   //scanf("%d",&cdDB[i].Year);
	   gets(cdDB[slot].Year);
	   printf("Enter the Genre of music: \n");
	   //scanf("%s",cdDB[i].Genre);
	   gets(cdDB[slot].Genre);
	  // printf("Enter 1 to continue or 0 To Finish: \n");
	  // scanf("%d",&ch);  
	//if(ch==0)
		//{
		//break;
		//}          
   // }
}

//******************************************************************************************//
void delAlbum(struct CdRecords cdDB[])
{
	int slot;				//INTEGER TO HOLD SLOT NUMBER
	char s[80];				//FIELD TO HOLD INPUTTED RECORD NUMBER TO DELETE
	printf("Enter Album: ");		//PROMPT FOR Album TO DELETE
	gets(s);
	slot = atoi(s);				//CONVERT INPUT VALUE TO A SLOT NUMBER

	if (slot>=0 && slot < datasize)		
		cdDB[slot].Artist[0] = '\0';	//CLEAR SELECTED STRUCTURE ENTRY
}
//******************************************************************************************//
void record_search(struct CdRecords cdDB[])
{
   system("CLS");
   int i;
   char name[20];
     
   printf("Enter Artist name :");
   scanf("%s", name);
   for(i = 0;i<datasize;i++)
   {
     if((strcmp(name,cdDB[i].Artist))==0)
     {
	  printf("\n");
        printf("%s\n",cdDB[i].Artist);
	  printf("%s\n",cdDB[i].Album);
	  printf("%s\n",cdDB[i].Label);
	  printf("%s\n",cdDB[i].Year);
	  printf("%s\n",cdDB[i].Genre);
     
	 }
   }
   printf("Press Enter To Continue");
   fflush(stdin);
   getch();

}

//******************************************************************************************//

void write_file(struct CdRecords cdDB[])
{
    system("CLS");
	int i;
    fp=fopen("CD-Records.txt","w");
	
    for (i=0;i<datasize;i++)		
    {
         fprintf(fp, "%s		%s		%s		%s		%s\n",cdDB[i].Artist,cdDB[i].Album,cdDB[i].Label,cdDB[i].Year,cdDB[i].Genre); 
    }
    
		printf("Data has been written to file");
    		fflush(stdin);
    		getch();            
    		fclose(fp);//Close the file

		}

//******************************************************************************************//

void read_file(struct CdRecords cdDB[])
{
	system("CLS");	
	int j;
		fp = fopen("CD-Records.txt","r");
	//Read the data that was written	
		printf("reading data...\n");

      for (j=0; j<datasize; j++) 
      {
		if (cdDB[j].Artist[0]){	
		fscanf(fp,"%s %s %s %s %s",cdDB[j].Artist, cdDB[j].Album, cdDB[j].Label, &cdDB[j].Year, cdDB[j].Genre);
		printf("Record %d\n",j+1," is...\n");
		printf("%s\n",cdDB[j].Artist);
		printf("%s\n",cdDB[j].Album);
		printf("%s\n",cdDB[j].Label);
		printf("%s\n",cdDB[j].Year);
		printf("%s\n",cdDB[j].Genre);
		//printf("\n\n");
		}
		printf("\n\n");
	}
	
	  fclose(fp);
      printf("Press Enter To Continue");
      fflush(stdin);
      getch();     
	// close file 
}

//******************************************************************************************//

	// Sort an array of integers with inefficient version of bubblesort

void naive_sort (struct CdRecords array [], int arraySize, int * count)
 {
	int find_free();
   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;
  }

//******************************************************************************************//
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);
	}
//******************************************************************************************//

int main() 
{
     system("CLS");
     int ch = 0;
       
     struct CdRecords cdDB[datasize];
     init_list(cdDB);	//CLEAR THE STRUCTURE
      do{
        system("CLS");
        printf("MAIN MENU\n");	
        printf("Press 1 To Enter Records\n");	
        printf("Press 2 To Bubble Sort Records\n");	
		printf("Press 3 To Quick Sort Records\n");	
        printf("Press 4 To Save Records To File\n");	
        printf("Press 5 To Read Records From File\n");	  
        printf("Press 6 To Show Diagnostic Details\n");
        printf("Press 7 To Search For A Record\n");
		printf("Press 8 To Delete A Record\n");
		printf("Press 9 To Quit\n");         
        printf("Enter Your Choice : ");
        scanf("%d",&ch);
    
  switch (ch)
  		{
  
          case 1:
           	write_records(cdDB);
          	 	break;
		  case 2:
			sort_critical_count(cdDB,2);
          		break;
          case 3:
            quick_sort(cdDB,1,2);
          		break;
          case 4:
             write_file(cdDB);
         	  	break;
          case 5:
   	        read_file(cdDB);
         		break;
          case 6:
            sort_critical_count(cdDB,5);       
  				break;
          case 7:
           record_search(cdDB);
  				break;
		  case 8:
           delAlbum(cdDB);
  				break;	
          case 9:
  				break;
  		  default:			
printf("%d",&ch);  		
		break;	
      		 } 
  					
  		} while(ch !=9);
	}
  • 3 Contributors
  • 5 Replies
  • 189 Views
  • 13 Hours Discussion Span
  • Latest Post Latest Post by dwks

Dani AI

Generated

Several distinct problems in the posted program explain why QuickSort appears to “not work.” The replies from (unsafe input and fflush(stdin)) and (alternative indirect-sort and debugger advice) are on-target, but the QuickSort routine itself and how it’s called contain the real functional bugs: the inner-loop compares the wrong element (the code compares array[i] twice instead of comparing array[j] in the second loop), the pivot is kept as a pointer into the array rather than copied (so swaps can clobber the pivot), and the wrapper/arguments are confused — the code passes a critical-operation counter or literal indices (main calls quick_sort(cdDB,1,2)) instead of the actual number of active records. Also enable compiler warnings (-Wall) and fix the obvious I/O issues noted by (replace gets with fgets and remove fflush(stdin); make main return 0).

Concrete fixes:

  • Make a stable pivot copy: copy the pivot string into a local buffer before the partition phase.
  • In the partition loop check bounds before calling strcmp, and use array[j] in the second inner loop.
  • Call the sorter with real element indexes: either call a wrapper q_sort(array,n) that calls quick_sort(array, 0, n-1), or call quick_sort(array, 0, n-1) directly. Compute n from find_free (treat -1 as datasize if the DB is full).
  • Replace all gets() with fgets(buffer, sizeof buffer, stdin) and strip the trailing newline.
  • Fix any calls that pass addresses instead of arrays into fscanf (pass the array name, not &array).

A minimal corrected partition + recursion (uses existing swap()):

void quick_sort(struct CdRecords array[], int left, int right) {
    int i = left, j = right;
    char pivot[20];
    strcpy(pivot, array[(left + right) / 2].Genre);  /* copy pivot */

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

Checklist before testing: compute n (active records), call quick_sort(array, 0, n-1) or q_sort(array,n), compile with warnings, step through with a debugger to watch i, j, pivot, and test on small datasets.

Recommended Answers

All 5 Replies

Member Avatar for Ancient Dragon

It took a little while to work out the algorithm, but below is one way to sort the array indirectly using another integer array. First, initialze an int array with values 0, 1, 2, .... During the sort, swap these numbers instead of members of the original structure array. The algorithm was taken from which may have been the same one you used.

#include <iostream>
using namespace std;

struct str
{
	char name[80];
};

str s[] = {
	{"six"},
	{"seven"},
	{"eight"},
	{"Filex"},
	{"Max"},
	{"Albert"},
};


void q_sort(str array[], int numbers[], int left, int right)
{
  int pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = numbers[left];
  while (left < right)
  {
    while (( strcmp(array[numbers[right]].name, array[pivot].name) >= 0) && (left < right))
      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }
    while ((strcmp(array[numbers[left]].name,array[pivot].name) <= 0) && (left < right))
      left++;
    if (left != right)
    {
      numbers[right] = numbers[left];
      right--;
    }
  }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(array,numbers, left, pivot-1);
  if (right > pivot)
    q_sort(array,numbers, pivot+1, right);
}

void quickSort(str array[], int numbers[], int array_size)
{
  q_sort(array, numbers, 0, array_size - 1);
}

int main(int argc, char* argv[])
{
	int i;
	int array[] = {0,1,2,3,4,5,6};
	quickSort(s,array, 6);
	// duplicate the s array so that we can rearrange it
	// according to the order of integers in array[].
	struct str s1[6];
	memcpy(s1,s, sizeof(s1));
	for(i = 0; i < 6; i++)
	{
		s[i] = s1[array[i]];		
	}
	for(i = 0; i < 6; i++)
		cout << s[i].name << " ";
	cout << endl;
	return 0;
}
Member Avatar for nabil1983

Hey thanx for the help..... but when i try to incorporate the coding u wrote to the program u helped me with in the other thread ' Why is qsort not initialised here!!??''

it dont seem to work???

Member Avatar for Ancient Dragon

it won't work in your program as I wrote it. You have to make appropriate changes to the structure. If you are using a compiler that has a debugger, learn to use the debugger so that you can single-step through the program and see what is going on.

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.