воскресенье, 21 октября 2012 г.

Сортировка данных на NXT

В начале этой неделе я опубликовал вопрос: как в произвольном тексте найти 10 наиболее часто используемых слов? В программах для NXT обработка кучи данных с сенсоров является обыденным делом, но что если тебе надо узнать только 10 самых больших или маленьких значений? Как ты будешь решать этот вопрос? В языке RobotC нет специальных функций для сортировки; в NXC есть единственная ArraySort функция, упорядочивающая численные массивы по возрастанию. Поэтому в данной статье я решил провести небольшое исследование различных алгоритмов сортировки. Я помню эту классную демонстрацию работы алгоритмов, которая наглядно показывает различия в принципах сортировки. Я подумал, что будет реально здорово, если я сделаю тоже самое на NXC. И я сделал это.


Пузырьковая сортировка


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

for(int i = 0; i < MAX_NUMBERS; i++)
{
  for(int j = 0; j < (MAX_NUMBERS - 1); j++)
  {
    if (arr[j] > arr[j+1])
    {
      temp = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = temp;
    }
  }
}

№ итерации
Исходный массив 10 5 2 7 1 9
1 5 10 2 7 1 9
2 5 2 10 7 1 9
3 5 2 7 10 1 9
4 5 2 7 1 10 9
5 5 2 7 1 9 10
6 2 5 7 1 9 10
7 2 5 1 7 9 10
8 2 1 5 7 9 10
9 1 2 5 7 9 10

Единственным его недостатком является то, что он достаточно медленный. Его вычислительная сложность равна O(n2). Это означает, что при увеличении массива время работы алгоритма будет расти экспоненциально. Например, массив из 11 показаний сенсоров будет отсортирован на 20% медленнее, чем массив из 10 элементов, а обработка 50 замеров потребуют в 25 раз больше времени.

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


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

for (i = 1 ; i < MAX_NUMBERS ; i++ )
{
  for (j = 0 ; j < i ; j++ )
  {
    if ( arr[j] > arr[i] )
    {
      temp = arr[j] ;
      arr[j] = arr[i] ;
 
      for (k = i ; k > j ; k-- )
      {
        arr[k] = arr[k - 1] ;
      }
      arr[k + 1] = temp ;
    }
  }
}

В таблице ниже кроме самих итераций алгоритма я покажу, чему равнялась переменная temp.

№ итерации  temp
Исходный массив 10 5 2 7 1 9 -
1 5 5 2 7 1 9 10
2 5 10 2 7 1 9 -
3 2 10 10 7 1 9 5
4 2 2 10 7 1 9 5
5 2 5 10 7 1 9 -
6 2 5 7 7 1 9 10
7 2 5 7 10 1 9 -
8 1 5 7 10 10 9 2
9 1 5 7 7 10 9 2
10 1 5 5 7 10 9 2
11 1 1 5 7 10 9 2
12 1 2 5 7 10 9 -
13 1 2 5 7 9 9 10
14 1 2 5 7 9 10


Сортировка Шелла


Сортировка Шелла является модификацией алгоритма сортировки вставками. Разница вот в чем: вместо того, чтобы сравнивать соседние элементы, как в сортировке пузырьком, сортировка Шелла несколько раз сравнивает элементы, находящиеся на определенном расстоянии друг от друга (зададим расстояние буквой m). Это расстояние равняется половине размера входного массива и на каждой последующей итерации m уменьшается вдвое.
В нашем примере сначала будут сортироваться между собой элементы, отстоящие друг от друга на расстоянии 3 элемента (6 / 2 = 3), а затем на расстоянии 1-го элемента (3 / 2 = 1 - целочисленное деление).

for(m = MAX_NUMBERS/2 ; m > 0; m /= 2)
{
  for(j = m; j < MAX_NUMBERS; j++)
  {
    for(i = j - m; i >= 0; i -= m)
    {
      if(arr[i + m] >= arr[i])
        break;
      else
      {
        mid = arr[i];
        arr[i] = arr[i + m];
        arr[i + m] = mid;
      }
    }
  }
}

В таблице ниже вы можете увидеть, как это работает:

№ итерации 
Исходный массив 10 5 2 7 1 9
1 7 5 2 10 1 9
2 7 1 2 10 5 9
3 1 7 2 10 5 9
4 1 2 7 10 5 9
5 1 2 7 5 10 9
6 1 2 5 7 10 9
7 1 2 5 7 9 10


Демонстрационная программа


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

Исходный код программы на языке NXC доступен здесь. Данная статья является переводом руководства Xander Soldaat "Tutorial: Sorting your Data" с комментариями переводчика.

4 комментария:

  1. Нельзя ли использовать Qsort/heapsort. Они намного быстрее

    ОтветитьУдалить
  2. Дело в том, что quicksort алгоритм подразумевает поддержку рекурсии железом и языком программирования. А стандартное FW NXT блока, не поддерживает рекурсии - так, что о quicksort остается только мечтать. Ровно как и о других рекурсивных алгоритмах.

    ОтветитьУдалить
  3. В новом RobotC появилась же поддержка рекурсии?

    ОтветитьУдалить
  4. я же сказал - стандартное FW - это раз. А два - то, что данная статья про NXC.

    ОтветитьУдалить

Related Posts Plugin for WordPress, Blogger...