перебрать массив по возрастанию побыстрее, как это сделать за n циклов AVR? Опции

[_Ivan_33]

здравствуйте! есть массив на 32 элемента типа int
нужно поставить их в порядке возрастания микроконтроллером ATmega1280 с тактовой частотой 16 Мгц от кварца
успею ли я простым перебором, сранивая соседние числа и двигая их уложиться в 1100 мкс?

[MrYuran]

Оптимальный алгоритм требует 2*N циклов сравнения (емнип), где N - количество сортируемых членов
Алгоритм Шелла
Педия

[_Ivan_33]

спасибо добрый человек =)

[=GM=]

массив на 32 элемента типа int нужно отсортировать в порядке возрастания

Я делал сортировку таким образом.

0. Номер массива i=1

1. Для i-го элемента простым перебором находится максимум от (i+1)-го элемента массива до N-го.

2. Максимум сравнивается с i-м элементом и меняется их местами, если второй больше.

3. i=i+1

4. п.1-п.3 повторяются до i=N

За 17600 тактов спокойно можно отсортировать. Чтобы убыстрить процесс, можно разбить массив пополам, отсортировать каждую половину, затем слить вместе.

[Xenia]

Можно еще быстрее . Только для этого надо сразу класть числа на нужное место, раздвигая ранее положенные. Типа того, как солдат ищет себе место в строю. Причем можно съэкономить циклы, если не сравнивать новое число со всеми прежде лежащими в массиве, а принимать во внимание, что этот массив всегда упорядочен. Т.е. солдат сначала тыкается в середину строя, сравнивая свой рост со стоящим в середине. Взависимости от этого сравнения, сразу отбрасывается половина ряда, с которой сравниваться нет необходимости. Дальше он тыкается в середину соответствующего полуряда, потом четвертьряда и т.д. В результате чего найдет свое место за не более log₂(N) сравнений.

[ASN]

_Ivan_33
Посмотрите qsort из <stdlib.h>.

[dch]

слияние отсортированных массивов, правда тебуется двукратный объем памяти или индекса, сначал у Вас размер массивчика 1 а пар массивов 16, а в конце одна пара массивов, а размер массива 16 и туда сюда гоняете

Сообщение отредактировал dch - Feb 17 2010, 16:29

[rezident]

ИМХО Xenia забыла упомянуть, что для ее способа желательно иметь второй буфер. В противном случае "сразу класть числа на нужное место" вступает в противоречие с "раздвигая ранее положенные".