Сортировка данных на 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(n²). Это означает, что при увеличении массива время работы алгоритма будет расти экспоненциально. Например, массив из 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" с комментариями переводчика.