[proghelp]

Hello I was having problems getting a quicksort to work to sort words by the aplhabet, currently it is not changed much from when it sorted numbers, is there any advice on a way to fix it to do that. Thank you

 
#include <ctype.h>
#include <string>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <stdio.h>


using namespace std;

const int DATA = 1000;
int compare(const void* , const void*);


int main()
{
   int i;
   int m;
   int j;
   int n;
   char c;
   char list[DATA];
   string word[100];
	 

	cout << "Enter words:\n";

fgets (list, 256, stdin );		   

	printf ("You entered: ");
	cout << endl;
	printf (list);
	  cout << endl;

	while (list[i])
  {
	
	if (isupper(list[i])) list[i]=tolower(list[i]);
	putchar (list[i]);
	i++;
	}

cout << endl;
qsort(list, DATA, sizeof(char), compare);


   cout << endl;
   cout << "The sorted list of words:\n";

  printf (list);
   cout << endl;

   return 0;
}

	int compare(const void* pnum1, const void *pnum2)
// compares two numbers, returns -1 if first is smaller
// returns 0 is they are equal, returns 1 if first is larger
{
	int num1, num2;

	num1 = *(char *)pnum1;  // cast from pointer to void
	num2 = *(char *)pnum2;  // to pointer to int
	
	
	if(num1 < num2)
		return -1;
	else
		if (num1 == num2)
			return 0;
		else
			return 1;
	}

 

[n8wxs]

There are quicksort tutorials on the the site. See

Quick Sort: Everything You Wanted to Know
QuickSort Tutorial

Also
C++ Creating a general use sort class

[proghelp]

Thanks . Alright so now I have a quicksort program,. I am a begginer in programming how do i change the program and its parameters to work with strings.

#include <ctype.h>
#include <string>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <stdio.h>

using namespace std;

const int DATA = 1000;
char compare(const void* , const void*);
void QuickSort(int* list, int startIndex, int endIndex);
int SplitArray(int* list, int pivotValue, int startIndex, int endIndex);


int main()
{
   int i;
   int m;
   int j;
   int n;
   char c;
   char list[DATA];
   string word[100];
   int * words;
	   

	cout << "Enter words:\n";

	
fgets (list, 256, stdin );		   


	printf ("You entered: ");
	cout << endl;
	printf (list);
	  cout << endl;

	while (list[i])
  {
	
	if (isupper(list[i])) list[i]=tolower(list[i]);
	putchar (list[i]);
	i++;
	}



cout << endl;
QuickSort(words,0,DATA - 1);  

   cout << endl;
   cout << "The sorted list of words:\n";

   printf (list);
   cout << endl;

   return 0;
}



	
void QuickSort(int* list, int startIndex, int endIndex)
{
	int pivot = list[startIndex];					//pivot element is the leftmost element
	int splitPoint;
	
	if(endIndex > startIndex)						 //if they are equal, it means there is
													  //only one element and quicksort's job
													  //here is finished
	{
		splitPoint = SplitArray(list, pivot, startIndex, endIndex);
													  //SplitArray() returns the position where
													  //pivot belongs to
		list[splitPoint] = pivot;
		QuickSort(list, startIndex, splitPoint-1);   //Quick sort first half
		QuickSort(list, splitPoint+1, endIndex);	 //Quick sort second half
	}
}


int SplitArray(int* list, int pivot, int startIndex, int endIndex)
{
	int leftBoundary = startIndex;
	int rightBoundary = endIndex;
	
	while(leftBoundary < rightBoundary)			   //shuttle pivot until the boundaries meet
	{
		 while( pivot < list[rightBoundary]		  //keep moving until a lesser element is found
				&& rightBoundary > leftBoundary)	  //or until the leftBoundary is reached
		 {
			  rightBoundary--;						//move left
		 }
		 swap(list[leftBoundary], list[rightBoundary]);
		 //PrintArray(array, ARRAY_SIZE);			 //Uncomment this line for study
		 
		 while( pivot >= list[leftBoundary]		  //keep moving until a greater or equal element is found
				&& leftBoundary < rightBoundary)	  //or until the rightBoundary is reached
		 {
			  leftBoundary++;						 //move right
		 }
		 swap(list[rightBoundary], list[leftBoundary]);
		 //PrintArray(array, ARRAY_SIZE);			 //Uncomment this line for study
	}
	return leftBoundary;							  //leftBoundary is the split point because
													  //the above while loop exits only when 
													  //leftBoundary and rightBoundary are equal
}

[KYA]

I would use the ASCII values of chars to compare them.

[proghelp]

Actually since I posted that I completely redid the problem, and my program works the problem is for the assignment I'm supposed to use the qsort function and have a count for each word for how many times it occurs. So now I have to change it. Any advice on how to do that?

#include <algorithm>
#include <iostream>
#include <cctype>
#include <string>
using namespace std;

