C++ sorting program

Time sensitive project for school....

Page 1 of 1

9 Replies - 24845 Views - Last Post: 08 February 2006 - 09:33 PM Rate Topic: *---- 1 Votes

#1 gryphin  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 128
  • Joined: 29-October 05

C++ sorting program

Posted 02 February 2006 - 11:43 AM

I need to get this source code to run not only the quick sort but also the bubble sort that is in psuedo code in the source file running, and implement a third style of sorting.

They need to all three run at the same time showing the length of time it takes to sort the arrays it is to sort. Then it needs to also stay open long enough for me to write out the results. Anyone know how to help me?

Please help. Time is of the essence. Project must be turned in tomarrow before midnight. Thank you everyone ahead of time, I know you guys are great.


// CS1410 sorting Demo
//   - Bob Nielson


#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>
using namespace std;

const long int NUMBER=50000;   // # of integers to compare quick vs. bubble

// bubblesort function
void bubbleSort(int sortme[NUMBER], long int limit);   // sort
void fillArray(int array[NUMBER], long int limit);     // create the array
void displayArray(int array[NUMBER], long int limit);  // display the first n items
void swap(int& x, int& y);                             // swap x and y

// teacher supplied quicksort
void quickSort(int sortme[NUMBER], long int limit);    // sort
int compare(const void *arg1, const void *arg2);       // compare function

int main()
{
	// create the variables
	int numbers[NUMBER+1];	// array to sort
	long int limit;      // current number to compare
	long int stime;         // start time
	
	// seed the random # generator
	srand(time(0));
	
	// compare bubble times vs. quicksort times from 10,000 to NUMBER, inc by 10,000
	for (limit=10000; limit <= NUMBER; limit=limit+10000)
	{
  cout.precision(4);
  cout.setf(ios::fixed);
  cout << setw(10) << limit;

  // bubble
  fillArray(numbers, limit);
  stime=clock();
  bubbleSort(numbers, limit);
  cout << setw(10) << double((clock()-stime))/double(1000);

  // uncomment this to verify correct sort
  // displayArray(numbers,10);

  // quick sort
  fillArray(numbers, limit);
  stime=clock();
  quickSort(numbers, limit);
  cout << " " << setw(10) << double((clock()-stime))/double(1000);
  cout << "\n";

  // uncomment this to verify correct sort
  // displayArray(numbers,10);

	}
	
	return 0;
}


// bubblesort function
//    input  -  array to be sorted
//           -  number of items to sort
//    output -  sorted array
void bubbleSort(int sortMe[NUMBER], long int limit)
{
	// puesdocode for bubble sort
	//
	// begin bubblesort(array,limit)
	//     for i=1 to limit-1
	//        for j=i to limit
	//           if array[i] > array[j]
	//              swap(array[i],array[j]
	//           endif
	//        next j
	//      next i
	// end
	

}


// fill array - fills an array with random numbers
//   input    - array to fill
//            - number of items
//   output   - the array filled with random numbers
void fillArray(int array[NUMBER], long int limit)
{
	int i;

	for (i=1; i<limit; i++)
	{
  array[i]=rand();
	}
}

// displayArray  -  displays the first n items in an array
//   input       -  the array
//               -  the number of items to display
//   output      -  displays the first n items in an array
void displayArray(int array[NUMBER], long int limit)
{
	int i;

	for (i=1; i<limit; i++)
	{
  cout << array[i] << " ";
	}
	cout << "\n";
}

// swap          -  swaps items x and y
//   input       -  2 items
//   output      -  the 2 items swapped 
void swap(int& x, int& y)
{
	int temp;

	temp=x;
	x=y;
	y=temp;
}


// quickSort      -  Quick Sort
//    input       -  a array to sort
//                -  # of items to sort
//    output      -  the sorted array
// NOTE:  -  For now disreguard the messy pointers (*)
void quickSort(int sortme[NUMBER], long int limit)
{
	qsort( (void *)sortme, (size_t)limit, sizeof(int *), compare);
}

// compare  - Compares two items
//          - negative if item1 is less than item2
//          - positive if item1 is greather than item2
//          - 0 if item1 == item2
int compare(const void *arg1, const void *arg2)
{
	int value = (*(char**)arg1)-(*(char**)arg2);
	return value;
}


Is This A Good Question/Topic? 0
  • +

Replies To: C++ sorting program

#2 Voodoo Doll  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 12
  • View blog
  • Posts: 108
  • Joined: 24-January 06

Re: C++ sorting program

Posted 02 February 2006 - 12:06 PM

Quote

Time is of the essence. Project must be turned in tomarrow before midnight.

Relax, you have plenty of time. Deep breaths are important to keep from getting panic'd. ;) The good news is that this program is all but done. You need to convert the pseudocode provided in bubbleSort to C++ code and you'll be finished, once you verify that the sort works, of course.

But I'm not going to do it for you. Translating pseudocode to real code is an important skill, so I want you to give it a try first. :) If you get stuck, or it doesn't work, we'll be happy to give you a hand.
Was This Post Helpful? 0
  • +
  • -

