Файл: 62. Массивы 63. Алгоритмы обработки массивов.pptx

Сортировка – это расстановка элементов массива в заданном порядке.

…по возрастанию, убыванию, последней цифре, сумме делителей, по алфавиту, …

Алгоритмы:

простые и понятные, но неэффективные для больших массивов

метод пузырька
метод выбора

сложные, но эффективные

«быстрая сортировка» (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

Как написать метод «камня»?

?

Как сделать рекурсивный вариант?

?

Задачи

«A»: Напишите программу, в которой сортировка выполняется «методом камня» – самый «тяжёлый» элемент опускается в конец массива.

«B»: Напишите вариант метода пузырька, который заканчивает работу, если на очередном шаге внешнего цикла не было перестановок.

«С»: Напишите программу, которая сортирует массив по убыванию суммы цифр числа. Используйте функцию, которая определяет сумму цифр числа.

Идея: найти минимальный элемент и поставить его на первое место.

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»: Массив содержит четное количество элементов. Напишите программу, которая сортирует первую половину массива по возрастанию, а вторую – по убыванию. Каждый элемент должен остаться в «своей» половине.

Пример:

Массив:

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

«C»:

Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком» и методом выбора. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.

Быстрая сортировка (QuickSort)

Ч.Э.Хоар

Идея: выгоднее переставлять элементы, который находятся дальше друг от друга.

Для массива из N элементов нужно всего N/2 обменов!

!

Быстрая сортировка

Шаг 2: переставить элементы так:

при сортировке элементы не покидают « свою область»!

Шаг 1: выбрать некоторый элемент массива X

A[i] <= X

A[i] >= X

Шаг 3: так же отсортировать две получившиеся области

Разделяй и властвуй (англ. divide and conquer)

Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов (для этого надо отсортировать массив…).

Как лучше выбрать X?

?

Быстрая сортировка

Разделение:

выбрать любой элемент массива (X=67)
установить L = 1, R = N
увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа)
уменьшая R, найти первый элемент A[R], который <= X (должен стоять слева)
если L<=R то поменять местами A[L] и A[R] и перейти к п. 3 иначе стоп.

Быстрая сортировка

78	6	82	67	55	44	34
L						R

34	6	82	67	55	44	78
		L			R

34	6	44	67	55	82	78
			L	R

34	6	44	55	67	82	78
			R	L

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 ):