Быстрая сортировка

Задача: Характеристикой столбца целочисленной матрицы назовем сумму
модулей его отрицательных нечетных элементов. Переставляя столбцы заданной
матрицы, расположить их в соответствии с ростом характеристик.
Проблема: преподаватель сказал, что можно использовать библиотечную быструю сортировку, но это задача нетривиальная, и проще будет самому (например пузырьковую сортировку). Написать не проблема. Просто интересно стало, что это за нетривиальная задача такая (люблю я их).
Подскажите пожалуйста, если не сложно, хотя бы с чего начать, какие библиотеки подключать...
Просто С++ изучаю третий месяц, еще толком не разобрался "че по чем".
Задачу я решил. Осталась только сортировка. Решения во вложениях.
Прикреплённый файлmatrix.cpp (1,34 Кбайт, скачиваний: 350)
Прикреплённый файлmatrix.h (373 байт, скачиваний: 192)
Прикреплённый файлtask_20.cpp (339 байт, скачиваний: 221)

Добавлено 21.11.12, 14:35
вроде так

Сообщение отредактировано: kotmatroskin55 - 21.11.12, 14:35

Например qsort() использовать.
Транспонировать матрицу, в качестве размера элемента для функций указывать размер строки, написать свою функцию сравнения для qsort() чтоб вычисляла и сравнивала нужную характеристику, отсортировать всё при помощи qsort() и снова транспонировать матрицу.
Как-то так.
Ну или если на плюсах, то на std::sort аналогичное сделать.

Сообщение отредактировано: cppasm - 21.11.12, 14:48

А КАК QSORT() использовать, какие параметры передаются. как она вообще работает?
Если можно поподробнее. Я просто пытаюсь понять что и как.
Функция, вычисляющая нужную характеристику написана. Вот она:

int charact(int** matrix, int size, int columnnum)
{
    int key = 0; //сумма   модулей  отрицательных нечетных элементов столбца
    for (int i = 0; i < size; i++)
    {
        if ((matrix[columnnum][i] < 0) && (matrix[columnnum] [i] %2 != 0))
            key += abs(matrix[columnnum][i]);      
    }
    return key;
}

А дальше что? Где можно посмотреть исходник qsort()?

Сообщение отредактировано: kotmatroskin55 - 21.11.12, 15:39

http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/

КОРОЧЕ РЕШИЛ НЕ ПАРИТЬСЯ С QSORT. СДЕЛАЛ ПУЗЫРЬКОВУЮ. ВОТ ГОТОВЫЙ ПРОЕКТ, МОЖЕТ КОМУ СГОДИТСЯ.
Прикреплённый файл2020.ZIP (2,35 Кбайт, скачиваний: 179)

kotmatroskin55, можете немножко объяснить этот фрагмент? если не отрицательное и при делении элемента в модуле на 2 должна получится единица (я понимаю эту часть кода, но не понимаю, почему именно такое условие). и зачем делается два условия и, соответственно, две переменные, которые дальше сравниваются? уделите, пожалуйста, пару минут

...

if(matrixA[i][j1]<0 && Math.abs(matrixA[i][j1])%2==1)
t+=Math.abs(matrixA[i][j1]);
if(matrixA[i][j1+1]<0 && Math.abs(matrixA[i][j1+1])%2==1)
t1+=Math.abs(matrixA[i][j1+1]);}

if(t>t1)
for(int i=0; i<3; i++)
{
t=matrixA[i][j1];
matrixA[i][j1]=matrixA[i][j1+1];
matrixA[i][j1+1]=t;
}

...


// ой, я, кажется, разобралась!

Сообщение отредактировано: madam psevdo - 21.05.17, 16:33

Не прошло и пять лет Решил немного освежить знания STL.

Пример синтетическо-академический:

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <numeric>
#include <vector>
 
using Vector = std::vector<int>;
using Matrix = std::vector<Vector>;
 
int main() {
  // задаем матрицу построчно
  Matrix M = {
    { 0, 1, 2, 3, 4},
    { 0, 0, 0, 0, 0},
    {-1, 0, 7,-2, 0},
    { 0,-1, 0, 0, 0},
    { 2, 2,-7, 0,-5},
  };
  // выводим до сортировки
  std::cout << "До сортировки: " << std::endl;
  for(const auto &i:M) {
    for(const auto &j:i) std::cout << std::setw(3) << j << " ";
    std::cout << std::endl;
  }
  // если матрица задана построчно - сделаем временную (заданную "постолбцово")
  Matrix T;
  for(auto i=0; i<M.size(); i++) T.push_back(Vector(M.size(),0));
  for(auto i=0; i<M.size(); i++) for(auto j=0; j<M.size(); j++) T[i][j]=M[j][i];
  // сортируем
  std::qsort(&T.front(),M.size(),sizeof(Vector),[](const void* A, const void* B) {
    int Sum1 = std::accumulate(static_cast<const Vector*>(A)->begin(),
                               static_cast<const Vector*>(A)->end(), 0,
                               [](int r, int a) {
                                  return (a<0 && std::abs(a)%2!=0) ? r+std::abs(a):a;
                               });
    int Sum2 = std::accumulate(static_cast<const Vector*>(B)->begin(),
                               static_cast<const Vector*>(B)->end(), 0,
                               [](int r, int a) {
                                  return (a<0 && std::abs(a)%2!=0) ? r+std::abs(a):a;
                               });                          
    if(Sum1>Sum2) return -1;
    if(Sum1<Sum2) return 1;
    return 0;
  });
  // заполняем исходную матрицу значениями из временной
  for(auto i=0; i<M.size(); i++) for(auto j=0; j<M.size(); j++) M[i][j]=T[j][i];
  // выводим после сортировки
  std::cout << "После сортировки: " << std::endl;
  for(const auto &i:M) {
    for(const auto &j:i) std::cout << std::setw(3) << j << " ";
    std::cout << std::endl;
  }
  return 0;
}