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

Сортировка методом прямого включения

Полезная статья? Пожалуйста, поставьте "+"
Алгоритмизация и программирование - Содержание
Сортировка методом прямого включения, так же как и сортировка методом простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов.
Сортировка методом прямого включения, как и все описанные выше, производится по шагам. На k - м шаге считается, что часть массива, содержащая первые    k-1 элементов, уже упорядочена, то есть
а [1] ≤ а [2] ≤  ... ≤ a [k-1].
Далее необходимо взять k - й элемент и подобрать для него такое место в отсортированной части массива, чтобы после его вставки упорядоченность не нарушалась, то есть надо найти такое j ( 1 ≤ j ≤ k -1 ), что а [j] ≤ a[k] < a[j+1]. Затем вставить элемент  а [k]  на найденное место.
С каждым шагом отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить n-1 шаг.
Сейчас можно коротко описать фрагмент алгоритма сортировки методом прямого включения:
For  k: = 2  To  n  Do
{ так как начинам сортировку с поиска подходящего места для a[2], i изменяется от 2 до n }
Begin
x: = a[k];
‘вставить x на подходящее место в a[1] , ..., a[k] ‘
End;
Осталось ответить на вопрос, как осуществить поиск подходящего места для элемента x. Поступим следующим образом: будем просматривать элементы, расположенные левее x ( то есть те, которые уже упорядочены ), двигаясь к началу массива. Нужно просматривать элементы a[ j ] , j изменяется от k-1 до 1. Такой просмотр должен закончиться при выполнении одного из следующих условий:
•    найден элемент a[j] < x, что говорит о необходимости вставки x между  a[j-1] и a[j].
•    достигнут левый конец упорядоченной части массива, следовательно, нужно вставить x на первое место.
До тех пор, пока одно из этих условий не выполнится, будем смещать просматриваемые элементы на первую позицию вправо, в результате чего в отсортированной части будет освобождено место под x.

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

program n3; { Сортировка по убыванию }
const n=5;
type ar=array [1..n] of integer;
var  i:integer;
a:ar;

procedure sorting3(var a:ar);
var i,j,x,k:integer;
begin
for k:=2 to n do
begin
x:=a[k]; j:=k-1;
while (j>0)and(x>=a[j]) do
begin
a[j+1]:=a[j];
dec(j);
end;
a[j+1]:=x;
end;
end;
begin
writeln('Введите исходный массив:');
for i:=1 to n do read(a[i]);
sorting3(a);
writeln('Отсортированный массив:');
for i:=1 to n do write(a[i],' ');
writeln;
end.
Категория: Алгоритмизация и программирование | Добавил: Ni-Cd (10 Декабря 2011)
Просмотров: 2179 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
  Полезные материалы  

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

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

Поиск
 

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

Статистика


Рейтинг@Mail.ru

 


2007 - 2024 © Ni-Cd. All Rights Reserved