Selection Sorting--Help Urgently Needed

TetrahedreX · #1 02-May-2005, 08:55

First of all, I'd like to thank those of you who helped me with my last problem.

Unfortunately, I now have a very perplexing problem with a function I am trying to create. The function is supposed to run a selection sort on a two-dimensional array, sorting with the first column (the numbers in the first column are called the department numbers). I have managed to do that part, but the requirements of the program demand that I sort the array again, and this time sort within the department number, but by the numbers in the second column of the array. As an example, this is how it the array should look.

Without sorting:
2 9 389
5 2 083
3 4 382
2 5 732
3 6 892
2 7 297
5 1 874
After the first sort:
2 9 389
2 5 732
2 7 297
3 4 382
3 6 892
5 2 083
5 1 874
After the second sort:
2 5 732
2 7 297
2 9 389
3 4 382
3 6 892
5 1 874
5 2 083

The problem that I have is that I cannot make the second sort work without sorting the entire array by the values in the second column. I need to figure out a way of making it stop when it encounters the end of the 2's, 3's, or 5's, and then on the next pass start with the next section of numbers (that is, within the 2, 3, or 5 section).

The code I am using follows:

CPP / C++ / C Code:

void sortem(arrayType &emp, int elems)
{
        int startScan,
            minIndex0,
            minIndex1,
            minIndex2,
            minValue0,
            minValue1,
            minValue2,
            row,
            col,
            ind,
            departmentnumber = 10;
        short searchNum,
              scanValue,
              incrementer = 0;

        for(startScan = 0; startScan < (elems - 1); startScan++)
        {
                minIndex0 = startScan;
                minValue0 = emp[startScan][0];
                minValue1 = emp[startScan][1];
                minValue2 = emp[startScan][2];

                for(int index = startScan + 1; index < elems; index++)
                {
                        if(emp[index][0] < minValue0)
                        {
                                minValue0 = emp[index][0];
                                minValue1 = emp[index][1];
                                minValue2 = emp[index][2];
                                minIndex0 = index;
                        }
                }
                emp[minIndex0][0] = emp[startScan][0];
                emp[minIndex0][1] = emp[startScan][1];
                emp[minIndex0][2] = emp[startScan][2];
                emp[startScan][0] = minValue0;
                emp[startScan][1] = minValue1;
                emp[startScan][2] = minValue2;
        }
// The above loop works perfectly. The below loop is where I start having 
// problems.
        for(short department = 1; department < departmentnumber; department++)
        {
                searchNum = searchArray(emp, department);
                if(searchNum != -1)
                {
                        while(searchNum == emp[incrementer][0])
                        {
                                incrementer++;
                                for(startScan = 0; startScan < (elems - 1); startScan++)
                                {
                                        minIndex1 = startScan;
                                        minValue0 = emp[startScan][0];
                                        minValue1 = emp[startScan][1];
                                        minValue2 = emp[startScan][2];
                                        if(searchNum != emp[startScan][0])
                                                break;
                                        for(int index = startScan + 1; index < elems; index++)
                                        {
                                                if(emp[index][1] < minValue1)
                                                {
                                                        minValue0 = emp[index][0];
                                                        minValue1 = emp[index][1];
                                                        minValue2 = emp[index][2];
                                                        minIndex1 = index;
                                                }
                                        }
                                        emp[minIndex1][0] = emp[startScan][0];
                                        emp[minIndex1][1] = emp[startScan][1];
                                        emp[minIndex1][2] = emp[startScan][2];
                                        emp[startScan][0] = minValue0;
                                        emp[startScan][1] = minValue1;
                                        emp[startScan][2] = minValue2;
                                }
                        }
                }
        }

}

Any help would be greatly appreciated, as this is due tomorrow.

Stack Overflow · #2 02-May-2005, 12:17

Hello,

I believe I understand what you are asking. I have rewritten the last part of your sorting code that should allow you to accomplish this task. I'll show you the code, and explain it step by step:

CPP / C++ / C Code:

// The above loop works perfectly. The below loop is where I start having 
// problems.

	// FIXED: Our goal is to find the number of sets found of emp[][0]
	// Once we find that, everytime we find a matched set, we sort that.

	// Loop through all elements
	for (int i = 0; i < (elems - 1); i++) {
		// If the next element exists and it equals the previous
		if ((i+1 != (elems - 1)) && emp[i][0] == emp[i+1][0]) {
			// Start scanning at i, and only compare against like indices
			for(startScan = i; startScan < (elems - 1) && emp[startScan][0] == emp[i][0]; startScan++)
			{
				// Selection sort
				minIndex0 = startScan;
				minValue0 = emp[startScan][0];
				minValue1 = emp[startScan][1];
				minValue2 = emp[startScan][2];

				// Make sure we scan only like indices; emp[][0]
				for(int index = startScan + 1; index < (elems - 1) && emp[index][0] == emp[i][0]; index++)
				{
					// Compare [1] to minValue1
					if(emp[index][1] < minValue1)
					{
						minValue0 = emp[index][0];
						minValue1 = emp[index][1];
						minValue2 = emp[index][2];
						minIndex0 = index;
					}
				}
				// Sort
				emp[minIndex0][0] = emp[startScan][0];
				emp[minIndex0][1] = emp[startScan][1];
				emp[minIndex0][2] = emp[startScan][2];
				emp[startScan][0] = minValue0;
				emp[startScan][1] = minValue1;
				emp[startScan][2] = minValue2;
			}
		}
	}

This is the new code that you can replace after the first two commented lines you will find in the sortem function. I just revised those few lines.

The first line of code you will notice a loop that loops through all the elements. This will allow us to sort appropriately. The second line is an if statement. The if statement basically means this:

If the next index does not equal the limit, and this index is equal to the next index

The third line starts the sort scan at i, our current location. From there we increment until the end; but not exactly. We increment until the index of emp is no longer the same to the next. Giving us the advantage of only dealing with that one value.

When the loop starts, we sort the array. I took your first sort code and modified it to sort [1] instead of [0] against minValue1; rather than minValue0.

It's that simple. My output:

CPP / C++ / C Code:

/* Before */
2 9 389
5 2 83
3 4 382
2 5 782
3 6 892
2 7 192
5 1 874

/* After */
2 5 782
2 7 192
2 9 389
3 4 382
3 6 892
5 1 874
5 2 83

If you have further questions, please feel free to ask.

- Stack Overflow

TetrahedreX · #3 03-May-2005, 10:57

Many thanks for the assisstance, Stack. Your code worked perfectly for me.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Free 1st month / Free setup / No credit card needed...Plans start at 4.95	LarryIsaac	Web Hosting Advertisements & Offers	0	11-Oct-2003 14:03
Sorting columns by selection	dean	MySQL / PHP Forum	1	03-Oct-2003 06:29