Selection sort with an array of structs

I am having trouble sorting members of a struct

Page 1 of 1

3 Replies - 7880 Views - Last Post: 27 December 2009 - 01:34 PM Rate Topic: -----

#1 AvtrOfWoe  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 01-December 09

Selection sort with an array of structs

Posted 01 December 2009 - 04:55 PM

I am trying to sort multiple elements in an array of structs. I can get the integers to order descending, but I am having trouble getting the names to sort with it.

Here is my heading


#include <iostream>				// Standard IO routine
#include <cstdlib>				 // Standard C++ library
#include <fstream>				   // File Stream
#include <string>				  // String Class
#include <iomanip>				 // Formatting

using namespace std;			   // Standard NameSpace





Here is the struct itself

struct soda {

	string name;
	double price;
	int numCans;
};

/* ========================================================================== */
/* TYPE DEFS */

typedef soda SodaMachine[MAX_NUM_DRINKS];






And here is the sort function I am having trouble with.


void SortAndPrint (int n, SodaMachine sodaMachine){
/* The SortAndPrint function sorts the items in the array
   based on numer of cans that are for a drink, then it 
   prints them out 

   Parameters:
   sodaMachine: the array of structs with the data in them.

   */
	


		int				 // 1st 3: type is index type of array
			start,	  
						// index to first value in unsorted portion
			largest,   // index to smallest value in unsorted
						// portion
			current,	// used to scan array for smallest value
						// temp: type is basetype of array
			temp;		// temporary storage during a swap

		// perform N - 1 passes
		for ( start = 0; start < (n - 1); start++ ) {

			largest = start;

			// scan unsorted part of array to find
			// smallest value
			for ( current = (start + 1); current < n; current++ )
				if ( sodaMachine[current].numCans > sodaMachine[largest].numCans )
					largest = current;
			sodaMachine[largest].name = sodaMachine[current].name;
				
			
			// perform one exchange of elements if
			// necessary
			if (largest != start){

				temp = sodaMachine[start].numCans;

				sodaMachine[start].numCans = sodaMachine[largest].numCans;
				sodaMachine[start].name = sodaMachine[largest].name;
				sodaMachine[largest].numCans = temp;
				
	}
			
} // outer for loop

			   // Print out the names
		for (int i = 0; i < MAX_NUM_DRINKS; i++){
	
		cout << i << ". " << sodaMachine[i].name << endl;
		cout << "Available: " << sodaMachine[i].numCans;
		cout << endl << endl;
	} // For Loop

} // SortAndPrint





Any and all help would be appreciated!

Is This A Good Question/Topic? 0
  • +

Replies To: Selection sort with an array of structs

#2 brds  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 76
  • View blog
  • Posts: 515
  • Joined: 22-October 08

Re: Selection sort with an array of structs

Posted 02 December 2009 - 08:26 AM

During the swap, swap *all* data, not just the number of cans.
struct soda temp; /* Storage for swapping all data */


Was This Post Helpful? 0
  • +
  • -

#3 jimblumberg  Icon User is online

  • member icon


Reputation: 4068
  • View blog
  • Posts: 12,550
  • Joined: 25-December 09

Re: Selection sort with an array of structs

Posted 27 December 2009 - 11:38 AM

View PostAvtrOfWoe, on 1 Dec, 2009 - 03:55 PM, said:

I am trying to sort multiple elements in an array of structs. I can get the integers to order descending, but I am having trouble getting the names to sort with it.

Here is my heading


#include <iostream>				// Standard IO routine
#include <cstdlib>				 // Standard C++ library
#include <fstream>				   // File Stream
#include <string>				  // String Class
#include <iomanip>				 // Formatting

using namespace std;			   // Standard NameSpace





Here is the struct itself

struct soda {

	string name;
	double price;
	int numCans;
};

/* ========================================================================== */
/* TYPE DEFS */

typedef soda SodaMachine[MAX_NUM_DRINKS];






And here is the sort function I am having trouble with.


void SortAndPrint (int n, SodaMachine sodaMachine){
/* The SortAndPrint function sorts the items in the array
   based on numer of cans that are for a drink, then it 
   prints them out 

   Parameters:
   sodaMachine: the array of structs with the data in them.

   */
	


		int				 // 1st 3: type is index type of array
			start,	  
						// index to first value in unsorted portion
			largest,   // index to smallest value in unsorted
						// portion
			current,	// used to scan array for smallest value
						// temp: type is basetype of array
			temp;		// temporary storage during a swap

		// perform N - 1 passes
		for ( start = 0; start < (n - 1); start++ ) {

			largest = start;

			// scan unsorted part of array to find
			// smallest value
			for ( current = (start + 1); current < n; current++ )
				if ( sodaMachine[current].numCans > sodaMachine[largest].numCans )
					largest = current;
			sodaMachine[largest].name = sodaMachine[current].name;
				
			
			// perform one exchange of elements if
			// necessary
			if (largest != start){

				temp = sodaMachine[start].numCans;

				sodaMachine[start].numCans = sodaMachine[largest].numCans;
				sodaMachine[start].name = sodaMachine[largest].name;
				sodaMachine[largest].numCans = temp;
				
	}
			
} // outer for loop

			   // Print out the names
		for (int i = 0; i < MAX_NUM_DRINKS; i++){
	
		cout << i << ". " << sodaMachine[i].name << endl;
		cout << "Available: " << sodaMachine[i].numCans;
		cout << endl << endl;
	} // For Loop

} // SortAndPrint





Any and all help would be appreciated!


You could the SDL's sorting algorithm to do the sorting.

#include <algorithm>

bool sodaSort(const SodaMachine &s1, const SodaMachine &s2)
{
   return(s1.numCans < s2.numCans);
}

void sortSoda(SodaMachine &soda)
{
   std::sort(soda.begin(), soda.end(), sodaSort);
}




The sortSoda() would be called after filling in the structure.
I would also change from using the array of SodaMachines to a
vector of sodaMachines.
Was This Post Helpful? 0
  • +
  • -

#4 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5826
  • View blog
  • Posts: 12,678
  • Joined: 16-October 07

Re: Selection sort with an array of structs

Posted 27 December 2009 - 01:34 PM

Your compare logic is mostly fine for the sort, but your swap is buggered. Also, your print prints max rather than n values.

I would implement separate swap:
void swap(soda &s1, soda &s2) {
	soda temp = s1;
	s1 = s2;
	s2 = temp;
}



Also, rather than passing "n" around all the time and forgetting about it, I'd use a struct for your list as well.

struct Soda { // note the upper case; be consistent with types.
	string name;
	double price;
	int numCans;
};

struct SodaMachine {
	Soda items[MAX_NUM_DRINKS];
	int size;
	// add some brains:
	SodaMachine() : size(0) {}
	void add(const soda &item) { items[size++] = item; }
};

void Print(Soda &soda) {
	cout soda.name << endl << "Available: " << soda.numCans << endl << endl;
}

void Print(SodaMachine &sm) {
	for (int i = 0; i < sm.size; i++){
		Print(sm.items[i]);
	}
}

void Sort(SodaMachine &sm) { /* your code here */ }

void SortAndPrint(SodaMachine &sm) {
	Sort(sm);
	Print(sm);
}


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1