урок 5. Сортировка массива

Глава 2. Алгоритмизация и программирование

Сортировка — это расстановка элементов списка (массива) в заданном порядке.
Под сортировкой (упорядочением) массива понимают перераспределение значений его элементов в некотором определенном порядке.

# Сортировка выбором.

Сортировка элементов массива по возрастанию выбором осуществляется следующим образом:

1. В массиве выбирается минимальный элемент (вернее, его индекс nMin, присваиваем ему значение первого элемента массива i).
2. В цикле сравниваем второй элемент массива с первым ( если A[ j ] меньше A [nMin], минимальный и первый элемент меняются местами (первый элемент считается отсортированным).

3. В неотсортированной части массива снова выбирается минимальный элемент; он меняется местами с первым неотсортированным элементом массива.
4. Действия пункта 3 повторяются с неотсортированными элементами массива, пока не останется один неотсортированный элемент (максимальный).

Шаги алгоритма: 1. находим номер минимального значения в текущем списке, 2. производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции), 3. теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы. Для реализации устойчивости алгоритма необходимо в пункте 2 минимальный элемент непосредственно вставлять в первую неотсортированную позицию, не меняя порядок остальных элементов.

Задача:
Произвести сортировку массива A по возрастанию, состоящего из N элементов, заполненного целыми случайными числами в диапазоне (1, 200).

ИДЕЯ решения задачи

1 этап — наполнение массива числами в диапазоне (1, 200), используя генератор случайных чисел, вывод массива

2 этап — сортировка элементов массива выбором, вывод отсортированного массива

# Сортировка пузырьком с помощью циклов for

from random import randint

N = 5
A = [0]*N
for i in range(N):
    A[i]=randint(1,200)
print(*A)
for i in range(N-1):
    for j in range(N-i-1):
        if A[j] > A[j+1]:
            A[j], A[j+1] = A[j+1], A[j]
print(A)

Интеллект — карта. Сортировка

Домашнее задание:
Теория: Изучить слайды презентации 9-4.ру_Основы программирования (Сайт Полякова К.Ю.)
Задачи."A", «B» слайд 62
(Написать программы на PYTHON) сдать учителю в Google — Класс.

ЗАДАЧА «А»
Напишите программу, которая заполняет массив из N = 10 элементов случайными числами в диапазоне [100,999] и сортирует его по возрастанию средней цифры числа (сначала идут все числа, средняя цифра которых равна 0, потом — 1, и т.д.).
Пример:
Массив: 502 163 256 137 198 374 119 181 144 16 9
Сортировка: 502 119 137 144 256 163 169 374 181 198

ЗАДАЧА «В»
Напишите программу, которая заполняет массив из N = 10 элементов случайными числами в диапазоне [10,100] и сортирует его по возрастанию последней цифры числа (сначала идут все числа, которые заканчиваются на 0, потом все, которые заканчиваются на 1, и т.д.).
Пример:
Массив: 12 10 31 40 55 63 28 87 52 92
Сортировка: 10 40 31 12 52 92 63 55 87 28

ДОПОЛНИТЕЛЬНО:

20. *Напишите программу, которая сортирует массив по убыванию суммы цифр числа.
21. *Напишите программу, которая сортирует первую половину
массива по возрастанию, а вторую – по убыванию (элементы
из первой половины не должны попадать во вторую и наоборот).

Информатика, 9 класс К.Ю. Поляков, Е.А. Еремин

Cдать программы в Google-Класс