Упорядочение массива методом вставки Сообщение по Информатике ученика 11 «а» класса МОУ СОШ 45 Калюжного Андрея Калининград 2008 г. - презентация

1 Упорядочение массива методом вставки Сообщение по Информатике ученика 11 «а» класса МОУ СОШ 45 Калюжного Андрея Калининград 2008 г.

2 Цели проекта Рассмотреть принцип сортировки массива вставками. Научиться применять метод сортировки на практике. Рассмотреть случаи применения сортировки «вставками»

3 На сайте 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

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 Алгоритм сортировки массива. Готовый код программы можно скачать по адресу: или взять в приложенном у проекту архиве.

5 Приведем в пример простую задачу сортировки массива методом «вставки»: 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