0

I have a 2D vector of doubles, and I need to sort it using quicksort. However, when I print all the steps, it seems it's not working the way it should. My vector is a global variable, I try to sort each row and print the current vector after each iteration.

vector<vector<double>> vect;
int rows, cols;
void Print2DArray() {
    for (int i = 0;i < vect.size();++i) {
        for (int j = 0;j < vect[i].size();++j) {
            cout << vect[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int partition(int low, int high, int ind) {
    double pivot = vect[ind][high];
    int i = low;
    double tmp;
    for (int j = low;j <= high - 1;++j) {
        if (vect[ind][j] <= pivot) {
            tmp = vect[ind][j];
            vect[ind][j] = vect[ind][i];
            vect[ind][i] = tmp;
            i++;
        }
    }
    tmp = vect[ind][high];
    vect[ind][high] = vect[ind][i];
    vect[ind][i] = tmp;
    Print2DArray();
    return i;
}
void Sort(int low, int high, int ind) {
    if (low < high) {
        int pi = partition(low, high, ind);
        Sort(low, pi - 1, ind);
        Sort(pi + 1, high, ind);
    }
}
void TwoDimSort() {
    for (int i = 0;i < vect.size();++i) {
        Sort(0, vect[i].size() - 1, i);
    }   
    Print2DArray();

}
int main() {
    rows = 3;
    cols = 9;
    srand((unsigned)time(NULL));
    for (int i = 0;i < rows;++i) {
        vector<double> tmp;

        for (int j = 0;j < cols;++j) {
            double num = (rand() % 100) * 0.9;
            if (num > 0.0)
                tmp.push_back(num);
        }
        vect.push_back(tmp);
    }
    Print2DArray();
    TwoDimSort();
    Print2DArray();
    getchar();
    return 0;
}
anastasiia_kos
  • 41
  • 8
  • Is there a reason you're not using the builtin `std::sort`? What input is failing currently and what is the expected output? Thanks for clarifying. – ggorlen Nov 12 '19 at 19:18
  • 2
    How is a 2D vector sorted? What is the sorting criteria? I.e. do you sort just each row, sort sorted vectors according to some criteria, sort all elements without regard to inner vectors (as if it was a one giant vector)? – Yksisarvinen Nov 12 '19 at 19:21
  • 1
    Also, even if this is supposed to be a school exercise, have you tested your `Sort` to see if it successfully sorts a one dimensional vector? If it can't sort a 1D vector, it isn't magically going to sort a 2D vector. – PaulMcKenzie Nov 12 '19 at 19:21
  • @ggorlen It was a task in college to write my own quicksort implementation. – anastasiia_kos Nov 12 '19 at 19:37
  • @Yksisarvinen Each row is sorted separately. – anastasiia_kos Nov 12 '19 at 19:38
  • @anastasiia_kos [How to implement sorting algorithms …](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c) – PaulMcKenzie Nov 12 '19 at 20:31

1 Answers1

0

I think you could just use the following implementation.

void swap(double array[], int i, int j) {
  auto h = array[i];
  array[i] = array[j];
  array[j] = h;
}

int partition(double array[], int low, int high) {
  //  Assign the last element to the pivot element
  int pivot = array[high];
  //  Index of smaller element
  int lowIndex = (low - 1);
  //  Iterate from lowest to highest element
  for (int j = low; j <= high - 1; j++) {

    // Swap elements if j-th element is smaller than the pivot element
    if (array[j] < pivot || array[j] == pivot) {
      lowIndex++;
      swap(array, lowIndex, j);
    }
  }
  swap(array, lowIndex + 1, high);
  return (lowIndex + 1);
}

double *quickSort(double array[], int lo, int hi) {
  if (lo < hi) {
    int pi = partition(array, lo, hi);
    //  Recursively sort smaller half of the list
    quickSort(array, lo, pi - 1);
    //  Recursively sort higher half of the list
    quickSort(array, pi + 1, hi);
  }
  //  Return sorted list
  return array;
}

Global variables are bad practice in this case!

void Print2DArray(std::vector<std::vector<double>> vect) {
    for (int i = 0;i < vect.size();++i) {
        for (int j = 0;j < vect.at(i).size();++j) {
            std::cout << vecta.at(i).at(j) << " ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

void TwoDimSort(std::vector<std::vector<double>> vect) {
    for (int i = 0; i < vect.size(); ++i) {
        // Print the sorted row
        print(quickSort(0, vect.at(i).size() - 1, i));
    }   
}

void print(std::vector<double> v){
    for( auto d : v){
        std::cout << d << " ";    
    }
    std::cout << std::endl;
}

You should consider using this implementation of the print-function an quickSort. Subsequently I would recommend you to use vector::at instead of [], due to range checking reasons.

SchnJulian
  • 182
  • 1
  • 11