Сортировка массива методом «пузырька» Подготовили: ученицы 11 «А» класса МОУ СОШ 45 Кадцина Наталья Мачай Ирина Галантынова Мария.

Презентация:



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

Линейный массив Сортировка методом обмена («пузырька»)
Сортировка массива. Информатика 9 класс Токар И.Н. Информатика ФГОСС.
Сортировка простым обменом. (методом «пузырька») Рассмотрим идею метода на примере. Отсортируем по возрастанию массив из 5 элементов:
Подведение итогов г. Н.Новгород школа 58. Блиц-опрос! Что такое двумерный массив? Как его описать? Как заполнить двумерный массив? Приведите примеры заполнения.
Тема: Массивы ОДНОМЕРНЫЕ МАССИВЫ. Проверка домашнего задания Найти все 3-х значные числа, заканчивающихся на 2, 4, 8 и делящихся на 6. CLS FOR I = 100.
Двумерные массивы. Двумерным массивом называется совокупность данных, каждое значение которых, зависит от его положения в строке и в столбце.
Сортировка методом простого обмена (метод пузырька) Рекурсивная сортировка.
как подготовить информацию к обработке на компьютере как воспользоваться компьютером для обработки информации.
ВВОД 2. ЕСЛИ 3. СЛЕДУЮЩИЙ 4. МАССИВ 5. ВЫВОД.
Сортировка Сортировкой числового массива называют расположение его элементов в возрастающем или убывающем по величине порядке. Сортировка символьного массива.
СОРТИРОВКА МАССИВА МЕТОДОМ ВСТАВОК (insertion sort). Проект подготовили ученицы 11 «А» класса Тян Анастасия Ежевская Дарья Муниципальное общеобразовательное.
Урок 10. Сортировки 425 а1а2а3а4 Пример: Дан целочисленный массив А из 4-х элементов. 1 шаг. а1>a2? Да 3 b If a[1]>a[2] then begin b:=a[2]; a[2]:=a[1];
П. Лаплас – выдающийся французский математик, физик и астроном, известен работами в области небесной механики, дифференциальных уравнений, один из создателей.
Программирование на языке Паскаль Урок Сортировка массивов Рыжикова С. В. Учитель информатики МОУ СОШ 2 г. Волжского Волгоградской обл.
Массивом называется упорядоченная совокупность однородных величин, обозначенных каждая одним и тем же именем с различными целочисленными индексами, изменяющимися.
Простые алгоритмы сортировки. 2 Сортировка Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре,
Укажите строку, в которой есть ошибка: 1. Dim a(12) 2. For i=1 to Input a(i) 4. Next 5. s=a(12) 6. For i=1 to a(i)=a(i)-s 8. Next Ответ: 6.
Сортировка массивов Что изменилось? ЧТО ДАЛЬШЕ ? Поменяем местами голубой и лиловый прямоугольники.
ОДНОМЕРНЫЙ МАССИВ. Решение задач Разработка: Клинковская М.В. – учитель информатики и ИКТ МОУ гимназии 7 г. Балтийска уч. год.
Транксрипт:

Сортировка массива методом «пузырька» Подготовили: ученицы 11 «А» класса МОУ СОШ 45 Кадцина Наталья Мачай Ирина Галантынова Мария

Цели и задачи Ознакомиться с сортировкой методом «пузырька»Ознакомиться с сортировкой методом «пузырька» Научиться применять этот метод в решении задач Научиться применять этот метод в решении задач Узнать в каких случаях применяется этот метод Узнать в каких случаях применяется этот метод

Сортировка методом пузырька Основная идея сортировки (например, по возрастанию) методом пузырька очень простая. Предположим, что у нас N элементов в массиве и индекс каждого элемента лежит в промежутке от 1 до N. Первый шаг сортировки методом пузырька Например: 3, 1, 7, -9, 5 1. Сравниваем первый и второй элементы массива. Если первый элемент больше, чем второй, то меняем их местами. 1, 3, 7, -9, 5 2. Сравниваем второй и третий элементы массива. Если второй элемент больше, чем третий, то меняем их местами.... 1, 3, 7, -9, 5 3. Сравниваем предпоследний (N-1) и последний (N) элементы массива. Если предпоследний элемент больше, чем последний, то меняем их местами. 1, 3, -9, 5, 7 В результате самым последним элементом в массиве у нас окажется самый большой элемент. Повторяем вышеуказанные действия для части массива, начиная с 1 позиции до N-1 (шаг 2).

Второй шаг сортировки методом пузырька 1. Сравниваем первый и второй элементы массива. Если первый элемент больше, чем второй, то меняем их местами. 1, 3, -9, 5, 7 1, 3, -9, 5, 7 2. Сравниваем второй и третий элементы массива. Если второй элемент больше, чем третий, то меняем их местами. 1, -9, 3, 5, 7 1, -9, 3, 5, 7 3. Cравниваем элемент N-2 и элемент N-1 массива. Если (N-2)-й элемент больше, чем элемент N-1, то меняем их местами. 1, -9, 3, 5, 7 1, -9, 3, 5, 7 В результате предпоследний элемент в массиве у нас тоже будет на своем, "отсортированном" месте.

Последующие шаги сортировки методом пузырька Повторяем вышеуказанные действия для части массива, начиная с 1 позиции до N-2 (шаг 3), а потом для диапазона 1..N-3 и так далее до диапазона , 1, 3, 5, 7 -9, 1, 3, 5, 7 После завершения последнего шага наш массив будет отсортирован по возрастанию.

Блок схема

Программа 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 * (-200) + 100) 80 PRINT a(i); 90 NEXT i 100 FOR i = 1 TO n 110 FOR j = 1 TO n IF a(j) >= a(j + 1) THEN SWAP a(j), a(j + 1) 130 NEXT j 140 NEXT i 150 PRINT : PRINT "Отсортированный массив:" 160 FOR i = 1 TO n 170 PRINT a(i); 180 NEXT i 190 END

Блок схема

Программа CLS: RANDOMIZE TIMER INPUT Сообщите размер массива; n DIM a(n) PRINT Исходный массив FOR i=1 TO n a(i) = int(rnd*(-200)+100) PRINT a(i); NEXT i 1 x=0 FOR i=1 TO n-1 IF a(i)>a(i+1) THEN SWAP a(i), a(i+1) x=x+1 END IF NEXT i IF x>0 THEN 1 PRINT FOR i=1 TO n PRINT a(i); NEXT i END

Вывод Метод «пузырька» самый простой для понимания и реализации.Метод «пузырька» самый простой для понимания и реализации. Эффективен лишь для небольших массивов.Эффективен лишь для небольших массивов. Устойчивая сортировка ( не меняет взаимного расположения элементов без надобности).Устойчивая сортировка ( не меняет взаимного расположения элементов без надобности).