Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Министерство образования и науки РФ.
Федеральное агентство по образованию.
Томский Государственный Университет Систем Управления и
Радиоэлектроники.
ТУСУР.
Кафедра компьютерных систем в управлении и проектировании.
КСУП.
Отчет по лабораторной работе №7
“Сортировка ”
Выполнил: студент группы №514
______________________
Проверил: ассистент кафедры КСУП
______________________
ТОМСК – 2005г.
Содержание
1. Введение____________________________________________________________ стр.
2.Основная часть:
а)условие задачи №7_______________________________________________ стр.
б)программа с комментариями_____________________________________ стр.
в) условие задачи №17______________________________________________ стр.
г) программа с комментариями_____________________________________ стр.
3.Вывод_______________________________________________________________ стр.
Введение.
Сортировка – один из наиболее распространенных процессов современной обработки данных. Сортировкой называется распределение элементов множества по группам в соответствии с определенными правилами.
Сортировка простыми включениями
Этот метод обычно используют игроки в карты. Элементы
(карты) условно разделяются на готовую последовательность a1,a2,...,a(i-1) и входную последовательность ai,...,an. На каждом
шаге, начиная с i=2 и увеличивая i на 1, берут i-ый элемент входной последовательности и передают в главную последовательность, вставляя его на подходящее место.
Сортировка простым выбором
Метод:
1) Выбирается наименьший элемент.
2) Он меняется с первым элементом a[1].
3) Эти операции повторяются с оставшимися n-1 элементами, потом с n-2 элементами, пока не останется только один элемент наибольший.
Сортировка простым обменом (метод "пузырька")
Метод:
Сравниваем и обмениваем два соседних элемента, до тех пор пока не будут рассортированы все элементы.
Сортировка слиянием
Слияние обозначает объединение двух или более упорядоченных последовательностей в одну упорядоченную последовательность.
Задача №7.
Пусть дана строка, в которой между словами находится по одному пробелу. Переставить слова по возрастанию в лексикографическом порядке.
Описание переменных:
a) глобальные переменные:
б) локальные переменные:
Пошаговое описание:
Шаг №1 Вводим строку;
Шаг №2 Сортируем простым выбором;
Шаг №3 Выводим строку;
Описание ф-ий и процедур:
Lec – Сравнивает два слова и переставить слова по убыванию в лексикографическом порядке.
Hmv – Определяет кол-во слов в строке.
Wo – находит нужное слово в строке.
Del – удаляет нужное слово в строке.
Ins - вставляет нужное слово в строку.
Change – меняет местами слова.
Текст программы с коментариями
Uses Crt; {Подключение библиотек}
Var s : String;{Описание глобальных иеременных}
i,j : Word;
Function Lec(w1,w2:string):word;{Сравнивает два слова и определяет какое слово должно быть первым}
Var i1,kk,ll:word; {Описание локальных переменных}
Begin
If (Length(w1)>Length(w2)) then ll:=Length(w2) else ll:=Length(w1);
kk:=0;
For i1:=1 to ll do
If (Ord(w1[i1])<>Ord(w2[i1])) then
Begin
If (Ord(w1[i1])>Ord(w2[i1])) then kk:=1 else kk:=2;{}
Break;
End;
If ((kk=0)and(Length(w1)=ll)) then kk:=2;
If ((kk=0)and(Length(w2)=ll)) then kk:=1;
Lec:=kk;
End;
Function hmw(s2:string):word;{Определяет кол-во слов в строке}
Var i2,k2 : word; {Описание локальных переменных}
Begin
k2:=1;
For i2:=1 to Length(s2) do
If s2[i2]=' ' then inc(k2);
hmw:=k2;
End;
Function wo(n3:word;s3:string): string;{находит нужное слово}
Var i3,k3 :word; {Описание локальных переменных}
t3 :string;
Begin
k3:=1;
t3:='';
For i3:=1 to length(s3) do
Begin
If (s3[i3] = ' ') then Begin inc(k3); Continue; End;
If (k3 = n3) then t3:=t3+s3[i3];
End;
wo:=t3
End;
Procedure Del(var s4:string;n4:word);{удаляет нужное слово}
Var i4,k4,t4 :word; {Описание локальных переменных}
Begin
k4:=1;
t4:=0;
For i4:=1 to length(s4) do
Begin
If (s4[i4-t4] = ' ') then Begin inc(k4); Continue; End;
If (k4=n4) then Begin Delete(s4,i4-t4,1);Inc(t4); End;
End;
End;
Procedure Ins(var si:string;wi:string;ni:word);{Вставляет нужное слово}
Var ki,ii :word; {Описание локальных переменных}
Begin
ki:=1;
If (ki=ni) then begin Insert(wi,si,ni);Exit; end;
For ii:=1 to length(si) do
begin
If (si[ii] = ' ') then inc(ki);
If (ki=ni) then Begin Insert(wi,si,ii+1);Break; End;
end;
End;
Procedure Change(var st:string;v1,v2:word);{меняет слова местами}
var i5 :word; {Описание локальных переменных}
os :string;
Begin
os:=st;
Del(st,v1);
Ins(st,wo(v2,os),v1);
Del(st,v2);
Ins(st,wo(v1,os),v2);
End;
BEGIN
ClrScr; {Очитска экрана}
Write('Введите строку: ');
Readln(s);{Ввод строки}
For i:=1 to (hmw(s)-1) do{сортировка простым выбором}
For j:=i+1 to hmw(s) do
If Lec(wo(i,s),wo(j,s))=2 then Change(s,i,j);
Write('Строка: ',s);{вывод отсортированной строки}
Readkey;
END.{Конец программы}
Результаты работы прогаммы:
Введите строку: 345 ghfj tyrue cvbd
Строка: 345 cvbd ghfj tyrue
Задача №17
Дана матрица A из целых чисел размером MxN. Переставить строки матрицы так, чтобы строки стали расположены по возрастанию в лексикографическом порядке.
Описание переменных:
1)Глобальные:
а) i, j- определяем тип word, так как нужны целочисленные значения.
б) c – mat;
2)Локальные:
t1,i1,i2,k2 - определяем тип word, так как нужны целочисленные значения.
Пошаговое описание алгоритма:
Шаг№1 забиваем массив случайными числами;
Шаг№2вызов процедуры сортировки методом пузырька ;
Шаг№3 вывод результата на экран.
Описание ф-ий и процедур:
Lec – Устанавливает лексикографический порядок строк .
Change – Меняет местами строки матрицы.
Текст программы с комментариями
uses Crt; {Подключение библиотек}
const m=3; {Описание констант}
n=4;
type mat=array[1..m,1..n] of word; {Задание нового типа}
Var i,j:word; {Описание глобальных иеременных}
c :mat;
Procedure Change(var m1:mat;s11,s12:word); {Заголовок процедуры}
Var t1,i1 :word; {Описание локальных переменных}
Begin
For i1:=1 to n do
Begin
t1:=m1[s11,i1];m1[s11,i1]:=m1[s12,i1];m1[s12,i1]:=t1;
End;
End;
Function Lec(m2:mat;s21,s22:word):word; {Заголовок функции}
Var i2,k2 :word; {Описание локальных переменных}
Begin
k2:=1;
For i2:=1 to n do
Begin
If m2[s21,i2]>m2[s22,i2] then begin k2:=1;break; end;
If m2[s21,i2]<m2[s22,i2] then begin k2:=2;break; end;
End;
lec:=k2;
End;
BEGIN
ClrScr; {Очитска экрана}
Randomize;
For i:=1 to m do
Begin
For j:=1 to n do
Begin
c[i,j]:= random(100); {Задание массива случайным образом}
If ((c[i,j] div 10)>0) then Write(c[i,j],' ') else Write(c[i,j],' ');
End;
Writeln;
End;
For i:=1 to (m-1) do
For j:=i to m do
If Lec(c,i,j)=1 then Change(c,i,j);{Сортировка}
Writeln;
For i:=1 to m do
Begin
For j:=1 to n do {Вывод результата}
If ((c[i,j] div 10)>0) then Write(c[i,j],' ') else Write(c[i,j],' ');
Writeln;
End;
Readkey;
END.
Результаты работы прогаммы:
8 84 25 83
42 17 82 21
11 18 45 90
8 84 25 83
11 18 45 90
42 17 82 21
Вывод
С помощью этой лабораторной работы мы ознакомились с сортировкой, научились использовать метод пузырька и случайного выбора.