question with non-comparison sort

[backslashV]

Hello,
I am trying to find the correct index from the countsArray I have. The countsArray (which was populated in the first pass through the students array) includes the counts of 7 schools that were read from the students array (which was sorted by students' ID). What I have to do is do another pass through the original students array and this time when I encounter a student from a specific school put it in the correct place in the tempArray by using cumulative counts from the countsArray. I have a problem finding the correct index when doing the second pass by only using a loop. What I did is use different variables for each school which is certainly not acceptable.

  int schoolToIndex(string school) {
	if (school == "UCB")  return 0;
	if (school == "UCD")  return 1;
	if (school == "UCI")  return 2;
	if (school == "UCLA") return 3;
	if (school == "UCM")  return 4;
	if (school == "UCSD") return 5;
	if (school == "UCSF") return 6;

	cerr << "Unknown school " << school << endl;
	return -1;
}

void sortByGroupById2(Student students[], int len) {

	int countsArray[7] = {0};
	int index;
	Student* tempArray = new Student[len];

        //countsArray holds the # of students from each school
	for (int i = 0; i < len; i++)
		countsArray[schoolToIndex(students[i].getSchool())] += 1;

         int a, b, c; 
         a = b = c = 0;
         for (int i = 0; i < len; i++) {
            switch(schoolToIndex(students[i].getSchool()) {
             case 0 :  tempArray[a] = students[i]; a++; break; //UCB
             case 1 :  tempArray[ b + countsArray[0] ] = students[i]; b++; break;  //UCD
             case 2 :  tempArray[ c + countsArray[0] + countsArray[1] ] = students[i]; c++; break; //UCI
             //And so on.
            }
        }
        //copy the sorted array to the original one
	for (int i = 0; i < len; i++)
		students[i] = tempArray[i];

	delete[] tempArray;
}

[Kevin C]

- Before 'second pass', you need a pass through the countsArray that will calculate the index (of the tempArray) denoting where to place a student from the students array. You can store the results of this pass into a new array named statringIndex, or you can directly change the countsArray.

- for the second pass, you are missing a loop that goes through the 'students' array..

[backslashV]

right, I edited it. now there is a loop that does that. I am having difficulty calculating the index. because the loop that iterates thru the countsArray overrides the previous index and there is no way to find the starting index for the next index in the countsArray.

[Kevin C]

You have three posibiliities there:

1. Change the countsArray so that you insert an element '0' at the beginning

2. It is possible to reorganize the computation so that the 'overwriting problem' doesn't occur. You have to use a temporary variable to store the value of teh countsAttay which is being overwritten.

3. Just store the results in a new array.

[YFGHNG]

As @Kevin C said, you could do what is basically a three-way trade with his #2 suggestion, which you'd also see in sorting algorithms like insertion sort.

You already have your necessary variables; make a temp and assign

a = // certain value;
temp = a;
a = b;
b = temp;

Also +1 for line 6 :)
My alma mater finally getting some recognition.

[Kevin C]

And, by the way, don't mess up the calculation of last count, which should be skipped (you don't need it).

[Kevin C]

And, by the way, it is recommended for beginners that they use std::vector instead of arrays. If your book/course/instructor insists on c-style arrays, he/it is outdated, ad you should question the quality of instructions that you are receiving.

[YFGHNG]

Kevin C wrote:

If your book/course/instructor insists on c-style arrays, he/it is outdated, ad you should question the quality of instructions that you are receiving.

Not necessarily. A professor's job is to teach academics, which means almost anything and everything that's incorporated into their field. Hell, several of my professors have mentioned that they've barely seen recursion used in the actual field, as opposed to lots of file i/o, but that doesn't make the concept any less useless. If you suddenly have to write a custom sorting/searching function for whatever reason your boss wants, wouldn't it be useful to at least know of recursion?

There's also certain things that are easier to do with arrays than with vectors, and if you're dealing with memory constraints (aka space is money) where you know exactly the size of the data you're dealing with, why use dynamic containers versus a set array?

[Kevin C]

There are, certainly, a lot of legitimate uses for c-style arrays.

However, the question here is what a beginner should be using while he is being taught the basics of programming. Using c-style arrays is undoubletdly bad in such a case.

If an instructor decides to explain c-style arrays before std::vector to beginners, it is almost certainly a bad choice. There could be many 'excuses' for such a choice, but none of them really stands up to scrutiny.

Of more concern: if the instructor is making such an obvious and grave error, I would be worried about the quality of his programming instructions in general.

[YFGHNG]

I'll agree that it does really depend on the professor, but how I think of it is they're trying to teach building blocks that YOU have to manipulate vs building blocks that can move by themselves.

Typically (or from what I've seen) people learn arrays, then vectors, then dynamic memory (aka construct a vector class using dynamic allocation of new and delete with arrays).

[Kevin C]

When teaching programming to beginners, the instructions shouls be on a highest level possible. Low-level issues are not for beginners, otherwise people would be beginning programming in assembly language.

Explaining memory issues, pointer issues, copying issues and size-of-array issues should be avoided in order to concentrate on teaching algorithms and imperative and/or functional thinking.

The mentioned issues are best left for much later.

A metaphor: When you are learning driving, it is just a loss of time to be thinking about 4 cylinder engines and otto cycles, even if you are going to be a mechanic.

If people are, at present, mostly starting with the order as you have suggested, then, regrettably, most C++ lessons are outdated, and in such a case it is no wonder why everyone is starting in Python.

[backslashV]

@Kevin C
I now have the startingIndex array as follows:

startingIndex[0] = 0;
for (int i = 1; i < 7; i++)
	startingIndex[i] = startingIndex[i-1] + countsArray[i-1];

The problem is that I should not use different variables for each school in the 2nd pass. I have to somehow use the startingIndex array in the loop. Here is the instruction:
You do another pass through the student array and whenever you encounter a student from a school you add that student to the right portion of the helper array and increment that portion's index.
I can't think of a way to increment a potion in the tempArray without keeping a separate variable for each school.

[Kevin C]

Do you want me to post pseudocode or real solution in C++ code?

Lets start with pseudocode:

for (int i = 0; i < len; i++)
- get school of student[i]
- get starting index from the startingIndex array of given school
- save the student student[i] to the starting index in tempArray
- increase the school starting index in the startingIndex array

This solution does not use separate variables for each school. The startingIndex array contains the indices for all schools.

[backslashV]

thank you

this is what I was looking for:
- increase the school starting index in the startingIndex array

[Kevin C]

Yes, I thought so. Don't worry, you will get the hang of it. You are posting the usual questions.