Сортировка двумерного массива

dizzel
Offline
Зарегистрирован: 21.03.2016

Дан массив [28][5], он состоит из целых чисел.

Например

0,3,9,10,1
1,5,10,10,1
1,5,15,0,0
0,6,3,30,0
2,0,21,20,1

Чтобы понять что мне нужно легче объяснить что эти числа из себя представляют. Сортировать нужно порядок следования строк, внутри этих строк ничего менять нельзя.

Результат сортировки положить в такой же массив.

Первое число это номер от 0 до 3 и они могут повторятся (в этом столбце). Первая сортировка это сортировка строк так чтобы строки с меньшим числом оказались наверху. Возрастание.

Следущие 3 числа это день (от 0 до 6), час (от 0 до 23), минута (от 0 до 59). Последняя цифра не важна.

Суть такова что строки нужно выстроить в последовательности по возрастанию сначала по первому столбцу. На основе полученных результатов выполнить сортировку по возрастанию для второго столбца, потом так же для третьего и четвертого. Самое важное условие - для каждой следующей сортировки сохранять порядок результатов предыдущей.

Короче нужно условно выражаясь выстроить строки в порядке хода времени для каждой из цифр первого столбца.

Скажите это вообще реально? Если кто-то готов взяться то напишите пожалуйста мне на почту wild_z@mail.ru

dizzel
Offline
Зарегистрирован: 21.03.2016

Ах да. Среда - Ардуино ИДЕ. Если это важно.

brokly
brokly аватар
Offline
Зарегистрирован: 08.02.2014

Бюджет ?

mixail844
Offline
Зарегистрирован: 30.04.2012
да все можно , не до конца ясно что надо .
как будет выглядеть отсортированный по вашим критериям приведенный вами массив ? 
 
upd : 

0,3,9,10,1

0,6,3,30,0

1,5,10,10,1

1,5,15,0,0

2,0,21,20,1

вот так ? 

 

Бармалей
Бармалей аватар
Offline
Зарегистрирован: 23.09.2019

Курсовая? 

b707
Offline
Зарегистрирован: 26.05.2017

условно говоря , каждая строчка - отметка времени(timestamp)

первая цифра месяц, вторая день, третья час. четвертая минута.

Переводим все четыре цифры в минуты - в итоге  многомерная сортировка вырождается в одномерную по одному параметру. Задача элементарная. алгоритм сортировки можно взять любой из учебника.

Дизель, с вас 300 руб за разработку идеи.

wdrakula
wdrakula аватар
Offline
Зарегистрирован: 15.03.2016

кончай говниться, коллеги! Завтра протрезвею и днем накатаю сюда. Стыдно за сортировку бабки брать! Черти в аду котел заведут с несортированными дровами!

b707
Offline
Зарегистрирован: 26.05.2017

wdrakula пишет:

кончай говниться, коллеги! Завтра протрезвею и днем накатаю сюда.

ты опоздал, я уже все решил. А примерчик из учебника на сортировку пузырьком ТС и сам найдет

dizzel
Offline
Зарегистрирован: 21.03.2016

Да, спасибо, мне тоже подсказали перевести время в секунды. А это все упрощает. Сорян, что потратил ваше время. Задача оказывается была проще чем я думал.

brokly
brokly аватар
Offline
Зарегистрирован: 08.02.2014
#define SIZE 5

uint8_t in[][SIZE]={
  {0,3,9,10,1},
  {1,5,10,10,1},
  {1,5,15,0,0},
  {0,6,3,30,0},
  {2,0,21,20,1},
};

uint8_t out[5][SIZE]={0};

void printMass(uint8_t mass[][SIZE],uint8_t size){
   for(uint8_t i=0;i<size;i++){
      Serial.print(mass[i][0]);
      for(uint8_t j=1;j<SIZE;j++){
         Serial.print(',');
         Serial.print(mass[i][j]);     
      }
      Serial.println();
   }
}

// перевод времени в минуты
uint32_t getTime(uint8_t pr, uint8_t d, uint8_t h, uint8_t m){
  return (44640UL*pr)+(1440*d)+(60*h)+m;
}

