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

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

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

int m = 55;
int M[] = {7,9,22,41,4,10,43,8,19,45,21,55,6,75,30,7,5,85,54,455,1,54,98,
4,34,22,111,98,90,43,21,344,555,32,399,21,77,654,32,98,512,70,34,5,1,
2222,19,4,3,259,1090,459,33,49,510};
int Vmax=0, index=-1;
void setup()
{ 
 Serial.begin(9600); 
}
 
void loop()
{ 
   for ( int i =0 ; i<m ; i++ )
  {   
       if ( M[i] > Vmax and M[i]!=-1  )
        {               
          Vmax = M[i]; 
          index = i;                                 
        }                     
  } 

  if (Vmax>0)
  { 
   Serial.println(Vmax); 
  }
  else
  {
    Serial.end();
  }
  
 for ( int i =0 ; i<m ; i++ )
  {   
     
      M[index] =-1;
      Vmax =0;                    
  } 
      
}
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

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

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

/*
Name:       TestSort.ino
Created:	16.08.2019 4:02:40
Author:     DtS
*/

int M[] = { 7,9,22,41,4,10,43,8,19,45,21,55,6,75,30,7,5,85,54,455,1,54,98,
4,34,22,111,98,90,43,21,344,555,32,399,21,77,654,32,98,512,70,34,5,1,
2222,19,4,3,259,1090,459,33,49,510 };

size_t M_Size = sizeof(M) / sizeof(M[0]);


int ArrayCompare(const int *AFirst, const int *ASecond) {
	if (*AFirst < *ASecond) return -1;
	return (*AFirst == *ASecond) ? 0 : 1;
}


void PrintArray(const int *AArray, const size_t ASize) {
	char buf[32];
	for (uint8_t i = 0; i < ASize; i++) {
		sprintf(buf, "M[%d] = %d", i, AArray[i]);
		Serial.println(buf);
	}

	Serial.println();
}

void setup()
{
	Serial.begin(115200);
	Serial.println("Start sorting...\n\n");

	uint32_t StartSortingTime = micros();

	qsort(M, M_Size, sizeof(M[0]), ArrayCompare);

	uint32_t EndSortingTime = micros();

	Serial.print("Array sorted at: ");
	Serial.print(EndSortingTime - StartSortingTime);
	Serial.println(" microseconds.\n");

	PrintArray(M, M_Size);

	Serial.println("Reverse Sorting\n");
	StartSortingTime = micros();
	qsort(M, M_Size, sizeof(M[0]), [](const int *AFirst, const int *ASecond) -> int{ return -ArrayCompare(AFirst, ASecond); });
	EndSortingTime = micros();
	
	Serial.print("Array reverse sorted at: ");
	Serial.print(EndSortingTime - StartSortingTime);
	Serial.println(" microseconds.\n");
	
	PrintArray(M, M_Size);
	
}

void loop() { }

 

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

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

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

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

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

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

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

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

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

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

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

b707 пишет:

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

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

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

DetSimen пишет:

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

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

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

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

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

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

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

Arahissis
Offline
Зарегистрирован: 15.08.2019
Не знаю правильно ли считал миллисекунды, но вот что получилось.
int m = 25;
int M[] = {100,155,900,43,65,29,22,35,89,990,670,91,671,1,54,333,1090,56,4,25,
9999,346,212,86,901};
int Vmax=0, index=-1, t=0 , i=0;
uint32_t StartSortingTime, EndSortingTime;
void setup()
{ 
 Serial.begin(9600); 
}
 
void loop()
{ 
  
   StartSortingTime = micros();
   for ( i =t ; i<m ; i++ )
    {   
       if ( M[i] > Vmax )
        {               
          Vmax = M[i]; 
          index = i;                                           
        }      
   }                 


 for ( i = t ; i<m ; i++ )
  {   
      Vmax = M[i]; 
      M[i] = M[index];
      M[index] = Vmax;
      t++;
      Vmax=0;
      Serial.println(M[i]);        
      break;                                                       
  } 
  
     EndSortingTime = micros();
      
     if (t ==m)
     {
      Serial.print(" microseconds ");
      Serial.print(EndSortingTime - StartSortingTime);
      Serial.end();
     }
  }