Реферат: Сортировкой массива

Сортировка массивов


Под сортировкой массива подразумевается процесс перестановки элементов с целью упорядочивания их в соответствии с каким-либо критерием (по возрастанию, убыванию, последней цифре, сумме делителей, …).


Виды сортировок:


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

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


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

метод выбора




«быстрая сортировка» (Quick Sort)

сортировка «кучей» (Heap Sort)

сортировка слиянием

пирамидальная сортировка


Рассмотрим один из видов сортировок (сложный, но эффективный – «быстрая сортировка» (Quick Sort).


Идея – более эффективно переставлять элементы, расположенные дальше друг от друга.


^ Сколько перестановок нужно, если массив отсортирован по убыванию, а надо – по возрастанию? (N div 2)


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


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




A[i] <= X

A[i] >= X

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


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


78

6

82

67

55

44

34


Разделение:

выбрать средний элемент массива (X=67)




78

6

82

67

55

44

34




установить L:=1, R:=N

увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа)

уменьшая R, найти первый элемент A[R], который <= X (должен стоять слева)

если L<=R, поменять местами A[L] и A[R] и перейти к п. 3


L > R : разделение закончено


procedure QSort ( first, last: integer);

var L, R, c, X: integer;

begin

if first < last then

begin

X:= A[(first + last) div 2];

L:= first; R:= last;


while L <= R do

begin

while A[L] < X do L:= L + 1;

while A[R] > X do R:= R - 1;

if L <= R then

begin

c:= A[L]; A[L]:= A[R]; A[R]:= c;

L:= L + 1; R:= R - 1;

end;

end;

QSort(first, R); QSort(L, last);

end;

end;


Программа для сортировки массива по возрастанию:


Задача № 1. Заполнить массив из 10 элементов случайными числами в интервале [-50..50] и отсортировать его по возрастанию с помощью алгоритма быстрой сортировки.


program qq;

uses crt;

const N = 10;

var A: array[1..N] of integer;

i:integer;

procedure QSort ( first, last: integer);

var L, R, c, X: integer;

begin

if first < last then

begin

X:= A[(first + last) div 2];

L:= first; R:= last;


while L <= R do

begin

while A[L] < X do L:= L + 1;

while A[R] > X do R:= R - 1;

if L <= R then

begin

c:= A[L]; A[L]:= A[R]; A[R]:= c;

L:= L + 1; R:= R - 1;

end;

end;

QSort(first, R); QSort(L, last);

end;

end;

Begin

clrscr;

writeln('icxodnay massiv');

randomize;

For i:=1 to n do Begin

A[i]:=random(101)-50;

Write(A[i]:6); End;

writeln;

writeln;

Qsort ( 1, N );

writeln ('novij massiv=');

for i:= 1 to n do

write (a[i]:6);

end.

end.


^ Программа для сортировки массива по убыванию:


Задача № 2. Заполнить массив из 10 элементов случайными числами в интервале [-50..50] и отсортировать его по убыванию с помощью алгоритма быстрой сортировки.

program qq;

uses crt;

const N = 10;

var A: array[1..N] of integer;

i:integer;

procedure QSort ( first, last: integer);

var L, R, c, X: integer;

begin

if first < last then

begin

X:= A[(first + last) div 2];

L:= first; R:= last;


while L <= R do

begin

while A[L] < X do L:= L + 1;

while A[R] > X do R:= R - 1;

if L <= R then

begin

c:=A[R];A[R]:=A[L];A[L]:=c;

L:= L + 1; R:= R - 1;

end;

end;

QSort(first, R); QSort(L, last);

end;

end;

Begin

clrscr;

writeln('icxodnay massiv');

randomize;

For i:=1 to n do Begin

A[i]:=random(101)-50;

Write(A[i]:6); End;

writeln;

writeln;

Qsort ( 1, N );

writeln ('novij massiv=');

for i:= 1 to n do

write (a[i]:6);

end.

end.