void setup() {
  Serial.begin(115200);
  Serial.println("IN:");
  printMass(in,SIZE);
  uint8_t p[SIZE]={0}; // признак сортировки
  for(uint8_t i=0;i<SIZE;i++){ // подготовка данных
     p[i]=i;
  }
  // Сортировка массива пузырьком
  for (uint8_t i = 0; i < SIZE - 1; i++) {
     for (uint8_t j = 0; j < SIZE - i - 1; j++) {
        if (getTime(in[p[j]][0],in[p[j]][1],in[p[j]][2],in[p[j]][3]) > 
            getTime(in[p[j+1]][0],in[p[j+1]][1],in[p[j+1]][2],in[p[j+1]][3])) {
            p[j]^= p[j + 1]; p[j+1]^= p[j]; p[j]^= p[j + 1];
        }
     }
  }
  // заполняем выходной массив
  for(uint8_t i=0;i<SIZE; i++){
     memcpy(out[i],in[p[i]],sizeof(in[0]));
  }
  Serial.println("OUT:");
  printMass(out,SIZE);
}

void loop() {
   //...
}

 

IN:
0,3,9,10,1
1,5,10,10,1
1,5,15,0,0
0,6,3,30,0
2,0,21,20,1
OUT:
0,3,9,10,1
0,6,3,30,0
1,5,10,10,1
1,5,15,0,0
2,0,21,20,1
 

b707 пишет:

Дизель, с вас 300 руб за разработку идеи.

Тебе придется поделиться со мной. Как вы много написали пока я скетч рисовал.

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

а чо, нынче qsort() насовсем отменили?

Бармалей
Бармалей аватар
Offline
Зарегистрирован: 23.09.2019

qsort памяти жреть очень много, эта простейшая программа вешает 4к, на Атмеге8 шибко и не применишь, :-)

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

Убейбох, не вижу в первом сапщении ни одного упоминания Atmega8

Бармалей
Бармалей аватар
Offline
Зарегистрирован: 23.09.2019

тагда применишь. Но всё равно жрёт многа

Kakmyc
Offline
Зарегистрирован: 15.01.2018

Учитывая, что результаты будут уходить в другой массив, все делается элементарно с помощью memcpy()

Бармалей
Бармалей аватар
Offline
Зарегистрирован: 23.09.2019

функция memcpy() не проверяет соответствие размера выходного буфера количеству копируемых байт. В результате совершается достаточно много ошибок, способных привести к переполнению буфера.

Kakmyc
Offline
Зарегистрирован: 15.01.2018

Бармалей пишет:

функция memcpy() не проверяет соответствие размера выходного буфера количеству копируемых байт. В результате совершается достаточно много ошибок, способных привести к переполнению буфера.

В данном случае размеры массива заданы конкретные.

rkit
Онлайн
Зарегистрирован: 23.11.2016

Бармалей пишет:

qsort памяти жреть очень много

Чушь

dizzel
Offline
Зарегистрирован: 21.03.2016

Спасибо, brokly

Я решил упростить себе задачу и просто ввел еще один элемент массива, в который будет записываться сумма секунд. По ней и будет происходить сортировка. Это слегка ускорит процесс, потому что не потребуется столько операций перемножения.

Kakmyc
Offline
Зарегистрирован: 15.01.2018

dizzel пишет:

Спасибо, brokly

Я решил упростить себе задачу и просто ввел еще один элемент массива, в который будет записываться сумма секунд. По ней и будет происходить сортировка. Это слегка ускорит процесс, потому что не потребуется столько операций перемножения.

Можно ещё проще сделать.
Взять текущее время и включать реле по модулю.

currentTime%setTime<60?digitalWrite(RELE2,HIGH):digitalWtite(RELE2,LOW);

Где currentTime время UT в секундах, а setTime- время в секундах когда нужно включать

dizzel
Offline
Зарегистрирован: 21.03.2016

