Сортировка

Автор работы: Пользователь скрыл имя, 21 Мая 2013 в 15:16, лабораторная работа

Описание работы

Исследование метод сортировки “Сортировка выбором”.
2.
Требовании к выполнению работы
Генерация: Случайная генерация указывающий тип элементов, размер массива,
диапазон значений элементов, количество случайных массивов
рассматривающих по каждому запусканию программу.
Эффективност: Время выполнения, операция сравнений, перемещения элементов
3.

Скачать архив (479.25 Кб) Сколько стоит заказать работу?

Файлы: 1 файл

ПАА №1.pdf

— 566.08 Кб (Скачать файл)

Page 1

Министерство образования и науки РФ Санкт-Петербургский государственный
электротехнический университет “ЛЭТИ”
кафедра МОЭВМ
Лабораторная работа №1 по дисциплине
«Построение и Анализ Алгоритмов»
на тему:
“Сортировка”
Выполнил: Отохагуа И.
Факультет КТИ
Группа №1303
Преподаватель: Романенка Д.А.
Санкт-Петербург
2013

Page 2

1. Вариант лабораторной работы
Исследование метод сортировки “Сортировка выбором”.
2.
Требовании к выполнению работы
Генерация: Случайная генерация указывающий тип элементов, размер массива,
диапазон значений элементов, количество случайных массивов
рассматривающих по каждому запусканию программу.
Эффективност: Время выполнения, операция сравнений, перемещения элементов
3.
Краткое сведение об алгоритме
В компьютерной науке, сосртираовак выбором
является алгоритм сортировки, в частности, на
месте сравнению рода. Он имеет O (n2) время
сложности, что делает его неэффективным на
больших списках, и в целом выполняет хуже, чем
подобного рода вставки. Выбор рода отличается
своей простотой, а также имеет преимущества по
сравнению с производительностью более сложные
алгоритмы в определенных ситуациях, особенно
там, где вспомогательной памяти ограничен.
Алгоритм разбивает входной список на две
части: подсписок элементов уже отсортированы,
который строится слева направо и находится в
конце, и подсписок элементов, подлежащих
сортировке, занимающего остальную часть списка.
Первоначально, отсортированный подсписок пуст, а
несортированные подсписок является весь список
входе.Алгоритм поступления, всегда найти
следующее наибольшее (или наименьшее, в
зависимости от сортировки) элемент и обмен его с
последним элементом массива.
3.
Анализ алгоритма
Выбор рода не трудно анализировать по
сравнению с другими алгоритмами сортировки, так
как ни одна из петель зависит от данных в массиве.
Выбор низкий элемент требует проверки всех п
элементов (это занимает п - 1 сравнений), а затем
замена его на первое место. Поиск следующего
низкий элемент требует сканирования остальных п -
1 элементов и так далее, для (п - 1) + (п - 2) + ... + 2 +
1 = п (п - 1) / 2 ∈ Θ (n2) сравнений (см. арифметической прогрессии). Каждый из этих
сканирования требуется один своп для п - 1 элементов (последний элемент уже на
месте)
2

Page 3

4
Исходный текст программы
List.h
ПостАлГ_Лаб1
Created by Imhoisili Otokhagua on 22/02/2013.
Copyright (c) 2013 Imhoisili Otokhagua. All rights reserved.
#ifndef _____________1__List__
#define _____________1__List__
class ARR{
public:

long *s;

ARR *next;

ARR* addARR(int,int);

void print(int);

void printSingle(int,ARR*);
};//*head,*newOne;
#endif /* defined(_____________1__List__) */
3
List.cpp
ПостАлГ_Лаб1
Created by Imhoisili Otokhagua on 22/02/2013.
Copyright (c) 2013 Imhoisili Otokhagua. All rights reserved.
#include "List.h"
#include <iostream>
using namespace std;
ARR *head,*newOne;
ARR* ARR::addARR(int size,int r){

ARR *trail;

if (head==NULL){

head=new ARR;

head-‐>s=new long[size];

srand(r);

for (int i = 0; i < size; i++){

head-‐>s[i]=1+(rand()%50);

}

head-‐>next=NULL;

}else{

newOne=head;

while (newOne-‐>next!=0)

newOne=newOne-‐>next;

trail=new ARR;

trail-‐>s=new long[size];

srand(r);

for(int i=0;i<size;i++){

trail-‐>s[i]=1+(rand()%50);

}

trail-‐>next=NULL;

newOne-‐>next=trail;

}

return head;
}

Page 4

