Программирование. Программирование на языке Python (Полякова К.Ю.). Общие сведения о языке Python История

• Название: Общие сведения о языке Python История
• Анкор: Программирование
• Дата: 27.02.2023
• Размер: 5.72 Mb.
• Имя файла: Программирование на языке Python (Полякова К.Ю.).ppt
• Тип: Документы; #956875
• страница: 17 из 18

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

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


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

A[i] <= X

A[i] >= X

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


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


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

78

6

82

67

55

44

34

Как лучше выбрать 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

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

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 части


массив


начало


конец