Я делаю это по расписанию. Что собственно и представляет из себя этот массив.

Kakmyc
Offline
Зарегистрирован: 15.01.2018

dizzel пишет:

Я делаю это по расписанию. Что собственно и представляет из себя этот массив.

Так и будет по расписанию:
for(int i=0;i< array_size;i++){
А тут все тоже самое, только в качестве setTime берется член массива.
}

dizzel
Offline
Зарегистрирован: 21.03.2016

Сортировка мне нужна для отображения ее на web интерфейсе. Для наглядности.

renoshnik
Offline
Зарегистрирован: 11.04.2013

dizzel пишет:

Дан массив [28][5], он состоит из целых чисел.

Например

0,3,9,10,1
1,5,10,10,1
1,5,15,0,0
0,6,3,30,0
2,0,21,20,1

Чтобы понять что мне нужно легче объяснить что эти числа из себя представляют. Сортировать нужно порядок следования строк, внутри этих строк ничего менять нельзя.

Результат сортировки положить в такой же массив.

Первое число это номер от 0 до 3 и они могут повторятся (в этом столбце). Первая сортировка это сортировка строк так чтобы строки с меньшим числом оказались наверху. Возрастание.

Следущие 3 числа это день (от 0 до 6), час (от 0 до 23), минута (от 0 до 59). Последняя цифра не важна.

Суть такова что строки нужно выстроить в последовательности по возрастанию сначала по первому столбцу. На основе полученных результатов выполнить сортировку по возрастанию для второго столбца, потом так же для третьего и четвертого. Самое важное условие - для каждой следующей сортировки сохранять порядок результатов предыдущей.**

Короче нужно условно выражаясь выстроить строки в порядке хода времени для каждой из цифр первого столбца. ***

Скажите это вообще реально? Если кто-то готов взяться то напишите пожалуйста мне на почту wild_z@mail.ru

** По моему после первой сортировки все последующие уже не актуальны...

*** Если после первой сортировки, последующие проводить отдельно в каждом полученном блоке, то актуальным будет только первый результат.

 

 

Kakmyc
Offline
Зарегистрирован: 15.01.2018

renoshnik пишет:

** По моему после первой сортировки все последующие уже не актуальны...

*** Если после первой сортировки, последующие проводить отдельно в каждом полученном блоке, то актуальным будет только первый результат.

 

 

Первая сортировка, массивов по значению первой ячейки.
Вторая сортировка по значению второй ячейки, но только тех значений, у которых первый член равен самому мелкому. И тд

brokly
brokly аватар
Offline
Зарегистрирован: 08.02.2014

DetSimen пишет:

а чо, нынче qsort() насовсем отменили?

А оно упростило бы нам жизнь ? 

dizzel
Offline
Зарегистрирован: 21.03.2016

brokly пишет:

IN:
0,3,9,10,1
1,5,10,10,1
1,5,15,0,0
0,6,3,30,0
2,0,21,20,1
OUT:
0,3,9,10,1
0,6,3,30,0
1,5,10,10,1
1,5,15,0,0
2,0,21,20,1

Кстати не правильно отсортировалось. По первому числу сортировка не важна. Главное 3 числа по середине.

Да и упростим задачку. Просто добавим в конец каждой строки еще одно число sum = дни * 1440 + часы * 60 + минуты и будем сортировать строчки по нему.

b707
Offline
Зарегистрирован: 26.05.2017

dizzel пишет:

Да и упростим задачку. Просто добавим в конец каждой строки еще одно число sum = дни * 1440 + часы * 60 + минуты и будем сортировать строчки по нему.

это это заказ - то озвучьте цену. А если нет - то вам уже столько советов надавали. что могли бы и сами сделать.

Еще одна переменная, на мой взгляд. нафик не нужна. Можно вычислять в процессе, контроллеру все равно заняться нечем

И, кстати, где наш с брокли гонорар?

Kakmyc
Offline
Зарегистрирован: 15.01.2018

А лучше поставь библиотеку Time.h, переведи все в UnixTime и работай с ним

