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

[Mark_Shadow]

Понятие сортировки и ее назначение. Внутренняя и внешняя сортировка. Пример.
Сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке.
Цель сортировки - облегчить последующий поиск элементов в таком отсортированном множестве.
Различают сортировки по возрастанию (неубыванию) и убыванию (невозрастанию).
Различают методы внутренней сортировки (в памяти компьютера) и внешней сортировки (данные из файла).
Эффективность алгоритма - количество сравнений элементов и их перестановок в ходе алгоритма.

Вот с примером пока проблематично... я тут попыталась ее написать... но у меня все сводится к занесению данных в память компьютера... зря время потратила...
Короче, потом еще подумаю... примером внутренней сортировки может служить любая из тех, что я выложу чуть позже...

Сортировка массива методом простого выбора.
Удобна для массива, не содержащего одинаковые элементы.

Пример

program Sort_Coice;
const n=10;
var m: array[1..n] of real;
min: real;
imin,k,i: integer;
begin
for k:=1 to n-1 do
begin
min:=m[k];
imin:=k;
for i:=k+1 to n do
if m[i]<min then
begin
min:=m[i];
imin:=i;
end;
m[imin]:=m[k];
m[k]:=min;
end;
end.

Сортировка массива методом обмена (“пузырьковая сортировка”).
Самая любимая сортировка)

Пример.

program sort_exchange;
const n=10;
var m: array [1..n] of real;
w: real;
i,k: integer;
begin
for k:= 1 to n-1 do
for i:= 1 to n-k do
if m[i]>m[i+1] then
begin
w:=m[i];
m[i]:=m[i+1];
m[i+1]:=w;
end;
end.

Сортировка массива методом вставки (прямого включения).
Это как раз та самая, которую я пыталась в файле использовать...

Пример.

program sort_insert;
const n=11;
var m: array [0..n-1] of integer;
i,j,x: integer;
begin
for i:=2 to n-1 do
begin
x:=m[i];
m[0]:=x;
j:=i;
while x<m[j-1] do
begin
m[j]:=m[j-1];
dec(j);
end;
m[j]:=x;
end;
end.

Сортировка массива методом слияний (сортировка фон Неймана).
Разбить массив на несколько частей, части сортируются любым методом.

Пример.

program sort_merge;
const n=10;m=5;l=5;
var a: array [1..m] of integer;
b: array [1..l] of integer;
c: array [1..n] of integer;
i,j,k: integer;
begin
i:=1;j:=1;k:=1;
while (i<=m) and (j<=l) do
if a[i] < b[j] then begin
c[k]:=a[i];
inc(i);
inc(k);
end
else
begin
c[k]:=b[j];
inc(j);
inc(k);
end;
while j<=m do
begin
c[k]:=b[j];
inc(j);
inc(k);
end;
end.

{Быстрая сортировка (сортировка Хоара).
Основная идея - сокращение числа операций при обмене не соседних, а далеко стоящих элементов.

Пример.

ну, в общем, это я потом допишу...}

Comments

[Элайт,]

мы их в прошлом семестре наизусть учили.. 4 или 5 видов сортировок..
до сих пор передергивает

[Mark_Shadow]

ААА!!! Ты их знаешь??? Скажи, у тебя нигде не завалялось примера внешней сортировки??!
Нигде не могу найти...

Напрашивается вопрос) а где ты учишься?

[Элайт,]

внешнее - это что? мы, мб, ее по-другому называли))
я сейчас заканчиваю первый курс по прикладной математике и информатике)))

[Mark_Shadow]

Сиреневый ветерок
Вай))) я тоже учусь на ПМИ))) тож первый курс) А я все переживала, что среди моих дневниковцев нет программистов)
Паскаля больше не будет... поэтому оценка идет в диплом... короче, мы сдаем все, что знаем по паскалю и больше с этим поленом не встретимся) А так как весь второй семестр учили Си и Дэльфи, то Паскалем никто не занимался)
Внешняя, ну это когда ты данные читаешь, например с хард диска или с файла... ну в общем откуда-нибудь, а их настолько много, что в оперативную память они не помещаются, данные из файла ты можешь считывать последовательно, а значит можешь их сортировать... Вот сортировка из файла и называется внешней. Алгоритмы вроде как те же... но что-то у меня не получается...

[Элайт,]

мы с паскалем еще в первом семестре попрощались)) и ура.
ыыы)))
имхо, тут классно сортировка прошла бы. первое принимаешь за какое-то ключевое значение, потом смотришь больше или меньше.. та же сортировка вставками по сути.
не, у нас такого безобразия не было))) зато поразрядная была ><

[Mark_Shadow]

Сиреневый ветерок
как же вам везет... мы ведь в этом семестре только зря время тратили на это паскаль...
хотя, говорят, что будет время когда нам 10 языков за неделю освоить нужно будет))) так что я не расстраиваюсь сильно из-за того, что завтра экзамен.
Вот я тоже думала, что сортировка вставками здесь больше всех подходит. кроме того, в файле даже лучше - не надо индексы сдвигать все время.

[Элайт,]

чем дальше, тем ведь легче) тем более, бОльшая часть языков сделана именно на базе паскаля или си) так что такого ужаса, как в переходе с первого на второй уже не будет ^__^
удачи тебе там завтра на экзамене) выдай все по полной)))

а вас самих эти сортировки по алгоритму заставляют писать? О_о

[Mark_Shadow]

Сиреневый ветерок
Спасибо тебе за поддержку!
нет ну почему... вот те, что выложила, я правда недописала быструю сортировку, их нам давали)
а вот с файлом, надо самой организовать)
Какие языки вы еще учите?