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

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

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

Разделение:

• выбрать любой элемент массива (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

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

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

...

X = choice ( A[L:R+1] )

...

X = choice ( A[L:R+1] )

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

В стиле 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 )