методы сортировок. Алгоритмизация и программирование
 Скачать 1.44 Mb.
|
Раздел 3. Алгоритмизация и программирование§29-30. Методы сортировок Что такое сортировка?Сортировка – это расстановка элементов массива в заданном порядке. …по возрастанию, убыванию, последней цифре, сумме делителей, по алфавиту, … Алгоритмы:
метод выбора сложные, но эффективные «быстрая сортировка» (QuickSort) сортировка «кучей» (HeapSort) сортировка слиянием (MergeSort) пирамидальная сортировка время работы N Метод пузырька (сортировка обменами)Идея: пузырек воздуха в стакане воды поднимается со дна вверх. Для массивов – самый маленький («легкий» элемент перемещается вверх («всплывает»).
сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами за 1 проход по массиву один элемент (самый маленький) становится на свое место 1-й проход:
Метод пузырька
2-й проход: 3-й проход:
4-й проход:
Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов). ! Метод пузырька1-й проход: сделать для j от N-2 до 0 шаг -1 если A[j+1]< A[j] то # поменять местами A[j] и A[j+1] 2-й проход: сделать для j от N-2 до 1 шаг -1 если A[j+1]< A[j] то # поменять местами A[j] и A[j+1] 1 единственное отличие! Метод пузырька1-й проход: for j in range(N-2, -1 ,-1): if A[j+1]< A[j]: # поменять местами A[j] и A[j+1] 2-й проход: for j in range(N-2, 0 ,-1): if A[j+1]< A[j]: # поменять местами A[j] и A[j+1] 0 единственное отличие! от N-2 до 0 шаг -1 Метод пузырькаfor i in range(N-1): for j in range(N-2, i-1 ,-1): if A[j+1] < A[j]: A[j], A[j+1] = A[j+1], A[j] i-1 Идея: найти минимальный элемент и поставить его на первое место. for i in range(N-1): найти номер nMin минимального элемента из A[i]..A[N] if i != nMin: поменять местами A[i] и A[nMin] for i in range(N-1): if i!= nMin: A[i], A[nMin] = A[nMin], A[i] nMin = i for j in range(i+1,N): if A[j] < A[nMin]: nMin = j Сортировка слияниемСлияние отсортированных массивов:
A B
С Na = len(A); Nb = len(B) iA = iB = 0; C = [] while iA < Na and iB < Nb: if A[iA] <= B[iB]: C.append(A[iA]); iA += 1 else: C.append(B[iB]); iB += 1 C = С + A[iA:] + B[iВ:] пока оба массива непустые добавить остаток Сортировка слияниемdef mergeSort( A ): if len(A) <= 1: return mid = len(A) // 2 L = A[:mid] R = A[mid:] mergeSort(L) mergeSort(R) C = merge(L, R) for i in range(len(A)): A[i] = C[i] слияние выход из рекурсии рекурсивные вызовы копируем результат в массив A Почему нельзя A = C? ? Сортировка слияниемdef merge( A, B ): Na = len(A); Nb = len(B) iA = iB = 0; C = [] while iA < Na and iB < Nb: if A[iA] <= B[iB]: C.append(A[iA]); iA += 1 else: C.append(B[iB]); iB += 1 C = С + A[iA:] + B[iВ:] return C Процедура слияния: Сортировка слияниемзадача разбивается на несколько подзадач меньшего размера; эти подзадачи решаются с помощью рекурсивных вызовов того же (или другого) алгоритма; решения подзадач объединяются, и получается решение исходной задачи. «Разделяй и властвуй» (divide and conquer): работает быстро нужен дополнительный массив Ч.Э.Хоар разделение I: < X III: > X II: = X Эти части нужно так же отсортировать! ! Как лучше выбирать X? ? Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов (долго искать …). B1: < X B2: > X BX: = X import random def qSort ( A ): if len(A) <= 1: return A X = random.choice(A) B1 = [ b for b in A if b < X ] BX = [ b for b in A if b == X ] B2 = [ b for b in A if b > X ] return qSort(B1) + BX + qSort(B2) Что плохо? ? Где рекурсия? ? Asort = qSort( A ) расход памяти! Сравнение алгоритмов сортировки
Быстрая сортировка «на месте»Шаг 2: переставить элементы так: при сортировке элементы не покидают « свою область»! Шаг 1: выбрать некоторый элемент массива X
Шаг 3: так же отсортировать две получившиеся области Разделяй и властвуй (англ. divide and conquer)
Как лучше выбрать X? ? Быстрая сортировкаРазделение: выбрать любой элемент массива (X=67) установить L = 0, R = N-1 увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа) уменьшая R, найти первый элемент A[R], который <= X (должен стоять слева) если L<=R то поменять местами A[L] и A[R] и перейти к п. 3 иначе стоп.
L R L R 78 44 44 78 Быстрая сортировка
L > R : разделение закончено! ! Быстрая сортировкаN = 7 A = [0]*N # заполнить массив qSort( A, 0, N-1 ) # сортировка # вывести результат Основная программа: массив начало конец Быстрая сортировка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 ) qSort ( A, nStart, R ) qSort ( A, L, nEnd ) рекурсивные вызовы while A[L] < X: L += 1 while A[R] > X: R -= 1 разделение на 2 части массив начало конец меняем местами Быстрая сортировкаСлучайный выбор элемента-разделителя: from random import randint def qSort ( A, nStart, nEnd ): ... X = A[randint(L,R)] ... X = A[randint(L,R)] или так: from random import choice def qSort ( A, nStart, nEnd ): ... X = choice ( A[L:R+1] ) ... X = choice ( A[L:R+1] ) Сортировка в PythonB = sorted( A ) алгоритм Timsort По возрастанию: B = sorted( A, reverse = True ) По убыванию: reverse = True По последней цифре: def lastDigit ( n ): return n % 10 B = sorted( A, key = lastDigit ) key = lastDigit или так: B = sorted( A, key = lambda x: x % 10 ) lambda x: x % 10 «лямбда»-функция (функция без имени) Сортировка в Python – на местеA.sort() По возрастанию: A.sort ( reverse = True ) По убыванию: reverse = True По последней цифре: def lastDigit ( n ): return n % 10 A.sort ( key = lastDigit ) key = lastDigit или так: A.sort( key = lambda x: x % 10 ) lambda x: x % 10 Задачи«A»: Массив содержит четное количество элементов. Напишите программу, которая сортирует по возрастанию отдельно элементы первой и второй половин массива. Каждый элемент должен остаться в «своей» половине. Используйте алгоритм быстрой сортировки. Пример: Массив: 5 3 4 2 1 6 3 2 После сортировки: 2 3 4 5 6 3 2 1 Задачи«B»: Напишите программу, которая сортирует массив и находит количество различных чисел в нем. Используйте алгоритм быстрой сортировки. Пример: Массив: 5 3 4 2 1 6 3 2 4 После сортировки: 1 2 2 3 3 4 4 5 6 Различных чисел: 5 Задачи«A»: Напишите программу, в которой сортировка выполняется «методом камня» – самый «тяжёлый» элемент опускается в конец массива. «B»: Напишите вариант метода пузырька, который заканчивает работу, если на очередном шаге внешнего цикла не было перестановок. «С»: Напишите программу, которая сортирует массив по убыванию суммы цифр числа. Используйте функцию, которая определяет сумму цифр числа. Задачи«C»: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком», методом выбора и алгоритма быстрой сортировки. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода. «D»: Попробуйте построить массив из 10 элементов, на котором алгоритм быстрой сортировки c с выбором среднего элемента показывает худшую эффективность (наибольшее число перестановок). Сравните это количество перестановок с эффективностью метода пузырька (для того же массива). Задачи«A»: Массив содержит четное количество элементов. Напишите программу, которая сортирует первую половину массива по возрастанию, а вторую – по убыванию. Каждый элемент должен остаться в «своей» половине. Пример: Массив: 5 3 4 2 1 6 3 2 После сортировки: 2 3 4 5 6 3 2 1 Задачи«B»: Напишите программу, которая сортирует массив и находит количество различных чисел в нем. Пример: Массив: 5 3 4 2 1 6 3 2 4 После сортировки: 1 2 2 3 3 4 4 5 6 Различных чисел: 5 |