Киберфак – бесплатно скачать презентации PowerPoint, лекции, рефераты, шпоры, курсовые cyberfac logo
cyberfac.ru
На главную | Регистрация | Вход
  Статьи  
Главная » Статьи » Информатика » Алгоритмизация и программирование

Обменная сортировка с разделением (сортировка Хоара)

Полезная статья? Пожалуйста, поставьте "+"
Алгоритмизация и программирование - Содержание

Сортировка методом простого обмена ( методом "пузырька” ) является в среднем самой неэффективной. Это обусловлено самой идеей метода, который требует в процессе сортировки сравнивать и обменивать между собой только соседние элементы. Можно существенно улучшить метод сортировки, основанный на обмене. Это улучшение приводит к самому лучшему на сегодняшний день методу сортировки массивов, который можно назвать обменной сортировкой с разделением. Он основан на сравнениях и обменах элементов, стоящих на возможно больших расстояниях друг от друга. Предложил этот метод Ч. А. Р. Хоар в 1962 году. Поскольку производительность этого метода впечатляюща, автор назвал его "быстрой сортировкой”.

Идея метода
1.     В исходном неотсортированном массиве выбрать некоторый элемент        x ( барьерный элемент ).
2.     Переставить элементы массива таким образом, что слева от x оказались элементы массива, меньшие или равные x, а справа - элементы массива, большие x.
Пусть при этом элемент x попадет в позицию k, тогда массив будет иметь вид:  ( a[1], a[2], ... , a[k-1] ), a[k], ( a[k+1], ... , a[n] ).

Каждый из элементов a[1], a[2], ... , a[k-1] меньше либо равен a[k], каждый из элементов a[k+1], ... , a[n]  больше a[k]. Отсюда можно сделать вывод, что элемент a[k] стоит на своем месте. А исходный массив при этом разделится на две неотсортированные части, барьером между которыми является элемент a[k].

Для дальнейшей сортировки необходимо применить пункты 1 и 2 для каждой из этих частей. И так до тех пор, пока не останутся подмассивы, состоящие из одного элемента, то есть пока не будет отсортирован весь массив.

Алгоритм "быстрой сортировки” можно определить как рекурсивную процедуру, параметрами которой являются  нижняя и верхняя границы изменения индексов сортируемой части исходного массива:

program n5;var a: array[1..10] of integer;procedure Init;
{формирование массива из фала}
var f: text;
i: integer;
begin
Assign(f,'g:\s.dat');
Reset(f);
for i:=1 to 10 do read(f,a[i]);
close(f);
end;

procedure Print;          {печать массива}
var i: integer;
begin
for i:=1 to 10 do write(a[i]:5);
writeln;
end;

procedure Quik_sorting(m,l: integer);
var i,j,x,w: integer;
begin
i:=m;
j:=l;
x:=a[(m+l) div 2];
repeat
while a[i] while a[j]>x do dec(j);
if i<=j then
begin
w:=a[i]; a[i]:=a[j]; a[j]:=w;
inc(i);
dec(j);
end;
until i>j;
if m if iend;
begin                     {основная программа}
writeln('Массив:');
init;
print;
Quik_sorting(1,10);
writeln('отсортированный массив');
print;
end.

Категория: Алгоритмизация и программирование | Добавил: Ni-Cd (10 Декабря 2011)
Просмотров: 1416 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
  Полезные материалы  

В нашем каталоге файлов можно найти много полезной информации. Также советуем заглянуть в каталог статей: в нем есть полезные статьи по темам: Экономика предприятия, Общая экономика, Финансы и Кредит, также Словарь терминов по экономике, Маркетинг, Бухучет и Мировая экономика
Также есть полезная страница Факультеты МИФИ, которая расскажет о том, какие есть в МИФИ факультеты.
Меню
 

Навигация
Высокоуровневые методы информатики и программирования [28]
Информатика и программирование [34]
Информационные системы в экономике [36]
Языки программирования и методы трансляции [15]
Алгоритмизация и программирование [61]
 

Поиск
 

Онлайн
Онлайн всего: 1
Гостей: 1
Пользователей: 0
 

Статистика


Рейтинг@Mail.ru

 


2007 - 2018 © Ni-Cd. All Rights Reserved