struct to_lower {
  int operator() ( int ch )
  {
	return tolower ( ch );
  }
};


int main()
{
  string list[500];
  int nLength;
  string nTemp;
  int iCv;
  int i;
  char n;
  int q;

   cout << "Enter some lines of text  "
		 << "(Enter Ctrl-Z on a line by itself to exit)\n";
while ( !cin.eof() )
	{
	   
		cin >> list[i];
transform(list[i].begin(), list[i].end(), list[i].begin(), to_lower());
		i++;
	}
	

nLength = i;

	cout << "The sorted words would be:\n";


  for (iCv = 1; iCv < nLength; ++iCv)
  {
	//the new value to be inserted into a temporary location 
	nTemp = list[iCv];
	// k is the index of the number to the left of the iCv.
	int k;

	for (k = iCv-1; k >= 0 && list[k] > nTemp; k--)
	{
	  list[k+1] = list[k];
	}
	list[k+1] = nTemp;
  }
  for(iCv=0;iCv<nLength;iCv++) cout<<list[iCv]<<" ";
  cout<<endl;

  return 0;
}

[KYA]

Will you know the # of words during compile time?

[proghelp]

If you mean the number of all the words I suppose that i or nLength after cin would have whatever the number would be.

[KYA]

Word counting example:

#include <iostream>
#include <fstream>
#include <string>

int main()
{
std::ifstream inFile;
inFile.open( "loremipsum.txt", std::ios::in );

if( inFile.is_open() )
{
std::string word;
unsigned long wordCount = 0;

while( !inFile.eof() )
{
inFile >> word;
if( word.length() > 0 )
{
wordCount++;
}
}

std::cout << "The file had " << wordCount << " word(s) in it." << std::endl;
}
return 0;
}

Assign word strings into an array. Then after the reading/assigning I would search through the array and calculate the total amount each word appeared. (You'll have to account for capitalization?) This can be stored in another array if you want. Print results.

[proghelp]

Thank you. I'll have to work on that. I realized I was doing the wrong qsort function earlier but what I have now isn't working any advice on that?

#include <algorithm>
#include <iostream>
#include <cctype>
#include <assert.h>
#include <string>
using namespace std;

struct to_lower {
  int operator() ( int ch )
  {
	return tolower ( ch );
  }
};

int compare (const void * a, const void * b)
{
  //return ( *(int*)a - *(int*)b );
	return (strcmp(*(const char **)a, *(const char **)b));

}


int main()
{
  string list[500];
  int nLength;
  string nTemp;
  int iCv;
  int i;
  int n;
  int q;


   cout << "Enter some lines of text  "
		 << "(Enter Ctrl-Z on a line by itself to exit)\n";
while ( !cin.eof() )
	{
	   
		cin >> list[i];
		transform(list[i].begin(), list[i].end(), list[i].begin(), to_lower());
		i++;
	}
	
nLength = i;

	cout << "The sorted words would be:\n";

qsort(list, nLength, sizeof list[0],&compare);

	 for (n = 0; n < nLength; n++) {
		cout <<" \n"<< n << list[n];
		
	}

  return 0;
}

[KYA]

Ideally, you should be able to modify this to use chars instead of ints. [i.e the first letter of the word, ascii values]

This post has been edited by KYA: 26 November 2008 - 07:57 PM

[proghelp]

Thank you for all the help so far. The qsort() function that I need to use is apparently part of cstdlib (stdlib.h) as shown in http://www.cplusplus...dlib/qsort.html although I have been trying to get it to work with strings. Here's what I have so far.

#include <algorithm>
#include <iostream>
#include <cctype>
#include <assert.h>
#include <string>
using namespace std;

struct to_lower {
  int operator() ( int ch )
  {
	return tolower ( ch );
  }
};

int compare (const void * a, const void * b)
{
  //return ( *(int*)a - *(int*)b );
	return (strcmp(*(const char **)a, *(const char **)b));

}

int main()
{
  string list[500];
  int nLength;
  string nTemp;
  int iCv;
  int i;
  int n;
  int q;
  int word[500];
   

   cout << "Enter some lines of text  "
		 << "(Enter Ctrl-Z on a line by itself to exit)\n";
while ( !cin.eof() )
	{
		cin >> list[i];
		transform(list[i].begin(), list[i].end(), list[i].begin(), to_lower());
		word[i]=1;  
			   
		
		if (list[i]==list[i-1]);
		{
			word[i]=+1;
		}
		i++;
	}
	
nLength = i;

	cout << "The sorted words would be:\n";

qsort(list, nLength, sizeof list[0],&compare);

	 for (n = 0; n < nLength; n++) {
		cout <<" \n"<< n << list[n]<< word[n];
		
	}
  return 0;
}

This post has been edited by proghelp: 26 November 2008 - 08:20 PM

[ipushmycar]

Wrong thread.

This post has been edited by ipushmycar: 21 February 2011 - 02:41 PM