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

Вид материала

Документы

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

Подобный материал:

• Сортировка одномерного массива, 21.66kb.
• Поэтому при написании программы будьте особенно внимательны, не путайте индексы элементов, 363.59kb.
• Лабораторная работа «Сортировка массива», 19.68kb.
• Поняття масиву. Одновимірний масив, 62.45kb.
• Задача сводится к организации цикла по I и вычислению Ci=Ai+Bi при каждом значении, 96.83kb.
• План урока: Проверка домашнего задания. Объяснение нового материала, 64.98kb.
• Самостоятельная работа Найти произведение всех элементов двумерного массива, которые, 14.88kb.
• Одномерные и двумерные массивы (таблицы) Массив, 105.09kb.
• Исследование влияния геометрических параметров оборудования на форму и размеры трещины, 74.33kb.
• Программа вычисления суммы элементов двумерного массива const, 28.23kb.

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


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


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

Простые и понятные, но неэффективные для больших массивов	Сложные, но эффективные
метод пузырька метод выбора	«быстрая сортировка» (Quick Sort) сортировка «кучей» (Heap Sort) сортировка слиянием пирамидальная сортировка

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


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

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

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


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

A[i] <= X

A[i] >= X

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


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

78

6

82

67

55

44

34

Разделение:

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

78

6

82

67

55

44

34

2. установить L:=1, R:=N
   
3. увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа)
   
4. уменьшая R, найти первый элемент A[R], который <= X (должен стоять слева)
   
5. если 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.