Размещено на http://www.allbest.ru/

"Приднестровский государственный университет им. Т.Г. Шевченко"

Рыбницкий филиал

Кафедра физика, математика и информатика

Курсовая работа

по дисциплине: "Структуры и алгоритмы обработки данных"

на тему: " Сортировка выбором связанного списка"

Выполнил: Кравец С.

Проверила: Глазова Н.С.

г. Рыбница 2012 г.

Содержание

Введение

1. Сортировка выбором связанного списка

2. Реализация приложения "сортировка выбором связанного списка"

2.1 Экспериментальный раздел

Заключение

Список литературы

Приложение

Введение

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

Один из них "Сортировка выбором связанного списка". Цель курсовой работы является изучение сортировки выбора на примере связанного списка.

Задачи:

· Изучить теоретические аспекты для реализации приложения " Сортировка выбором связанного списка".

· Реализовать алгоритм "Сортировка выбором связанного списка".

· Провести анализ работоспособности программного продукта реализующего "Сортировка выбором связанного списка".

1. Сортировка выбором связанного списка

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

Основным критерием для классификации алгоритмов сортировки является их быстродействие. При сортировке выполняются два типа операций - сравнение ключей и перестановка элементов (в случае со связными списками - переназначение указателей). Если в массиве n элементов, то алгоритм считается хорошим, если число перестановок равно произведению числа элементов массива n на логарифм этого числа log(n). Например, стандартная пузырьковая сортировка требует числа перестановок, равного квадрату от n. алгоритм программный множество

Методы сортировки можно разбить на три основных класса:

· сортировка включениями;

· сортировка выбором;

· сортировка обменом.

Принцип, лежащий в основе первого класса, заключается в том, что массив разбивается на две половины - итоговую и входную. Берется элемент из входной половины и вставляется в итоговую в порядке сортировки. Число перестановок элементов в общем случае равно квадрату от n.

В случае сортировки выбором алгоритм таков: берется минимальный элемент массива и ставится в начало массива, и т.д. Число перестановок элементов в общем случае меньше, чем в первом случае, и будет равно произведению числа элементов массива на логарифм от этого числа. Быстрая сортировка относится ко второму классу.

Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке.

Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м.

На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на Рис.1

