Упорядочение массива методом вставки Сообщение по Информатике ученика 11 «а» класса МОУ СОШ 45 Калюжного Андрея Калининград 2008 г.
Цели проекта Рассмотреть принцип сортировки массива вставками. Научиться применять метод сортировки на практике. Рассмотреть случаи применения сортировки «вставками»
На сайте ALGLIB.RU можно найти следующее описание сортировки массива «вставками»:ALGLIB.RU Последовательно просматриваем a2,..., an и каждый новый элемент ai вставляем на подходящее место в уже упорядоченную совокупность a1,..., ai. Это место определяется последовательным сравнением ai с упорядоченными элементами a1,..., ai. ~ i = 2 j = 1 a(i) < a(j) нет да k = i: b = a(i) a(k) = a(k-1) k > j k = k-1 нет да j = j+1 j < i нет да i = i+1 i <= n да нет ~ a(j) = b: j = i 351 i = j = 1 j = 2 n = 3 i = 3 k = 3 b = 1 5 k = 2 3 k = 1 1 i = 4
FOR i = 2 TO n Открываем цикл по переменной i, изначально равному 2-ум j = 1 Присваиваем переменной j значение 1 WHILE j < i Открываем цикл по переменной j IF a(i) < a(j) THENСравниваем переменные с индексами i и j. Если меньше, то: b = a(i) Присваиваем переменной b значение переменной i FOR k = i TO j STEP -1Открываем цикл по переменной k с шагом -1 a(k) = a(k - 1)Присваиваем эл. массива с инд. k значение эл. инд. k-1 NEXT k Закрываем цикл по переменной k a(j) = b Присваиваем эл. массива с инд. j значение переменной b j = 1Присваиваем переменной j значение 1 ELSE Если нет, то есть если переменная с индексами i > j j = j + 1Увеличиваем значение переменной j на 1 END IFЗакрываем блочную форму оператора IF … THEN WENDЗакрываем цикл по переменной j NEXT IЗакрываем цикл по переменной i Алгоритм сортировки массива. Готовый код программы можно скачать по адресу: или взять в приложенном у проекту архиве.
Приведем в пример простую задачу сортировки массива методом «вставки»: 10 CLS 20 RANDOMIZE TIMER 30 INPUT Какой размер массива"; n 40 DIM a(n) 50 PRINT Исходный массив:" 60 FOR i = 1 TO n 70 a(i) = CINT(RND * (-400) + 200) 80 PRINT a(i); 90 NEXT i 100 FOR i = 2 TO n 110 j = WHILE j < i 130 IF a(i) < a(j) THEN 140 b = a(i) 150 FOR k = i TO j STEP a(k) = a(k - 1) 170 NEXT k 180 a(j) = b 190 j = ELSE 210 j = j END IF 230 WEND 240 NEXT I 250 PRINT : PRINT Отсортированный массив:" 260 FOR i = 1 TO n 270 PRINT a(i); 280 NEXT i 290 END