QuickSort Still Not Working??

Question

nabil1983 0 Junior Poster in Training

18 Years Ago

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

c

3 Contributors
5 Replies
177 Views
13 Hours Discussion Span
Latest Post 18 Years Ago Latest Post by dwks

dwks 149 Posting Whiz in Training

18 Years Ago

Don't use gets(). It's dangerous. Use fgets() instead. (http://faq.cprogramming.com/cgi-bin/smartfaq.cgi?answer=1049157810&id=1043284351)

fflush(stdin) is also wrong. (http://faq.cprogramming.com/cgi-bin/smartfaq.cgi?answer=1052863818&id=1043284351)

main() should return a value. printf("%d",&ch);

Ancient Dragon 5,243 Achieved Level 70

18 Years Ago

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 here 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;
}

Reply to this topic

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.

nabil1983 0 Junior Poster in Training · Answer 1 · 2005-12-11T05:29:03+00:00

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???

Ancient Dragon 5,243 Achieved Level 70 Team Colleague Featured Poster · Answer 2 · 2005-12-11T05:38:52+00:00

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.

dwks 149 Posting Whiz in Training · Answer 3 · 2005-12-11T05:40:33+00:00

For reference, the other thread is here: http://www.daniweb.com/techtalkforums/thread36544.html