Рис.1. Последовательность шагов.

Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] (выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.

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

n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * (n2+n) = Theta(n2).

Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки растет квадратично относительно количества элементов.

Алгоритм не использует дополнительной памяти: все операции происходят "на месте".

Рассмотрим последовательность из трех элементов, каждый из которых имеет два поля, а сортировка идет по первому из них.

Рис.2. Сортировка последовательности по первому полю.

Результат ее сортировки можно увидеть уже после шага 0, так как больше обменов не будет. Порядок ключей 2a, 2b был изменен на 2b, 2a, так что метод неустойчив.

Если входная последовательность почти упорядочена, то сравнений будет столько же, значит, алгоритм ведет себя неестественно.

2. Реализация приложения "сортировка выбором связанного списка"

Постановка задачи

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

· Ввод случайных чисел.

· Отсортировка по возрастанию с помощью программы.

Описание технологии разработки

Используем структуру:

struct list.

Функция, выводящая список на экран:

PrintList.

Список формируется с помощью случайных чисел, с помощью функции:

randomize.

В данной программе использовали следующие переменные и указатели.

int n=0; int min=MAXINT; int i; int buf; list *head; list *p; list *tmp; list *k; list *j;

Определение размера списка осуществляется вручную.

cin"n;

Далее происходит формирование самого списка.

for(i=0; i<n; i++)

p->next=new list;

p=p->next;

p->name=random(100)+1;

p->next=NULL;

На данном этапе программного продукта происходит вывод списка на экран.

PrintList(p,head,n);

Далее сортируем список.

for(k=head; k; k=k->next)

min=MAXINT;

for(j=k; j; j=j->next)

if(j->name < min)

tmp = j;

min=j->name;

Меняем местами самый минимальный, и текущий элементы списка.

buf=k->name;

k->name=min;

tmp->name=buf;

Функция вывода списка на экран.

void PrintList(list* p, list* head, int n)

p=head;

while(p != 0)

p=p->next;

2.1 Экспериментальный раздел

На рисунке 3 изображен ввод желаемого количества элементов списка. После сформирования списка случайных чисел, осуществляется первый цикл.



Рис.3 Ввод количества элементов.

На рисунке 4 изображены следующие два шага преобразования списка. Где видно, что число 21 меняется местами с числом 39.

Рис.4 Пошаговое формирование списка.

На рисунке 5 изображен конечный результат данной программы. Отсортированный список.



Рис.5.Конечный результат.

Заключение

В ходе выполнения данной курсовой работы были рассмотрены проблемы реализации приложения "Сортировка выбором связанного списка", изучен теоретический аспект и получен практические навыки работы.

Получен практический опыт работы с такими возможностями языка программирования С++,как сортировка выбором связанного списка.

В результате выполнения данной курсовой работы были выполнены следующие задачи:

· Изучены теоретические аспекты для реализации приложения " Сортировка выбором связанного списка".

· Разработан алгоритм работы приложения " Сортировка выбором связанного списка".

· Создан программный продукт " Сортировка выбором связанного списка" на языке С++.

· Проведен анализ работоспособности программного продукта реализующего " Сортировка выбором связанного списка".

Список литературы

1. Ананий В. Левитин Глава 3. Метод грубой силы: Сортировка выбором.

2. Гилберт Стивен, Макартни Билл. Самоучитель Visual C++ 6 в примерах. - К.: ООО "ТИД ДС", 2003. - 496с.

3. Лабораторный практикум. Кузьмина Е.А., Минасов Ш.М., Тархов С.В., варианты индивидуальных заданий: Карчевская М.П., Рамбургер О.Л.

4. Уэйт М., Прата С., Мартин Д. Язык Си. Руководство для начинающих.

5. Шиманович Е.Л. C/C++ в примерах и задачах. - Минск: Новое знание, 2004, - 528с.

6. Шмидский Я.К. Программирование на языке С/С++. Самоучитель. -М.: Вильямс, 2004. -352с.

7. Роберт Седжвик Часть III. Глава 6. Элементарные методы сортировки.

8. Касаткин А.И., Вальвачев А.Н. Профессиональное программирование на языке Си: От Турбо Си к С++. - Минск: Вышэйшая школа, 1992. - 240с.

9. Николенко Д.В. Самоучитель по Visual C++. -СПб: Наука и техника, 2001.

Приложение

#include<conio.h>

#include<iostream.h>

#include<stdio.h>

#include<stdlib.h>

#include<values.h>

//__________________________STRUKTURA______________________

struct list

{

int name;

list *next;

};

//_________________________________________________________

void PrintList(list* p, list* head, int n);

int main()

{

randomize();

clrscr();

//________________________INICIALIZACIYA___________________

int n=0; //____________kolichestvo elementov spiska

int min=MAXINT; //____________minimal'nyi

int i; //____________schetchik cikla vivoda

int buf; //____________bufer poiska

list *head; //____________ukazatel' golovi spiska

list *p; //____________sam spisok

list *tmp; //____________bufer spiska

list *k; //____________schetchik cikla sortirovki

list *j; //____________schetchik cikla sortirovki

//___________________OPREDELENIE RAZMERA SPISKA____________

cout""Vvedite kolichestvo elementov\n";

cin"n;

n--;

//___________________SOZDAEM GOLOVU SPISKA_________________

p=new list;

head=p;

//___________________FORMIROVANIE SAMOGO SPISKA_____________

for(i=0; i<n; i++)

{

p->next=new list;

p=p->next;

p->name=random(100)+1;

}

p->next=NULL;

//___________________VIVOD SPISKA NA EKRAN___________________

cout""\n\n\nSformirovannii spisok\n\n";

PrintList(p,head,n);

//______________________SORTIRUEM SPISOK_____________________

cout""\n\n\nOtsortirovannii spisok\n\n";

for(k=head; k; k=k->next)

{

min=MAXINT; //__________opredeliaem minimal'nyi min=max

for(j=k; j; j=j->next) //__________proxod po spisku

{

if(j->name < min) //_________proverka minimal'nogo elementa

{

tmp = j;

min=j->name;

}

}

//___________meniaem mestami samii minimal'nyi i tekushii elementi spsiska

buf=k->name;

k->name=min;

tmp->name=buf;

getch();

cout""\n\n";

PrintList(p,head,n);

}

//_________________VIVOD OTSORTIROVANNOGO SPISKA___________

/*

cout""\n\n\nOtsortirovannii spisok\n\n";

PrintList(p,head,n);

getch();*/

return 0;

};

//_____________________FUNKCIA VIVODA SPISKA________________

void PrintList(list* p, list* head, int n)

{

p=head;

while(p != 0)

{

cout"p->name"" ";

p=p->next;

}

}

Размещено на Allbest.ru