List.cpp
ПостАлГ_Лаб1
Created by Imhoisili Otokhagua on 22/02/2013.
Copyright (c) 2013 Imhoisili Otokhagua. All rights reserved.
void ARR::print(int size){

ARR *node;

cout<<endl;

for(node=head;node!=NULL;node=node-‐>next){

for(int i=0;i<size;i++)cout<<node-‐>s[i]<<" ";

cout<<endl<<endl;

}
}
void ARR::printSingle(int size,ARR *m){

ARR *nNode;

cout<<endl;

nNode=m;

for(int i=0;i<size;i++) cout<<nNode-‐>s[i]<<" ";
}
main.cpp
ПостАлГ_Лаб1
Created by Imhoisili Otokhagua on 22/02/2013.
Copyright (c) 2013 Imhoisili Otokhagua. All rights reserved.
#include <iostream>
#include <ctime>
#include <cstdlib>
#include "List.h"
using namespace std;
//Selection sort
int SC(long h[],int size) {
int n=0;
int swaps=0;

cout<<endl<<endl;

clock_t s;
double SelecDur=0;
s=clock();

for (int i=0; i<size; i++) {
int iSmall=i;
for (int j=i+1; j<size; j++) {
if (h[iSmall]>h[j]) {
iSmall=j;
swaps++;
}
n++;
}
swap(h[iSmall], h[i]);
}
SelecDur=(clock()-‐s)/(double)CLOCKS_PER_SEC;
cout<<"Execution time: "<<SelecDur<<endl;
for (int i=0; i<size; i++) {
cout<<h[i]<<" ";
}
cout<<"\nNumber of comparisons: "<<n;
return swaps;
}
4

Page 5

main.cpp
ПостАлГ_Лаб1
Created by Imhoisili Otokhagua on 22/02/2013.
Copyright (c) 2013 Imhoisili Otokhagua. All rights reserved.
int main()
{

ARR *mandy,*temp = nullptr;

mandy=new ARR;

int option=0;int num=0;int randNum=0;int randLength=0;int comp=0;

cout<<"Enter number of arrays: \n";

cin>>num;
options:

//cout<<"\n1) Generate arrays of random lengths less than 20";

cout<<"\n1) Generate arrays of equal lengths chosen randomly by computer";

cout<<"\n2) Generate arrays of equal lengths chosen by user\n";

cin>>option;

if (option>=3||option<1){

cout<<"Wrong input choice, Please try again\n";

goto options;

}

if(option==1){

srand(time(0));

randNum=(rand()%(1000-‐900)+900);

randLength=(rand()%(20-‐5)+5);

for(int i=0;i<num;i++){

mandy=mandy-‐>addARR(randLength,randNum);

randNum=randNum-‐23;

}

mandy-‐>print(randLength);

cout<<endl;

}

if(option==2){

srand(time(0));

randNum=(rand()%(1000-‐900)+900);

cout<<"Enter length of array: \n";

cin>>randLength;

for(int i=0;i<num;i++){

mandy=mandy-‐>addARR(randLength,randNum);

randNum=randNum-‐23;

}

mandy-‐>print(randLength);

cout<<endl;

}
cout<<"Selection sort Algorithm\n";
for(int i=0;i<num;i++){
comp=SC(mandy-‐>s,randLength);
cout<<"\nNumber of swaps: "<<comp<<endl;
comp=0;
mandy=mandy-‐>next;
}
mandy=temp;
}
5

Page 6

5.
Тестовые примеры
6

Page 7

6.
Анализ примеры
Первый пример:
Тип элементов
Количество массивов
Количество
элементов по одному
массиву
Диапазон значений
элементов
Целые числа
5
50
53
Массив
1
2
3
4
5
Время
выполнения
Количество
сравнений
Количество
перемещений
9е-‐06
9е-‐06
7е-‐06
9е-‐06
8е-‐06
1225
1225
1225
1225
1225
46
49
42
48
45
Второй пример:
Тип элементов
Количество массивов
Количество
элементов по одному
массиву
Диапазон значений
элементов
Целые числа
3
85
53
Массив
1
2
3
Время
выполнения
Количество
сравнений
Количество
перемещений
1.9е-‐05
1.7е-‐05
1.9е-‐05
3570
3570
3570
77
75
81
Замечание: При больших количествах элементов массива требуется больше времени
выполнения сортировки.
Показываем отношение между количеством элементов массива и временем выполнения
сортировки
7

Page 8

График А
График А показывает результат после выполнений сортировки 5 случайных массивов
при увеличении их размер от 10 до 1000 элементов.
График Б
8

Page 9

График Б показывает результат после выполнения сортироки 1 массив при увеличении
его размер от 10 до 1000 элементов
Вывод:
В лабораторной работе мы исследовалы метод сортировки “Сортировка выбором” и можем
говорить, по нашим примерам, что:
• Алгоритм работает быстро в зависимости от количества элементов в массиве, то есть тем
меньше количество элементов в массиве, чем меньше время выполнения сортировки и
наоборот
• Алгоритм тоже быстро работает в зависимости от количества перемещений.
Рассматриваем случае когда у нас несколько массивов одного размера. Хотим знать
какой из этих массивов наш алгоритм выполняет первую очередь. Сравниваем полученный
результат из примера. Мы видим, что из этих массивов если операция выполняется и один
массив имеет больше количество сравнений чем другие этот массив был сортирован
используя больше времени. Значит, что количество перемещений влияет время выполнения
дело в том, что оно означает оценку беспорядочности массива.
9

Информация о работе Сортировка