#3 dec1pher  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 1
  • View blog
  • Posts: 116
  • Joined: 27-January 06

Re: C++ sorting program

Posted 02 February 2006 - 01:43 PM

gryphin you can translate it i trust too or you'll face with the psuedo gods!

- P.S:
>> They need to all three run at the same time showing the length of time it takes to sort the arrays it is to sort.

Will they be simultaneous? If so how bout using multi threading? It's easy but complicated :) Well f*ck it off don't melange your brain you're just on the correct way continue. i think bubblesorting is also correct for psuedo gods :). i'll pray to them for you :)
Was This Post Helpful? 0
  • +
  • -

#4 gryphin  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 128
  • Joined: 29-October 05

Re: C++ sorting program

Posted 02 February 2006 - 11:22 PM

This is only my second semester of classes. I have only just finished CS1400 intro to programming. This is for CS1410. I do not know how to do multi- anything. I just need to get it to run the 3 different sorting styles so that it shows how long each one takes in order to analyze them and give a brief report on which ones are more efficient and in which circumstances one might be better than another. But I also have to turn in my source code so he can check and make sure I did the source and did not just read about it online.
Was This Post Helpful? 0
  • +
  • -

#5 Voodoo Doll  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 12
  • View blog
  • Posts: 108
  • Joined: 24-January 06

Re: C++ sorting program

Posted 03 February 2006 - 07:29 AM

Quote

I do not know how to do multi- anything.

You shouldn't need to worry about threading for this program. I think dec1pher was reading a bit too much into the description. :) As far as I can tell, the program is done except for filling in the bubbleSort code and writing your own sort. I added the body of that function and the program ran exactly as you're saying it should.

Adding a third sort should be simple as you can just add another function and then copy the relevant part in the driver, changing the names as necessary.
fillArray(numbers, limit);
stime=clock();
mysort(numbers, limit);
cout << " " << setw(10) << double((clock()-stime))/double(1000);


The actual algorithm can be whatever you want, but a selection sort is probably the most intuitive. Just loop through the array backward (backward is faster, but you can do it forward too and look for the smallest). At each number, loop through the rest of the array and find the biggest number, then swap it with the current number. When you get to the beginning, the array will be sorted.
for i = N - 1 downto 0
    biggest = n;

    for j = 0 to N
      if array[i] > array[biggest]
        biggest = i;

    ; Don't swap with yourself :)
    if biggest != i
      swap(a[i], a[biggest]);


For us to really help, you need to be completely honest. Did you write the code you gave us or is it something your professor supplied you with and asked you to modify? If you wrote it yourself, we'll be far less detailed in how we help because the code shows a thorough understanding of the problem at hand as well as a good grounding in basic C++. If you didn't write it, we'll assume that you're not nearly as experienced with C++ as the code suggests. You'll get completely different answers from the two assumptions. ;)
Was This Post Helpful? 0
  • +
  • -

#6 gryphin  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 128
  • Joined: 29-October 05

Re: C++ sorting program

Posted 03 February 2006 - 09:40 AM

Sorry, I thought I said that it was supplied. It is not my code, but we have been give permission to modify it as needed for the assignment.
Was This Post Helpful? 0
  • +
  • -

#7 Voodoo Doll  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 12
  • View blog
  • Posts: 108
  • Joined: 24-January 06

Re: C++ sorting program

Posted 03 February 2006 - 03:59 PM

I can't offer much more help without doing it for you and inviting the wrath of Amadeus. ;) There are four steps to getting the final product, and if you patch together the posts in this thread, you barely have to think to finish each of them. :P

1: Add a function like bubbleSort but with a different name (trivial)
2: Translate the pseudocode in bubbleSort to C++ (easy)
3: Translate the selection sort pseudocode to C++ in the new function (also easy)
4: Copy the part of the driver I specified, but with your new function (trivial)
Was This Post Helpful? 0
  • +
  • -

#8 gryphin  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 128
  • Joined: 29-October 05

Re: C++ sorting program

Posted 03 February 2006 - 11:25 PM

I just do not know how to do if statements or for loops very well, and have never done a sort of any kind. I keep getting these errors what am I doing wrong?

--------------------Configuration: Sorter - Win32 Debug--------------------
Compiling...
sortersource.cpp
C:\Programs\Sorter\sortersource.cpp(90) : error C2065: 'array' : undeclared identifier
C:\Programs\Sorter\sortersource.cpp(90) : error C2109: subscript requires array or pointer type
C:\Programs\Sorter\sortersource.cpp(90) : error C2109: subscript requires array or pointer type
C:\Programs\Sorter\sortersource.cpp(92) : error C2109: subscript requires array or pointer type
C:\Programs\Sorter\sortersource.cpp(92) : error C2109: subscript requires array or pointer type
C:\Programs\Sorter\sortersource.cpp(92) : error C2665: 'swap' : none of the 2 overloads can convert parameter 1 from type 'int'
Error executing cl.exe.

Sorter.exe - 6 error(s), 0 warning(s)

