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

• Название: 62. Массивы 63. Алгоритмы обработки массивов
• Дата: 28.04.2023
• Размер: 1.09 Mb.
• Имя файла: programmirovanie-na-yazyke-python.pptx
• Тип: Документы; #1095573
• страница: 9 из 16

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

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], искать дальше во второй половине.