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

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

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

3 Сортировка методом пузырька Основная идея сортировки (например, по возрастанию) методом пузырька очень простая. Предположим, что у нас 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).

4 Второй шаг сортировки методом пузырька 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 В результате предпоследний элемент в массиве у нас тоже будет на своем, "отсортированном" месте.

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

6 Блок схема

= a(j " title="Программа 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 - 1 120 IF a(j) >= a(j " class="link_thumb"> 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 = 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"> = a(j " title="Программа 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 - 1 120 IF a(j) >= a(j ">

8 Блок схема

9 Программа 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

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