// CS1410 sorting Demo
//   - Bob Nielson


#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>
using namespace std;

const long int NUMBER=50000;   // # of integers to compare quick vs. bubble

// bubblesort function
void bubbleSort(int sortme[NUMBER], long int limit);   // sort
void fillArray(int array[NUMBER], long int limit);     // create the array
void displayArray(int array[NUMBER], long int limit);  // display the first n items
void swap(int& x, int& y);                             // swap x and y

// teacher supplied quicksort
void quickSort(int sortme[NUMBER], long int limit);    // sort
int compare(const void *arg1, const void *arg2);       // compare function

int main()
{
	// create the variables
	int numbers[NUMBER+1];	// array to sort
	long int limit;      // current number to compare
	long int stime;         // start time
	
	// seed the random # generator
	srand(time(0));
	
	// compare bubble times vs. quicksort times from 10,000 to NUMBER, inc by 10,000
	for (limit=10000; limit <= NUMBER; limit=limit+10000)
	{
  cout.precision(4);
  cout.setf(ios::fixed);
  cout << setw(10) << limit;

  // bubble
  fillArray(numbers, limit);
  stime=clock();
  bubbleSort(numbers, limit);
  cout << setw(10) << double((clock()-stime))/double(1000);

  // uncomment this to verify correct sort
   displayArray(numbers,10);

  // quick sort
  fillArray(numbers, limit);
  stime=clock();
  quickSort(numbers, limit);
  cout << " " << setw(10) << double((clock()-stime))/double(1000);
  cout << "\n";

  // uncomment this to verify correct sort
   displayArray(numbers,10);

	}
	
	return 0;
}


// bubblesort function
//    input  -  array to be sorted
//           -  number of items to sort
//    output -  sorted array
void bubbleSort(int sortMe[NUMBER], long int limit)
{

	int i;
	int j;

	// puesdocode for bubble sort
	//
	// begin bubblesort(array,limit)
	//     for i=1 to limit-1
	//        for j=i to limit
	//           if array[i] > array[j]
	//              swap(array[i],array[j]
	//           endif
	//        next j
	//      next i
	// end
	for (i=1; i<=limit-1;)
	{
  for (j=1; j<=limit-1;)
  {
 	 if (array[i] > array[j])
 	 {
    swap(array[i],array[j]);
 	 }
 	 j++;
  }
  i++;
	}
}


// fill array - fills an array with random numbers
//   input    - array to fill
//            - number of items
//   output   - the array filled with random numbers
void fillArray(int array[NUMBER], long int limit)
{
	int i;

	for (i=1; i<limit; i++)
	{
  array[i]=rand();
	}
}

// displayArray  -  displays the first n items in an array
//   input       -  the array
//               -  the number of items to display
//   output      -  displays the first n items in an array
void displayArray(int array[NUMBER], long int limit)
{
	int i;

	for (i=1; i<limit; i++)
	{
  cout << array[i] << " ";
	}
	cout << "\n";
}

// swap          -  swaps items x and y
//   input       -  2 items
//   output      -  the 2 items swapped 
void swap(int& x, int& y)
{
	int temp;

	temp=x;
	x=y;
	y=temp;
}


// quickSort      -  Quick Sort
//    input       -  a array to sort
//                -  # of items to sort
//    output      -  the sorted array
// NOTE:  -  For now disreguard the messy pointers (*)
void quickSort(int sortme[NUMBER], long int limit)
{
	qsort( (void *)sortme, (size_t)limit, sizeof(int *), compare);
}

// compare  - Compares two items
//          - negative if item1 is less than item2
//          - positive if item1 is greather than item2
//          - 0 if item1 == item2
int compare(const void *arg1, const void *arg2)
{
	int value = (*(char**)arg1)-(*(char**)arg2);
	return value;
}

[admin edit]edited to add code tags[\admin edit]

This post has been edited by Amadeus: 04 February 2006 - 08:41 AM

Was This Post Helpful? 0
  • +
  • -

#9 Amadeus  Icon User is offline

  • g+ + -o drink whiskey.cpp
  • member icon

Reputation: 248
  • View blog
  • Posts: 13,507
  • Joined: 12-July 02

Re: C++ sorting program

Posted 04 February 2006 - 08:14 AM

Most of the errors you are receiving are due to the fact that you are trying to access/manipulate a variable named array in your bubbleSort function...but no such variable exists within the scope of that function. I expect you may have wanted to use the array variable sortMe that is being supplied as an argument to the function itself.

To rid your self of those errors, change all references to 'array' to 'sortMe'...although be careful to do that in that function only.
Was This Post Helpful? 0
  • +
  • -

#10 gryphin  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 128
  • Joined: 29-October 05

Re: C++ sorting program

Posted 08 February 2006 - 09:33 PM

Thanks amadeus. I have gotten the program to run those two sorts, but now I need to add another so I am going to try to do that on my own, if I have any trouble I will see about posting another question. Thanks all for the help. Though the program will be late, you were all helpful. I just had too much going on with family to work on it.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1