Сортировка массива

Войдите на сайт для отправки комментариев

Пт, 16/08/2019 - 00:08

Arahissis

Offline

Зарегистрирован: 15.08.2019

Всем доброго времени суток. Я новичок как в ардуине, так и в написании программ под нее. Вот решил ради интереса и даже скорее тренировки, написать сортировку массива. Вот как получилось, как думаете, код слишком не оптимизированный и кривой?

01int m = 55;
02int M[] = {7,9,22,41,4,10,43,8,19,45,21,55,6,75,30,7,5,85,54,455,1,54,98,
034,34,22,111,98,90,43,21,344,555,32,399,21,77,654,32,98,512,70,34,5,1,
042222,19,4,3,259,1090,459,33,49,510};
05int Vmax=0, index=-1;
06void setup()
07{ 
08 Serial.begin(9600); 
09}
10  
11void loop()
12{ 
13   for ( int i =0 ; i<m ; i++ )
14  {   
15       if ( M[i] > Vmax and M[i]!=-1  )
16        {               
17          Vmax = M[i]; 
18          index = i;                                 
19        }                     
20  } 
21 
22  if (Vmax>0)
23  { 
24   Serial.println(Vmax); 
25  }
26  else
27  {
28    Serial.end();
29  }
30   
31 for ( int i =0 ; i<m ; i++ )
32  {   
33      
34      M[index] =-1;
35      Vmax =0;                    
36  } 
37       
38}

Ну и да тут, возможно даже не сортировка, т.к массив в конце заполняется значениями -1, но это можно исправить.

Пт, 16/08/2019 - 01:30

nik182

Offline

Зарегистрирован: 04.05.2015

Сортировка это то что студентам начального программистского образования дают в качестве разминки. Во многих учебниках преведены разные алгоритмы и описано на каких наборах данных какие работают лучше. Универсального = быстрого и мало использующего память нет. Чем Ваш алгоритм отличается от стандартных? К какому классу сортировщиков относится? Или Вы работу по классиикации Вашего алгоритма на нас хотите перевесить? Напишите чем Ваш алгоритм лучше стандартных.

Пт, 16/08/2019 - 08:44

DetSimen

Offline

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

Для изобретателей бициклов: есть стандартные библиотечные функции, лучше них никто не напишет

01/*
02Name:       TestSort.ino
03Created:    16.08.2019 4:02:40
04Author:     DtS
05*/
06 
07int M[] = { 7,9,22,41,4,10,43,8,19,45,21,55,6,75,30,7,5,85,54,455,1,54,98,
084,34,22,111,98,90,43,21,344,555,32,399,21,77,654,32,98,512,70,34,5,1,
092222,19,4,3,259,1090,459,33,49,510 };
10 
11size_t M_Size = sizeof(M) / sizeof(M[0]);
12 
13 
14int ArrayCompare(const int *AFirst, const int *ASecond) {
15    if (*AFirst < *ASecond) return -1;
16    return (*AFirst == *ASecond) ? 0 : 1;
17}
18 
19 
20void PrintArray(const int *AArray, const size_t ASize) {
21    char buf[32];
22    for (uint8_t i = 0; i < ASize; i++) {
23        sprintf(buf, "M[%d] = %d", i, AArray[i]);
24        Serial.println(buf);
25    }
26 
27    Serial.println();
28}
29 
30void setup()
31{
32    Serial.begin(115200);
33    Serial.println("Start sorting...\n\n");
34 
35    uint32_t StartSortingTime = micros();
36 
37    qsort(M, M_Size, sizeof(M[0]), ArrayCompare);
38 
39    uint32_t EndSortingTime = micros();
40 
41    Serial.print("Array sorted at: ");
42    Serial.print(EndSortingTime - StartSortingTime);
43    Serial.println(" microseconds.\n");
44 
45    PrintArray(M, M_Size);
46 
47    Serial.println("Reverse Sorting\n");
48    StartSortingTime = micros();
49    qsort(M, M_Size, sizeof(M[0]), [](const int *AFirst, const int *ASecond) -> int{ return -ArrayCompare(AFirst, ASecond); });
50    EndSortingTime = micros();
51     
52    Serial.print("Array reverse sorted at: ");
53    Serial.print(EndSortingTime - StartSortingTime);
54    Serial.println(" microseconds.\n");
55     
56    PrintArray(M, M_Size);
57     
58}
59 
60void loop() { }

Пт, 16/08/2019 - 14:50

