Алгоритмы поиска и сортировки данных

Введение 3
1. Алгоритмы сортировки и поиска 6
1.1. Сортировка массива методом «всплывающего пузырька» 6
1.2. Сортировка массива методом поиска локального минимума 8
1. 3. Сортировка Шелла 9
1.4. Прямой поиск в неупорядоченном массиве 13
1.5. Бинарный поиск в упорядоченном массиве 13
1.6. Интерполяционный поиск элемента в массиве 15
2. Алгоритм оценки эффективности методов сортировки и поиска 17
3. Разработка программного продукта 21
3.1. Интерфейс программного продукта 21
3.2. Программные тексты с комментариями 23
3.2.1. Листинг программного модуля ukurs_p.cpp 23
Заключение 29
Список литературы 30

cpp
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "uKurs_p.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
int m[100], kol;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
// процедура передачи чисел из Мemo2 глобальный массив m
void IsMemo2()
{int i;
kol=Form1->Memo2->Lines->Count;
Form1->Lbkol->Caption=IntToStr(kol);
for (i=0;i<=kol-1;i++)
{m[i]=StrToInt(Form1->Memo2->Lines->Strings[i]);}
}
//--------------------------------------------------------
// процедура передачи чисел из глоб.массива m в ListBox2
void VListBox2 ()
{int i;
Form1->ListBox2->Items->Clear();
for (i=0;i<=kol-1;i++)
{Form1->ListBox2->Items->Strings[i]=IntToStr(m[i]);}
}
//--------------------------------------------------------
void __fastcall TForm1::btnEXITClick(TObject *Sender)
{
Close();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormActivate(TObject *Sender)
{
IsMemo2();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::btbSort1Click(TObject *Sender)
{
// вызов сортировки методом пузырька
int Sr, Per, i, j, x, Ef;
Sr=0; Per=0; Ef=0; // Начальные значения параметров эффективности сортировки
IsMemo2(); // из Memo2 в массив m
for(j=0; j<kol-1; j++)
for(i=0; i<kol-1; i++)
{ Sr++;
if(m[i+1]<m[i])
{ x=m[i];
m[i]=m[i+1];
m[i+1]=x;
Per=Per+3; }
}
Ef = Sr + 10*Per; // расчет эффективности
Edit1->Text=IntToStr(Sr); // Выводим параметры сортировки
Edit2->Text=IntToStr(Per);
Edit3->Text=IntToStr(Ef);
VListBox2(); // передача чисел из массива m в ListBox2
}
//---------------------------------------------------------------------------
void __fastcall TForm1::btbSort2Click(TObject *Sender)
{
// вызов сортировки локальным минимумом
int Sr, Per, x, Ef;
Sr=0; Per=0; Ef=0; // обнуляем характеристики алгоритма
IsMemo2(); // из Memo2 в массив m
int i, j;
int min, imin;
// Главный цикл до n-1, а не n, т.к. последний остающийся элемент - максимальный
for (i=0; i<kol-1; i++)
{
min=m[i]; imin=i;
for (j=i+1; j<kol; j++)
{
Sr++;
if(m[j]<min)
{ min=m[j];
imin=j;
Per++; }
}
x=m[i];
m[i]=min;
m[imin]=x;
Per=Per+3;
}
Ef = Sr + 10*Per; // расчитываем эффективность
Edit4->Text=IntToStr(Sr);
Edit5->Text=IntToStr(Per);
Edit6->Text=IntToStr(Ef);
VListBox2(); // передача чисел из массива m в ListBox2
}
//---------------------------------------------------------------------------
void __fastcall TForm1::btbSort3Click(TObject *Sender)
{
// вызов сортировки Шелла
int Sr, Per, x, Ef;
Sr=0; Per=0; Ef=0;
IsMemo2(); // из Memo2 в массив m
int d = kol, i, j;
while (d > 0)
{
d /= 2;
/* Цикл представляет собой один "пузырьковый" проход по всем группам элементов
на данном шаге. Кроме того, здесь, он выполняется и в конце, когда d=1,
позволяя избежать результирующей сортировки */
for (i=d; i<kol; i++)
{
int tmp = m[i];
for (j=i-d;(j>=0)&&(m[j]>tmp); j-=d)
{
m[j+d] = m[j]; Sr++;
}
m[j+d] = tmp; Per++;
}
}
Ef = Sr + 10*Per;
Edit7->Text=IntToStr(Sr);
Edit8->Text=IntToStr(Per);
Edit9->Text=IntToStr(Ef);
VListBox2(); // передача чисел из массива m в ListBox2
}
//---------------------------------------------------------------------------
void __fastcall TForm1::btbPoisk0Click(TObject *Sender)
{
// прямой поиск в исходном массиве
int i, x, Sr;
IsMemo2(); // из Memo2 в массив m
Sr=0;
x=StrToInt(Edit10->Text);
for (i=0;i<=kol-1;i++)
{ Sr++;
if (x==m[i])
{ Edit15->Text="Искомое число "+Edit10->Text+ " найдено в позиции "+IntToStr(i+1);
goto Vyxod;
}
}
Edit15->Text="Искомое число "+Edit10->Text+ " отсутствует";
Vyxod:
Edit11->Text=IntToStr(Sr);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::btbPoisk1Click(TObject *Sender)
{
// прямой поиск в отсортированном массиве
int i, x, Sr; // число сравнений
IsMemo2(); // из Memo2 в массив m
Sr=0;
btbSort3Click(Sender); // сортировка массива m по методу Шелла
x=StrToInt(Edit10->Text);
for (i=0;i<kol-1;i++)
{ Sr++;
if (x==m[i])
{ Edit15->Text="Искомое число "+Edit10->Text+ " найдено в позиции "+IntToStr(i+1);
goto Vyxod;
}
}
Edit15->Text="Искомое число "+Edit10->Text+ " отсутствует";
Vyxod:
Edit12->Text=IntToStr(Sr);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::btbPoisk2Click(TObject *Sender)
{
//Бинарный поиск в отсортированном массиве
int i, Sr, x,
l, // индекс верхней границы часитичного массива
u, // индекс нижней границы часитичного массива
s;// индекс середины
IsMemo2(); // из Memo2 в массив m
Sr=0;
btbSort3Click(Sender); // сортировка массива m по методу Шелла
x=StrToInt(Edit10->Text);// Запрос на поиск
l=0;
u=kol-1;
while (true) // "бесконечный" цикл
{s=(l+u)/2; // определяем середину отрезка
if (m[s]<x) // определяем в какой части искать дальше
{l = s + 1;
Sr++;}
else
{Sr++;
if (m[s] == x) // если найден
{Edit15->Text="Искомое число "+Edit10->Text+ " найдено в позиции "+IntToStr(s+1);
goto Vyxod;}
else
{Sr++;
if (m[s]>x)
u=s-1;}
}
}
Edit15->Text="Искомое число "+Edit10->Text+ " отсутствует";
Vyxod:
Edit13->Text=IntToStr(Sr);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::btbPoisk3Click(TObject *Sender)
{
// вызов Интерполяционного поиска
int i, Sr, x,
iA, // индекс верхней границы часитичного массива
iB, // индекс нижней границы часитичного массива
iSred;// индекс середины
IsMemo2(); // из Memo2 в массив m
Sr=0;
btbSort3Click(Sender); // сортировка массива m по методу Шелла
x=StrToInt(Edit10->Text);// Запрос на поиск
iA = 0;
iB = kol-1;
while(iB >= iA) // пока не просмотрим весь
{
i = iA+(iB-iA)*(x-m[iA])/(m[iB]-m[iA]); // точка просмотра
Sr++;
if(x < m[i]) iB = i-1; // определяем направление поиска
else
{ Sr++;
if(x > m[i]) iA = i+1;
else
{Edit15->Text="Искомое число "+Edit10->Text+ " найдено в позиции "+IntToStr(i+1); // найден элемент
goto Vyxod;}
}
}
Edit15->Text="Искомое число "+Edit10->Text+ " отсутствует";
Vyxod:
Edit14->Text=IntToStr(Sr);
}
//---------------------------------------------------------------------------
Заключение
В результате выполнения курсовой работы были реализованы три метода сортировки и три метода поиска. Для каждого метода выводятся параметры эффективности работы алгоритма.
Результаты выполнения курсовой работы показывают значимость знания различных методов сортировки и поиска и умение применять их в зависимости от ситуации.
Список литературы
1.Ахо А. Структуры данных и алгоритмы: учеб. пособ. / А. Ахо, Д.Э. Хопкрофт, Д. Ульман; пер. с англ. - М.: Издательский дом "Вильяме", 2000.2.Ахтамова С.С. Алгоритмы поиска данных // Современные наукоемкие технологии. - 2007. - № 3 - С. 11-14.3.Бакнелл Джулиан М. Фундаментальные алгоритмы и структуры данных в Delphi. Пер. с англ./Джулиан М. Бакнелл. - СПб: ООО «ДиаСофтЮП», 2003.- 560 с.4.Вирт Н. Алгоритмы и структуры данных: Пер. с англ. М.: Мир, 2001.5.Гагарина Л.Г. Алгоритмы и структуры данных: учеб. пособие/ Л.Г. Гагарина, В.Д. Колдаев. - М.: Финансы и статистика; ИНФРА-М, 2009. -304 с.6.Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология / Пер с англ. И.В. Романовского. - СПб.: Невский диалект; БХВ-Петербург, 2003 г. - 654 с.7.Голицына ОЛ., Попов И.И. Основы алгоритмизации и программирования: учеб. пособие. - 3-е изд., испр. и доп. - М: ФОРУМ, 2008. - 432 с8.ГОСТ «Единая система программной документации» (ЕСПД): ГОСТ 19.701-90.9.Информатика : учебник для вузов / под ред. Н.В. Макаровой. - М. : Финансы и статистика, 2007. - 768 с.10.Кнут, Д. Искусство программирования. Т. 3. Сортировка и поиск. - М.: Издательский дом «Вильямс», 2003.11. Колдаев В. Д. Основы алгоритмизации и программирования: Учебное пособие / Под ред. проф. Л. Г. Гагариной. - М.: ИД «ФОРУМ»: ИНФРА-М, 2006. - 416c.12. Кормен, Томас X., Лейзерсон, Чарльз И., Ривсст, Рональд Л., Штайн, Клиффорд. Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. - М. : Издательский дом "Вильяме", 2005. - 1296 с.13. Королев, Л. Н. Информатика. Введение в компьютерные науки / Л. Н. Королев, А. И. Миков. - М.: Высш. шк., 2003.14. Макконнелл Дж. Основы современных алгоритмов. Москва: Техносфера, 2004. - 368с. 15. Мейн М. Структуры данных и другие объекты в С++ / М. МеЙн, У Савитч; пер. с англ. - М.: Издательский дом "Вильяме", 2002.16. Николаев В. И., Иванова И. В. Теория алгоритмов: Текст лекций. - СПб.: СЗТУ, 1995.17. Николаев В. И., Чалов Д. В., Сиоирев В. Н. Информатика. Теоретические основы: Учеб. пособие. - СПб.: СЗТУ, 2002.18.Островейковский В. А. Информатика: Учебник для вузов. - М.: Высш. шк.. 2000.19. Сотанин С. В. Численный анализ методов сортировки. [Электронный ресурс.- метод доступа: http://conf.sfu-kras.ru/sites/mn2011/thesis/s31/s31_01.pdf]20. Хусаинов Б.С. Структуры и алгоритмы обработки данных: примеры на языке Си: учеб. пособ. / Б.С. Хусаинов. - М.: Финансы и статистика, 2004.21. Шень А. Программирование: Теоремы и задачи / А. Шень. - М.: МЦНМО, 2004.
30