brokly
brokly аватар
Offline
Зарегистрирован: 08.02.2014

dizzel пишет:

Первое число это номер от 0 до 3 и они могут повторятся (в этом столбце). Первая сортировка это сортировка строк так чтобы строки с меньшим числом оказались наверху. Возрастание.

А, понял, не вопрос.

#define SIZE 5

uint8_t in[][SIZE]={
  {0,3,9,10,1},
  {1,5,10,10,1},
  {1,5,15,0,0},
  {0,6,3,30,0},
  {2,0,21,20,1},
};

uint8_t out[5][SIZE]={0};

void printMass(uint8_t mass[][SIZE],uint8_t size){
   for(uint8_t i=0;i<size;i++){
      Serial.print(mass[i][0]);
      for(uint8_t j=1;j<SIZE;j++){
         Serial.print(',');
         Serial.print(mass[i][j]);     
      }
      Serial.println();
   }
}

// перевод времени в минуты
uint32_t getTime(uint8_t pr, uint8_t d, uint8_t h, uint8_t m){
  return (44640UL*(31-pr))+(1440*d)+(60*h)+m;
}

void setup() {
  Serial.begin(115200);
  Serial.println("IN:");
  printMass(in,SIZE);
  uint8_t p[SIZE]={0}; // признак сортировки
  for(uint8_t i=0;i<SIZE;i++){ // подготовка данных
     p[i]=i;
  }
  // Сортировка массива пузырьком
  for (uint8_t i = 0; i < SIZE - 1; i++) {
     for (uint8_t j = 0; j < SIZE - i - 1; j++) {
        if (getTime(in[p[j]][0],in[p[j]][1],in[p[j]][2],in[p[j]][3]) > 
            getTime(in[p[j+1]][0],in[p[j+1]][1],in[p[j+1]][2],in[p[j+1]][3])) {
            p[j]^= p[j + 1]; p[j+1]^= p[j]; p[j]^= p[j + 1];
        }
     }
  }
  // заполняем выходной массив
  for(uint8_t i=0;i<SIZE; i++){
     memcpy(out[i],in[p[i]],sizeof(in[0]));
  }
  Serial.println("OUT:");
  printMass(out,SIZE);
}

void loop() {
   //...
}
IN:
0,3,9,10,1
1,5,10,10,1
1,5,15,0,0
0,6,3,30,0
2,0,21,20,1
OUT:
2,0,21,20,1
1,5,10,10,1
1,5,15,0,0
0,3,9,10,1
0,6,3,30,0
 

Как говориться "найди три отличия".

 

b707
Offline
Зарегистрирован: 26.05.2017

Kakmyc пишет:
А лучше поставь библиотеку Time.h, переведи все в UnixTime и работай с ним

и перевести надо еще до вкладывания в массив, хранить в нем часы и минуты отдельно совершенно лишнее

brokly
brokly аватар
Offline
Зарегистрирован: 08.02.2014

Он хочет в веб интерфейсе это показывать. Поэтому задача не облегчается, данные все равно туда сюда конвертить.  И память не экономится. Так что наверное большого смысла нет.

dizzel
Offline
Зарегистрирован: 21.03.2016

brokly Извиняюсь, за то что криво написал. Так получается что все ок.

b707 Я знаю, что уже охамел. =) Но это я уже побольшей части так для себя пишу ....в космос.

b707
Offline
Зарегистрирован: 26.05.2017

brokly пишет:

dizzel пишет:

чтобы строки с меньшим числом оказались наверху.

А, понял, не вопрос.


IN:
0,3,9,10,1
1,5,10,10,1
1,5,15,0,0
0,6,3,30,0
2,0,21,20,1
OUT:
2,0,21,20,1
1,5,10,10,1
1,5,15,0,0
0,3,9,10,1
0,6,3,30,0
 

что-то ты как-то не так понял....

brokly
brokly аватар
Offline
Зарегистрирован: 08.02.2014

b707 пишет:

что-то ты как-то не так понял....