Logik

Offline

Зарегистрирован: 05.08.2014

nik182, с меня плюс, но вот это

// студентам начального программистского образования дают в качестве разминки.

Как бы пренебрежительно. А не стоит. Алгоритмы сортировки - одно из сокровищ. Т.к. на практике огромное кол-во задач использует их для решения, а на упорядоченом множестве все рещается проще и быстрей. И если кто скажет что для ардуины не актуально, то это не так. Простой случай: один таймер а нужно формировать N временных интервалов для ряда независимых процессов. Засовываем интервалы в М[N], а таймер настраиваем на минимальный из всего М. Но его нужно найти, и искать каждый раз заново. Это может быть долго, но если М сортирован - проблема снимается.

Для ТС - известное видео https://www.youtube.com/watch?v=Gnp8G1_kO3I

Пт, 16/08/2019 - 15:26

wdrakula

Offline

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

Речь, как я понял, о том, что в avr-libc, в штатной, есть qsort(). Так какой чудак станет строить велосипед, соревнуясь с кодом, который вошел в состав libc десятки лет назад? Кто этот истиный фанат велосипедостроительства? Я еще могу понять, что математику иногда нужно переписывать, для компактности, но сортировку? Хотя - "каждый д..очит, как он хочет" (с).

Пт, 16/08/2019 - 16:00

b707

Offline

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

Arahissis - во-первых, как вы сами пишете, у вас не сортировка, а печать элементов массива в нужном порядке, причем сам массив после вашей процедуры портится. Для общности перепишите Ваш метод. чтобы на выходе снова получаося массив с прежними элементами. но в упорядоченном виде.

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

Пт, 16/08/2019 - 16:19

DetSimen

Offline

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

b707 пишет:

Эмммм... А сапщение #2 тока я вижу?

Пт, 16/08/2019 - 16:28

b707

Offline

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

DetSimen пишет:

Эмммм... А сапщение #2 тока я вижу?

эээээээээээ сорри :) проглядел

А результаты чего не выложил, интересно же!

Пт, 16/08/2019 - 16:37

DetSimen

Offline

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

1,711 мс прямо сортирует, и 2,080 обратно. Обратно сортирует предварительно отсортированный прямо.

Пт, 16/08/2019 - 16:41

DetSimen

Offline

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

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

Пт, 16/08/2019 - 16:53

#10

Arahissis

Offline

Зарегистрирован: 15.08.2019

`1`	`Не знаю правильно ли считал миллисекунды, но вот что получилось.`

01int m = 25;
02int M[] = {100,155,900,43,65,29,22,35,89,990,670,91,671,1,54,333,1090,56,4,25,
039999,346,212,86,901};
04int Vmax=0, index=-1, t=0 , i=0;
05uint32_t StartSortingTime, EndSortingTime;
06void setup()
07{ 
08 Serial.begin(9600); 
09}
10  
11void loop()
12{ 
13   
14   StartSortingTime = micros();
15   for ( i =t ; i<m ; i++ )
16    {   
17       if ( M[i] > Vmax )
18        {               
19          Vmax = M[i]; 
20          index = i;                                           
21        }      
22   }                 
23 
24 
25 for ( i = t ; i<m ; i++ )
26  {   
27      Vmax = M[i]; 
28      M[i] = M[index];
29      M[index] = Vmax;
30      t++;
31      Vmax=0;
32      Serial.println(M[i]);        
33      break;                                                       
34  } 
35   
36     EndSortingTime = micros();
37       
38     if (t ==m)
39     {
40      Serial.print(" microseconds ");
41      Serial.print(EndSortingTime - StartSortingTime);
42      Serial.end();
43     }
44  }

Ср, 22/03/2023 - 14:11

#11

Buzoff

Offline

Зарегистрирован: 03.04.2018

Добрый день.

А разве, для правильного расчета длительности процесса в посте #10, 14я строка, StartSortingTime = micros();, не должна находиться в setup?

И почему переменной index (в том же посте #10) присваивается значение -1, если она с этим значением нигде вроде не используется? Или это осталось при копировании первого варианта программы? Просто интересно, так как сам объяснения не нашел.

Вс, 02/07/2023 - 10:47

#12

kakaxi

Offline

Зарегистрирован: 20.07.2021

Используйте метод сортировки пузырьков.

Arduino.ru

Регистрация новых пользователей и создание новых тем теперь только на новом форуме https://forum.arduino.ru

Сортировка массива