Сортировка
Лабораторная работа, 21 Мая 2013, автор: пользователь скрыл имя
Описание работы
Исследование метод сортировки “Сортировка выбором”.
2.
Требовании к выполнению работы
Генерация: Случайная генерация указывающий тип элементов, размер массива,
диапазон значений элементов, количество случайных массивов
рассматривающих по каждому запусканию программу.
Эффективност: Время выполнения, операция сравнений, перемещения элементов
3.
Файлы: 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=
for(int i=0;i<size;i++)cout<<node-‐>
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)/(doubl
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)+9
randLength=(rand()%(20-‐5)+5)
mandy=mandy-‐>addARR(
randNum=randNum-‐23;
}
mandy-‐>print(randLength);
}
if(option==2){
srand(time(0));
randNum=(rand()%(1000-‐900)+9
cout<<"Enter length of array: \n";
cin>>randLength;
for(int i=0;i<num;i++){
mandy=mandy-‐>addARR(
randNum=randNum-‐23;
}
mandy-‐>print(randLength);
}
cout<<"Selection sort Algorithm\n";
for(int i=0;i<num;i++){
comp=SC(mandy-‐>s,
cout<<"\nNumber of swaps: "<<comp<<endl;
comp=0;
mandy=mandy-‐>next;
}
mandy=temp;
}
| 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