Да нет, как раз задача мутно поставлена, он хочет, что бы сортировка по первой ячейке была "по убыванию", а по времени по возрастанию. У него первая ячейка это какой то признак, а не день.

 

dizzel
Offline
Зарегистрирован: 21.03.2016

Верно первое число это номер релюхи и оно само сортируется на веб страничке...

brokly
brokly аватар
Offline
Зарегистрирован: 08.02.2014

dizzel пишет:

Верно первое число это номер релюхи и оно само сортируется на веб страничке...

Так если на веб морде включена сортировка по первой ячейке, то у тебя последовательность разрушится. Если конечно сортировка не по убыванию.

dizzel
Offline
Зарегистрирован: 21.03.2016

Ну точнее скажем так что там не происходит сортировка. Там данные разбираются по этому числу. А так как разбор идет по порядку от 0 до 29, то данные будут представлены в отсортированном виде и упорядоченно согласно времени от самого раннего до позднего события..

 

b707
Offline
Зарегистрирован: 26.05.2017

brokly пишет:

Да нет, как раз задача мутно поставлена, он хочет, что бы сортировка по первой ячейке была "по убыванию", а по времени по возрастанию. У него первая ячейка это какой то признак, а не день.

Так...  начинается типичное "потреблятство" - "пиджак хорош, но нельзя ли чуть-чуть изменить цвет"...

Брокли, я бы на твоем месте ничего бы ему не давал, пока не договоритесь о цене.

dizzel
Offline
Зарегистрирован: 21.03.2016

Не, я и не прошу. Я не хочу лезть на рожон. Брукли и так если честно поступил очень благородно. Дело в том что я описал даже не конкретно под свою задачу, а в общих чертах. Так что даже тот алгоритм что дал Брукли мне придется слегка адаптировать под себя. А вот если уже не будет получаться то я попрошу у Брукли имейл и думаю там мы уже договоримся.

dizzel
Offline
Зарегистрирован: 21.03.2016

Да Брукли, извините, пожалуйста, но кстати все равно не верно:

IN:
0,3,9,10,1
1,5,10,10,1
1,5,15,0,0
0,6,3,30,0
2,0,21,20,1
OUT:
2,0,21,20,1
1,5,10,10,1
1,5,15,0,0
0,3,9,10,1
0,6,3,30,0
 
Аут должен быть таким:
2,0,21,20,1
0,3,9,10,1
1,5,10,10,1
1,5,15,0,0
0,6,3,30,0
 
Брукли, скажите за сколько вы бы взялись помочь мне в этом вопросе? Я готов обрисовать больше деталей...
b707
Offline
Зарегистрирован: 26.05.2017

dizzel пишет:

А вот если уже не будет получаться то я попрошу у Брукли имейл и думаю там мы уже договоримся.

напомню, что ты изначально разместил тему в платном разделе. Брукли уже написал код и я не вполне понимаю, почему оплата его труда зависит от каких-то "если"...

Решать, конечно, Брукли... но как клиент ты ведешь себя некрасиво.

dizzel
Offline
Зарегистрирован: 21.03.2016

b707 пишет:

Брукли уже написал код и я не вполне понимаю, почему оплата его труда зависит от каких-то "если"...

Извините но сделки не было. Не было оговрены условия. Брукли проявил инициативу.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

b707 пишет:
А примерчик из учебника на сортировку пузырьком ТС и сам найдет
А чё, qsort уже выбросили из стандартной библиотеки?

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

ЕвгенийП пишет:

А чё, qsort уже выбросили из стандартной библиотеки?

http://arduino.ru/forum/ishchu-ispolnitelya/sortirovka-dvumernogo-massiv...

brokly
brokly аватар
Offline
Зарегистрирован: 08.02.2014

Да какая цена :) Дракула прав, за сортировку деньги брать стремно.

b707
Offline
Зарегистрирован: 26.05.2017

brokly пишет:

Да какая цена :) Дракула прав, за сортировку деньги брать стремно.

ну я за то, чтобы это был твой выбор :) А не нахальство со стороны клиента :)

