Sorting an Array

[SakuraPink]

hi everyone,

I need to write a piece of code that sort an array of double values named distance in the following code. The counter i is the index for another array as well therefore I don't want to change the order of the array. I got hint from this post:
http://www.daniweb.com/software-development/cpp/threads/351064
but my code still doesn't work.

#include <iostream>
#include <fstream>
#include <strstream>
#include <math.h>
#include <stdio.h>

using namespace std;

int main()
{
  int L = 10;
  int size = L*L*L;
  int x,y,z=0;
  double distance[size];
  int idx[size];
  int j = 0;
  int i = 0;
  int swp;

  for ( x = 0 ; x<L ; x++){
    for ( y = 0 ; y<L ; y++){
      for ( z= 0 ; z<L ; z++){

        distance[j] = sqrt ((x-(L-1)/2)*(x-(L-1)/2)+(y-(L-1)/2)*(y-(L-1)/2)+(z-(L-1)/2)*(z-(L-1)/2));
        //cout << distance[j] << "  " << j << endl;
        j +=1;
        }}}

  // cout << j << endl;

  for ( i = 0; i < j; i++) {
    idx[i]=i;
    //cout << idx[i];
  }

  for ( i = 0; i < j-1; i++) {
    if (distance[idx[i]] > distance[idx[i + 1]]) {
      swp = idx[i];
      idx[i] = idx[i + 1];
      idx[i + 1] = swp;
    }
    //    cout << idx[i]<< endl;
  }

  for ( i = 0; i < j-1; i++) {
      cout << distance[idx[i]] << endl;
  }
}

Any suggestion would be greatly appreciated.

[Nick Evan]

Is this an assignment of some sort? If not: I would recommend you use a vector instead of an Array, especially if you want the size to be dynamic as this piece of code suggests:

int L = 10;
int size = L*L*L;
int x,y,z=0;
double distance[size]; // Uh-oh, very bad!!

That way you can just use std::sort to sort everything out.

If this is an assignment, tell us what sorting-method you trying to create, because your code doesn't really make any sense. It sorta looks like a bubble-sort with an overkill-loop?

[mike_2000_17]

You bubble sort method is missing one nested loop level.

The loop that you have will have the result of making the largest distance to end up at the end of the array (and thus the name "bubble" sort). But it _only_ takes the largest value to the end, all the other values are not sorted. You have to repeat the process as many times as there are values in the array. And each time you do the bubbling loop, you don't have to go all the way to the end, only as far as there are unsorted values left. So, you can do:

for ( j = size; j > 1; --j) {
    for ( i = 0; i < j-1; i++) {
      if (distance[idx[i]] > distance[idx[i + 1]]) {
        swp = idx[i];
        idx[i] = idx[i + 1];
        idx[i + 1] = swp;
      }
      //    cout << idx[i]<< endl;
    }
  }

This is why the bubble sort method has O(N^2) complexity, because it requires two nested loops proportional to N to do it.

If this is not an assignment problem, use the std::sort method instead.

[SakuraPink]

Thanks guys for your responds.
Mike, using your help I was able to solve the problem.
About using std::sort, I thought that I can not use it or at least I don't know how it can help me solve this problem as I need to just sort the indices idx in my code.
If you wonder My whole code is the following, in which Density.xml is a file with 3 columns of data in L*L*L lines:

#include <iostream>
#include <fstream>
#include <strstream>
#include <math.h>
#include <stdio.h>

using namespace std;

int main()
{
  int L = 10;
  int size = L*L*L;
  int x,y,z=0;
  ifstream ifs("Density.xml");
  string sentence;
  string temp;
  string temp1[size];
  size_t pos,pos1;
  double distance[size];
  int idx[size];
  int j,i = 0;
  int swp;

  for ( x = 0 ; x<L ; x++){
    for ( y = 0 ; y<L ; y++){
      for ( z= 0 ; z<L ; z++){

        distance[j] = sqrt ((x-(L-1)/2)*(x-(L-1)/2)+(y-(L-1)/2)*(y-(L-1)/2)+(z-(L-1)/2)*(z-(L-1)/2));
        cout << distance[j] << "  " << j << endl;
        j +=1;
}}}
  cout << j << endl;
  for ( i = 0; i < j; i++) {
    idx[i]=i;
  }
  for ( j = size; j > 1; --j) {
    for ( i = 0; i < j; i++) {
      if (distance[idx[i]] > distance[idx[i + 1]]) {
        swp = idx[i];
        idx[i] = idx[i + 1];
        idx[i + 1] = swp;
      }
      //      cout << idx[i]<< endl;
    }
  }
  j=0;
  while(std::getline(ifs,sentence))
    {
      string tmp(sentence);
      pos = tmp.find_first_of(")", 0);
      tmp.erase(0, pos+2 );
      pos1 = tmp.find_first_of("\n", 0);
      temp1[j] = tmp.substr(0, pos1 );
      //      cout << distance[j] << "  " << temp1[j] << endl;
      j+=1;
    }
  for ( i = 0; i < j; i++) {
    cout << distance[idx[i]] << "  " << temp1[idx[i]] << endl;
  }
}

So I need to know the order of indices to be able to print distance and temp1 at the end. Is it possible to use std::sort in this case?

[mike_2000_17]

Yes, the std::sort function has a version that takes an extra parameter called "compare" which is used as a comparison function object (functor). The comparison function should be callable with two parameters of the type of the array that is being sorted and should return a bool value that should be true if the first parameter-value should be before the second one in the sorted list (i.e. the default is the less-than operator). So, you could define a functor for the comparison as follows:

struct compare_distances {
  double* dist_array;
  compare_distances(double* aDistArray) : dist_array(aDistArray) { };
  bool operator() (int i, int j) { 
    return (dist_array[i] < dist_array[j]);
  };
};

Then, you can use the std::sort function like so:

std::sort(idx,  //pointer to the first element of the array.
            idx + size, //pointer to the one-passed-last element of array.
            compare_distances(distance)); //comparison functor.

[SakuraPink]

Well Thanks a lot again. I will give it a try.