Multi-Dimensional Array Sorting

[mrchaos]

I'm tryring to sort a [300][2] array based on the data held in positon 2 of the array.

This is the routine I have come up with but it's a no go. Any help would be great.

for (i=1;i>=MAXARRAY-1;i++) {
          for(i2=0;i2<MAXARRAY;i2++) {
               if(iTF[i2][1] > iTF[i2 + 1][1]) {
                    iTemp = iTF[i2][0];
                    iTemp1 = iTF[i2][1];
                    iTF[i2][0] = iTF[i2 + 1][0];
                    iTF[i2][1] = iTF[i2 + 1][1];
                    iTF[i2 + 1][0] = iTemp;
                    iTF[i2 + 1][1] = iTemp1;
               }
          }
} 

[CornedBee]

I assume this array is of type int
C:

#include <stdlib.h>

intl qshelp(void *p1, void *p2)
{
  int i1 = *(((int*)p1)+1);
  int i2 = *(((int*)p2)+1);
  if(i1 < i2) return -1;
  if(i1 == i2) return 0;
  return 1;
}

// sort the array:
qsort(array, 300, qshelp);

C++:

#include <algorithm>
using std::sort;

class pred_s2dar {
  bool operator()(int *ar1, int*ar2) {
    return (ar1[1] < ar2[1]);
  }
};

// sort the array:
sort(array, array+300, pred_s2dar());

The advantage is that both methods use the quicksort algorithm, which is much faster than bubble sort.

[mrchaos]

That's all fine and dandy, but I want to know what is actually wrong with my bubble sort code. My program win't even go into the routine, it first line is wrong in someway i believe.

Thx,
Steve

[CornedBee]

i=1;i>=MAXARRAY-1;i++

You need a < here.

And C/C++ arrays begin idexing with 0, so you have to change your code to watch for that.

[parksie]

I thought std::sort used a merge sort?

[CornedBee]

I don't know. MSDN says nothing about theirs and I don't have access to a C++ standard. It might depend on the implementation. VC++7's sort takes O(N log N), maybe you can figure it out...

[jim mcnamara]

// sort the array:
qsort(array, 300,sizeof(int), qshelp);

qsort has 4 arguments.

[jim mcnamara]

Oh FWIW - consider using builtin routines for sorting. Like the ones CB mentioned.

Bubble sorts are great for classwork, but get you nowhere in the real world. We have to sort our 'ad hoc' data extractions that routinely have 30-60 million records in each of 12 files. If we used the bubble sort, the ad hoc for January 2002 would just now be finishing....



We use the HPUX sort package. Even then, it takes quite a while and uses 20GB+ of disk. When we have yearend files, they get sorted on the mainframe.

[CornedBee]

Yes, bubble sort is very easy to understand and implement, but it has the worst performance of all sorting algorithms I know.

[parksie]

It beats quick sort on mostly-sorted data. For example, you have a dataset that's unsorted, use quick sort or something to get it into order, then you can use a bubble sort once you've made any changes you want to keep it sorted.

[Tec-Nico]

You are right, Parksie... It also depends on how many items you have to sort. That is why there is even the knut rule for the Shell Sort.

Anyway... I was here again searching for code for translating the Automaton program. (Yes, I have translated the class State so far and now I am translating the class Automaton) and I need to sort a vector of strings. And yes, I found "algorithm.h" but the example i found was using the size of the string to sort it. How can I sort it alphabetically?

I tried the following:

#include <string>
#include <vector>
#include <algorithm>

// compare strings by length, descending order
bool  compare(string const& x, string const& y)  {
    return x < y; //x.size() > y.size();
}

void SortVector(vector<string> V){
    sort(V.begin(), V.end(), compare);
} 

What am I doing wrong? I don't want to program the Flagged-Bubble Sort... I already programmed MID, InStr and all those functions I would use on VB...

[Tec-Nico]

Oops.. I found one post by Parksie that showed me that...

But now my question is... Why if I make it a procedure it won't sort it but when I do it just like that it sorts it?

Example:

#include <string>
#include <vector>
#include <algorithm>

void SortVector(vector<string> V){
    sort(V.begin(), V.end());
}

void main(){
    vector<string> States;
    States.insert(States.end(), "s5");
    States.insert(States.end(), "s4");
    States.insert(States.end(), "s3");
    States.insert(States.end(), "s2");
    //This is an example, so don't think I had it this way.
   //I just did not want to add the GetArrows code.
   SortVector(States); //This won't sort it
   sort(States.begin(), States.end()); //This will work
} 

So why doesn't it work if it is called like I did? I mean, it is easier for me to just give the vector I want to sort it and then sort it with a procedure like that. But I had to do it the other way... I am just curious why wouldn't this approach work...

PS: Which is the most comfortable way for you guys to see the code?

[parksie]

Look very carefully at your argument list for SortVector

Also, why add another function just to "rename" sort() ?

[CornedBee]

Actually, less<> with strings should sort lexicographically...

[Tec-Nico]

True, Parksie it should be:

void SortVector(std::vector<string> V){

    sort(V.begin(), V.end());

}

But I am not using it... Thank you anyway..

[parksie]

Heh, nope. Still wrong. Try:

void SortVector(std::vector<string> &V){

    sort(V.begin(), V.end());

}

[Tec-Nico]

I will, but why...? Is it like "ByRef" and "ByVal" that is in VB?

[parksie]

Basically, yes.

The & tells it to pass that argument by reference, hence when you do something to V, it acts on the original V. If you had it as const, then you would not be able to change it, and the effect would be of pass-by-value, except without the copying overhead (hence why const references are used so much in C++).

You can use * to pass by pointer (references do not exist in C, so pointers are the only way to achieve this same effect). This requires "dereferencing" that pointer before use, with the * operator that I'm sure you're familiar with. You can use const in C++ with this as well.

No modifiers passes by value, and will copy the entire class/structure/type before the function starts. Alterations are permitted, but are fairly useless most of the time because they don't affect the caller.

[Tec-Nico]

Oh... Well, thank you.

Now I understand. I thought something like that might be happening. Please be patient to me... My C++ teacher was an ass and he never taught us anything. So all I know is because of practice. Not like on VB that I could take the book and grasp it quickly (It is because I used to work with Basic when I was in junior High and they did not teach us C nor C++ )

[WiKiDJeFF]

what does lexicographically mean?

[parksie]

Dictionary-style, basically.

Lexicon == dictionary. The 'lex' prefix is what determines it, I think.

[CornedBee]

latin lex, legis (f.)
1) a set form of words , contract, covenant, agreement
2) a law, rule