brokly
brokly аватар
Offline
Зарегистрирован: 08.02.2014
#define SIZE 5

uint8_t in[][SIZE]={
  {0,3,9,10,1},
  {1,5,10,10,1},
  {1,5,15,0,0},
  {0,6,3,30,0},
  {2,0,21,20,1},
};

uint8_t out[5][SIZE]={0};

void printMass(uint8_t mass[][SIZE],uint8_t size){
   for(uint8_t i=0;i<size;i++){
      Serial.print(mass[i][0]);
      for(uint8_t j=1;j<SIZE;j++){
         Serial.print(',');
         Serial.print(mass[i][j]);     
      }
      Serial.println();
   }
}

// перевод времени в минуты
uint32_t getTime(uint8_t d, uint8_t h, uint8_t m){
  return (1440*d)+(60*h)+m;
}

void setup() {
  Serial.begin(115200);
  Serial.println("IN:");
  printMass(in,SIZE);
  uint8_t p[SIZE]={0}; // признак сортировки
  for(uint8_t i=0;i<SIZE;i++){ // подготовка данных
     p[i]=i;
  }
  // Сортировка массива пузырьком
  for (uint8_t i = 0; i < SIZE - 1; i++) {
     for (uint8_t j = 0; j < SIZE - i - 1; j++) {
        if (getTime(in[p[j]][1],in[p[j]][2],in[p[j]][3]) > 
            getTime(in[p[j+1]][1],in[p[j+1]][2],in[p[j+1]][3])) {
            p[j]^= p[j + 1]; p[j+1]^= p[j]; p[j]^= p[j + 1];
        }
     }
  }
  // заполняем выходной массив
  for(uint8_t i=0;i<SIZE; i++){
     memcpy(out[i],in[p[i]],sizeof(in[0]));
  }
  Serial.println("OUT:");
  printMass(out,SIZE);
}

void loop() {
   //...
}
IN:
0,3,9,10,1
1,5,10,10,1
1,5,15,0,0
0,6,3,30,0
2,0,21,20,1
OUT:
2,0,21,20,1
0,3,9,10,1
1,5,10,10,1
1,5,15,0,0
0,6,3,30,0
 
ТС, ну ты бы сам вникнул бы, а.... Вот и про квиксорт тут заговорили.
brokly
brokly аватар
Offline
Зарегистрирован: 08.02.2014

ЕвгенийП пишет:

А чё, qsort уже выбросили из стандартной библиотеки?

http://arduino.ru/forum/ishchu-ispolnitelya/sortirovka-dvumernogo-massiva#comment-581909

Нате вам за это каку:

uint32_t getTime(uint8_t* d){
  return (1440**(++d++))+(60**(d++))+*d;
}

void setup() {
  Serial.begin(115200);
  Serial.println("IN:");
  printMass(in,SIZE);
  
  qsort(in,SIZE,sizeof(in[0]),[](const void *x, const void *y)->int{
        return getTime((uint8_t*)x)>getTime((uint8_t*)y)?1:-1; 
        });
   
  Serial.println("OUT:");
  printMass(in,SIZE);
}

 

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

brokly пишет:

Нате вам за это каку:

uint32_t getTime(uint8_t* d){
  return (1440**(++d++))+(60**(d++))+*d;
}

void setup() {
  Serial.begin(115200);
  Serial.println("IN:");
  printMass(in,SIZE);
  
  qsort(in,SIZE,sizeof(in[0]),[](const void *x, const void *y)->int{
        return getTime((uint8_t*)x)>getTime((uint8_t*)y)?1:-1; 
        });
   
  Serial.println("OUT:");
  printMass(in,SIZE);
}

О! Приятно посмотреть!

Тока это ... чё функция сравнения ноль-то не ворочает, когда равны? Никашерна! :-)

brokly
brokly аватар
Offline
Зарегистрирован: 08.02.2014

Вот еще :) На самом деле она ничего не возвращает .  Она просто не компилится.

return (1440**(d+1))+(60**(d+2))+*(d+3);

Так надо курить.