Быстрая сортировка
Реализуйте алгоритм быстрой сортировки (её называют сортировкой Хоара).
За один шаг алгоритма выполните следующие действия:
Выберите один элемент списка (его иногда называют опорным элементом). Сделать это можно разными способами, но важно придерживаться
одного принципа. В нашем случае опорным элементом всегда будет крайний правый (например, в списке [1, 2, 3] это 3).
Разбейте текущий список на три части: элементы меньше опорного, равные опорному и больше опорного.
В списке [5, 8, 9, 4, 2, 9, 1, 8] опорным элементом будет число 8 (крайнее правое), а получить надо три списка:
Для списка с элементами меньше опорного ([5, 4, 2, 1]) и списка с элементами больше опорного ([9, 9]) выполните те же шаги заново —
запустите рекурсию.
результат_1 = рекурсия([5, 4, 2, 1]).
результат_2 = [8, 8].
результат_3 = рекурсия([9, 9]).
Сложите результаты вызова рекурсий и получите отсортированный список:
отсортированный_список = результат_1 + результат_2 + результат_3.
Пример с разбором алгоритма выше (как сработала рекурсия)
С [9, 9] всё просто. Элементов меньше или больше опорного нет, поэтому рекурсия не пойдёт глубже, а вызов рекурсии по списку [9, 9] быстро завершится и вернёт этот же список (его и не нужно было сортировать).
С [5, 4, 2, 1] рекурсия пойдёт вглубь:
опорным элементом выбирается число 1;
меньше 1 элементов нет (значит, рекурсия по ним продолжаться не будет);
помимо опорного элемента, других равных нет, получаем список [1];
больше 1 все остальные элементы [5, 4, 2] — с этим списком будет вызвана рекурсия.
опорный элемент — 2;
меньше опорного — [];
равные опорному — [2];
больше опорного — [5, 4].
опорный элемент — 4;
меньше — [];
равны — [4];
больше — [5].
Тут вызовы завершаются, мы соединяем списки и возвращаем список [5] на уровень выше (в вызов с числами [5, 4]).
Там мы соединяем списки [] + [4] + [5] и получаем [4, 5]. Этот список возвращаем ещё на уровень выше (в вызов с числами [5, 4, 2]).
Опять складываем списки:
[ ] + [2] + [4, 5] = [2, 4, 5].
Этот список возвращаем в вызов на уровень выше (тот, который был запущен с [5, 4, 2, 1]).
Складываем списки:
[ ] + [1] + [2, 4, 5] = [1, 2, 4, 5].
Возвращаем [1, 2, 4, 5] в самый первый вызов, где мы выполняли следующие вызовы:
результат_1 = рекурсия([5, 4, 2, 1]).
результат_2 = [8, 8].
результат_3 = рекурсия([9, 9]).
В итоге после выполнения всех рекурсий получаем:
результат_1 = [1, 2, 4, 5].
результат_2 = [8, 8].
результат_3 = [9, 9].
Складываем все списки:
[1, 2, 4, 5] + [8, 8] + [9, 9] = [1, 2, 4, 5, 8, 8, 9, 9].
Этот полный список возвращается наружу — туда, где функция была вызвана изначально.
Напишите функцию, которая реализует этот алгоритм. Для удобства добавьте вспомогательную функцию, пусть она принимает на вход список, а возвращает три списка (с элементами меньше, равными и больше опорного).
Пример работы такой функции:
числа = [4, 9, 2, 7, 5]
вспомогательная_функция(числа) → [4, 2], [5], [9, 7]
Эту функцию можно будет использовать в основной-рекурсивной, чтобы код основной функции стал проще и понятнее.
Результат вычислений корректен.
Формат вывода соответствует примеру.
Основной функционал описан в отдельной функции(-ях).
Переменные и функции имеют значащие имена, не только a, b, c, d.
Python Урок 7. Массивы (списки) в Питоне: продолжение (алгоритмы)
import random from random import randint n=10;x=5 mas = [randint(1,10) for i in range(n)] for i in range (n): if mas[i] == x: nomer = i break if nomer >= 0: print ( «mas[«, nomer, «]=», x, sep = «» ) else: print ( «Не нашли!» )
В данном случае в переменной nomer сохраняется номер элемента массива с найденным значением.
Можно также предусмотреть более короткий вариант решения:
from random import randint n=10; x=5 mas = [randint(1,10) for i in range(n)] # инициализируем массив print(mas) ifTrue = [item for item in mas if item == x]# создаем массив найденных значений print(len(ifTrue)>0)
from random import randint n=10; x=5 mas = [randint(1,10) for i in range(n)] # инициализируем массив print(mas) ifTrue = [item for item in mas if item == x]# создаем массив найденных значений print(len(ifTrue)>0)
Но на языке Python цикл for обладает уникальным свойством: у него есть блок else, который выполняется в том случае, если в цикле не применился оператор break.
1 2 3 4 5 6 7 8 9 10 11 12 13
import random from random import randint n=10;x=5 mas = [randint(1,10) for i in range(n)] nomer = -1 for i in range (n): if mas[i] == x: print ( "mas[", i, "]=", x, sep = "" ) break else: print ( "Не нашли!" )
import random from random import randint n=10;x=5 mas = [randint(1,10) for i in range(n)] nomer = -1 for i in range (n): if mas[i] == x: print ( «mas[«, i, «]=», x, sep = «» ) break else: print ( «Не нашли!» )
Задание Python 7_1:
Дан массив. Необходимо подтвердить, что в массиве есть числа, кратные трем.
Задание Python 7_2:
Заполните массив случайными числами в диапазоне 0..4 и выведите на экран номера всех элементов, равных значению X (оно вводится с клавиатуры).
Поиск минимального или максимального элемента
import random from random import randint mas = [randint(1,10) for i in range(n)] MaxEl = mas[0] for i in range(1,n): if mas[i] > MaxEl: MaxEl = mas[i] print (MaxEl)
import random from random import randint mas = [randint(1,10) for i in range(n)] MaxEl = mas[0] for i in range(1,n): if mas[i] > MaxEl: MaxEl = mas[i] print (MaxEl)
В переменной MaxEl сохранится максимальный элемент массива.
import random from random import randint mas = [randint(1,10) for i in range(n)] MaxEl = max (mas) print ( MaxEl )
import random from random import randint mas = [randint(1,10) for i in range(n)] MaxEl = max (mas) print ( MaxEl )
Задание Python 7_3:
Заполните массив случайными числами. Найдите номера первого минимального и последнего максимального элемента массива.
Сортировка массива в Python
Метод Пузырька
Сортировку массива в python будем выполнять методом Пузырька:
1 2 3 4 5 6 7 8 9 10 11 12 13
import random from random import randint mas = [randint(1,10) for i in range(n)] for i in range(n): print(mas[i],sep="") print(" ") for i in range(n-1): for j in range(n-2, i-1 ,-1): if mas[j+1] mas[j]: mas[j], mas[j+1] = mas[j+1], mas[j] for i in range(n): print(mas[i],sep="")
import random from random import randint mas = [randint(1,10) for i in range(n)] for i in range(n): print(mas[i],sep=»») print(» «) for i in range(n-1): for j in range(n-2, i-1 ,-1): if mas[j+1] < mas[j]: mas[j], mas[j+1] = mas[j+1], mas[j] for i in range(n): print(mas[i],sep="")
Задание Python 7_4:
Необходимо написать программу, в которой сортировка выполняется «методом камня» – самый «тяжёлый» элемент опускается в конец массива.
исходный массив: [8, 2, 9, 5, 6, 7, 0, 4] результат: [0, 2, 4, 5, 6, 7, 8, 9]
Быстрая сортировка массива
Данную сортировку еще называют quick sort или сортировка Хоара (по имени разработчика — Ч.Э. Хоар).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
import random from random import randint # процедура def qSort ( A, nStart, nEnd ): if nStart >= nEnd: return L = nStart; R = nEnd X = A[(L+R)//2] while L R: while A[L] X: L += 1 # разделение while A[R] > X: R -= 1 if L R: A[L], A[R] = A[R], A[L] L += 1; R -= 1 qSort ( A, nStart, R ) # рекурсивные вызовы qSort ( A, L, nEnd ) N=10 A = [randint(1,10) for i in range(N)] print(A) # вызов процедуры qSort ( A, 0, N-1 ) print('отсортированный', A)
Задание Python 7_5:
Необходимо написать программу, которая сортирует массив (быстрой сортировкой) по возрастанию первой цифры числа.
Исходный массив: [2, 99, 14, 100, 88, 21, 31, 43, 79, 71] Отсортированный массив: [2, 14, 21, 31, 43, 71, 79, 88, 99, 100]
Встроенные функции
- mas.reverse() — стандартный метод для перестановки элементов массива в обратном порядке;
- mas2 = sorted (mas1) — встроенная функция для сортировки массивов (списков);
Задание Python 7_6:
Напишите программу, которая, не изменяя заданный массив, выводит номера его элементов в возрастающем порядке значений этих элементов. Использовать вспомогательный массив номеров.
[1,5,2,3,7] результат: 0 2 3 1 4
Задание Python 7_7:
Напишите программу, которая сортирует массив и находит количество различных чисел в нём. Не использовать встроенные функции.
Пример:
Введите количество: 10 Массив: [15, 19, 15, 12, 10, 13, 4, 18, 38, 27] Массив отсортированный: [4, 10, 12, 13, 15, 15, 18, 19, 27, 38] Количество различных элементов: 9
Задание Python 7_8:
Дан массив. Назовем серией группу подряд идущих одинаковых элементов, а длиной серии — количество этих элементов. Сформировать два новых массива, в один из них записывать длины всех серий, а во второй — значения элементов, образующих эти серии.
Пример:
Введите количество элементов: 15 Массив: [3, 1, 1, 1, 2, 5, 2, 5, 5, 1, 1, 3, 2, 5, 5] Элементы, создающие серии: [1, 5] Длины серий: [3, 2, 2]
Задание Python 7_9:
Напишите вариант метода пузырька, который заканчивает работу, если на очередном шаге внешнего цикла не было перестановок. Не использовать встроенные функции.
Задание Python 7_10:
Напишите программу, которая сортирует массив, а затем находит максимальное из чисел, встречающихся в массиве несколько раз. Не использовать встроенные функции.
Введите количество: 15 Массив исходный: [7, 15, 8, 11, 4, 7, 9, 4, 6, 12, 12, 8, 9, 8, 3] Массив отсортированный: [3, 4, 4, 6, 7, 7, 8, 8, 8, 9, 9, 11, 12, 12, 15] Максимальное из чисел, встречающихся в массиве несколько раз: 12