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

В стиле Python:

from random import choice

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 )

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

N	метод пузырька	метод выбора	быстрая сортировка
1000	0,09 с	0,05 с	0,002 с
5000	2,4 с	1,2 с	0,014 с
15000	22 с	11 с	0,046 с

Сортировка массива случайных значений:

Сортировка в Python

B = 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

Задачи

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

, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.

«D»: Попробуйте построить массив из 10 элементов, на котором алгоритм быстрой сортировки c с выбором среднего элемента показывает худшую эффективность (наибольшее число перестановок). Сравните это количество перестановок с эффективностью метода пузырька (для того же массива).

§ 65. Двоичный поиск

Двоичный поиск

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

X = 7

X < 8

8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4

X > 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6

X > 6

Выбрать средний элемент A[c] и сравнить с X.
Если X == A[c], то нашли (стоп).
Если X < A[c], искать дальше в первой половине.
Если X > A[c], искать дальше во второй половине.

Двоичный поиск

A[0]						A[N-1]	A[N]
6	34	44	55	67	78	82

L

R

с

L

с

R

X = 44

L

с

R

L

R

L = R-1 : поиск завершен!

!

Двоичный поиск

L = 0; R = N # начальный отрезок

while L < R-1:

c = (L+R) // 2 # нашли середину

if X < A[c]: # сжатие отрезка

R = c

else: L = c

if A[L] == X:

print ( "A[", L, "]=", X, sep = "" )

else:

print ( "Не нашли!" )

Двоичный поиск

N	линейный поиск	двоичный поиск
2	2	2
16	16	5
1024	1024	11
1048576	1048576	21

скорость выше, чем при линейном поиске

нужна предварительная сортировка

Когда нужно применять?

?

Число сравнений:

Задачи

«A»: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Подсчитать количество сравнений.

Пример:_Массив:_1_4_7_3_9_2_4_5_2_После_сортировки:_1_2_2_3_4_4_5_7_9_Введите_число_X:_4'>Пример:_Массив:_1_4_7_3_9_2_4_5_2_После_сортировки:_1_2_2_3_4_4_5_7_9_Введите_число_X:_2'>Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 7 9

Введите число X:

2

Число 2 найдено.

Количество сравнений: 2

Задачи

«B»: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, сколько чисел, равных X, находится в массиве.

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 7 9

Введите число X:

4

Число 4 встречается 2 раз(а).

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 7 9

Введите число X:

14

Число 14 не встречается.

Задачи

«C»: Заполнить массив случайными числами и ввести число и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Если такого числа нет, вывести число, ближайшее к X.

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 12 19

Введите число X:

12

Число 12 найдено.

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 12 19

Введите число X:

11

Число 11 не найдено. Ближайшее число 12.