Отчёт (Архив готовых лабораторных работ для ИУ)

Московский государственный технический

университет им. Н.Э. Баумана.

Факультет «Информатика и управление»

Кафедра ИУ5. Курс «Основы информатики»

Отчет по лабораторной работе №7

«Сортировка одномерного числового массива»

г. Москва, 2008 г.

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

Цели работы:

- освоение методов обработки массивов на примере сортировки массива;

- знакомство с алгоритмами сортировки;

- использование динамических массивов;

-инициализация массивов с помощью датчика случайных чисел;

- оценка быстродействия алгоритма.

Задание.

Отсортировать числовой массив методом выбора максимального (минимального) элемента и методом пузырькового всплытия. По окончании сортировки вывести отсортированный массив и количество сделанных сравнений и перестановок элементов.

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

Исследовать зависимость быстродействия от размера массива. Возможность изменения длины массива реализуйте с помощью динамического массива, а для его инициализации используйте датчик случайных чисел (см. Приложение 1). Результаты исследования выведите в виде отформатированной таблицы.

Разработка алгоритма

При выполнении работы обратите внимание на следующие требования и рекомендации:

1. Следует создать динамический массив. Размерность нединамического массива может быть только константой или константным выражением.

2. Автоматический контроль выхода индекса за границы массива не производится, поэтому надо следить за этим.

3. Имя массива является указателем на его нулевой элемент.

4. Освободить память, выделенную посредством new[], надо с помощью операции delete[].

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

Так если в массиве много повторяющихся элементов, то метод пузырькового всплытия справится быстрее. А если в массиве многие элементы уже стоят на своих местах, то быстрее справится метод min-max. Для этого надо добавить дополнительные условия.

Описание входных, выходных и вспомогательных данных:

Входные данные:

int n – кол-во перестановок;

int a – начало интервала;

int b – конец интервала;

int *arr1, *arr2 - указатели для хранения массивов;

cin >> sposob_vvoda – определяет способ задания массивов;

Выходные данные:

int sra – кол-во сравнений;

int per – кол-во перестановок;

Вспомагательные данные:

int max_i – индекс мах элемента;

int q – переменная для обмена значений;

int k – переменную k заводим чтоб не обнулить n при обратной сортировке;

Текст программы.

#include <iostream>

#include <ctime>

#include <cmath>

#include <cstdlib>

#include <iomanip>

#include "sortirovka.h"

using namespace std;

//---------------------------Прототипы функций---------------------------------------

void arr_generator(int *arr1, int *arr2, int n);//Заполняет два массива элементами

void output_array(int *arr, int n); //Вывод массива

//------------------------------НАЧАЛО ПРОГИ----------------------------------------

int main()

{

setlocale(0, "russian");

cout <<"Сортировка массивов\n";

//-----Создание массивов, инициализация, выделение памяти и заполнение элементами-----

int sra, per; //Кол-во перестановок и сравнений

int n, a, b; //кол-во эл. массива и интервал

int *arr1, *arr2; //указатели для хранения массивов

cout <<"Введите количество элементов массива ";

cin >> n;

try{

arr1= new int [n];

}catch(bad_alloc xa){

cout <<"Ошибка.\n";

system("Pause");

return 1;

}

try{

arr2= new int [n];

}catch(bad_alloc xa){

cout <<"Ошибка.\n";

system("Pause");

return 1;

}

char sposob_vvoda;

cout <<"Вы хотите ввести элементы массива с клавиатуры?(y/n) ";

cin >> sposob_vvoda;

if(sposob_vvoda == 'y')

{

arr_generator(arr1,arr2,n);

}else{

cout <<"Введите интервал ";

cin >>a >>b;

arr_generator(arr1, arr2, n, a, b);

}

output_array(arr1, n);

cout <<"\n\n";

//----------------Метод максимума----------------------------------

ma_sort(arr1, n, sra, per);

cout <<"Метод максимума.\nРезультат получен за " <<per <<" перестановок и " <<sra cout <<" сравнений\n";

output_array(arr1, n);

cout <<"\n\n";

//----------------Метод пузырькового всплытия--------------------------

puz_sort(arr2, n, sra, per);

cout <<"Метод пузырькового всплытия.\nРезультат получен за " << per <<" перестановок и " <<sra cout <<" сравнений\n";

output_array(arr2, n);

cout <<"\n\n";

//----------------Для отсортированного массива---------------------------

cout <<"Для отсортированного массива\n";

ma_sort(arr1, n, sra, per);

cout <<"Метод максимума.\nРезультат получен за " <<per <<" перестановок и " <<sra cout <<" сравнений\n";

puz_sort(arr2, n, sra, per);

cout <<"Метод пузырькового всплытия.\nРезультат получен за " << per <<" перестановок и " <<sra cout <<" сравнений\n";

cout <<"\n";

//------------------Для обратного массива---------------------------------

cout <<"Для обратного массива:\n";

int max_i, q, k= n; //переменную k заводим чтоб не обнулить n

sra= per= 0;

for(int j= 0; j < k; k--){

max_i= 0;

for(int i= 1; i < k; i++){

sra++;

if(arr1[i] < arr1[max_i]) max_i= i;

}

if(arr1[k-1] != arr1[max_i]){

per++;

q= arr1[k-1];

arr1[k-1]= arr1[max_i];

arr1[max_i]= q;

}

}

cout <<"Метод максимума.\nРезультат получен за " <<per <<" перестановок и " <<sra cout <<" сравнений\n";

output_array(arr1, n);

k= n;

sra= per= 0;

for(int j= 0; j < k; k--){

for(int i= 0; i < k-1; i++){

sra++;

if(arr2[i] < arr2[i+1]){

per++;

q= arr2[i+1];

arr2[i+1]= arr2[i];

arr2[i]= q;

}

}

}

cout <<"Метод пузырькового всплытия.\nРезультат получен за " << per <<" перестановок и " <<sra cout <<" сравнений\n\n\n";

output_array(arr2, n);

//-----------------------------Часть II-------------------------------------

a= arr1[1];

b= arr2[n];

delete [] arr1;

delete [] arr2;

cout <<"Количество " <<setw(20) <<"Метод максимума" <<setw(22) <<"Метот пузырька\n";

cout <<"элементов" <<setw(13) <<"перест." <<setw(10) <<"сравн." <<setw(12) <<"перест." cout <<setw(11) <<"сравн.\n";

//-----------------------------Таблица-----------------------------------------

for(int i= 1;i < (n*100);i+= i){

try{

arr1= new int [i];

}catch(bad_alloc xa){

cout <<"Нет места.\n";

return 1;

}

try{

arr2= new int [i];

}catch(bad_alloc xa){

cout <<"Нет места.\n";

return 1;

}

arr_generator(arr1, arr2, i, a, b);

ma_sort(arr1, i, sra, per);

cout <<fixed <<setw(6) <<i <<setw(14) <<per <<setw(10) <<sra;

puz_sort(arr2, i, sra, per);

cout <<setw(12) <<per <<setw(10) <<sra <<"\n";

delete [] arr1;

delete [] arr2;

}

//------------------------------------The End----------------------------------

system("Pause");

return 0;

}

//-----------------------------------Функции---------------------------------

void arr_generator(int *arr1, int *arr2, int n) //заполняет два массива элементами

{

cout << "Введите элементы\n";

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

cin >> arr1[i];

arr2[i]= arr1[i];

}

}

void output_array(int *arr, int n) //Вывод массива

{

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

cout << arr[i] <<" ";

}

cout << "\n";

}

Файл sortirovka.

sortirovka

void ma_sort(int *arr, int n, int &sra, int &per); //Cортировка min(max)

int puz_sort(int *arr, int n, int &sra, int &per); //Пузырьковый метод(возвращает 1 если сортировка закончилась раньше, срока иначе 0)

int randiapazon(int a, int b); //генерирует гисла от а до b

void arr_generator(int *arr1, int *arr2, int n, int a, int b); //Заполнение массива случайными числами

void ma_sort(int *arr, int n, int &sra, int &per) //Cортировка max

{

int max_i, q;

sra= per= 0;

for(int j= 0; j < n; n--){

max_i= 0;

for(int i= 1; i < n; i++){

sra++;

if(arr[i] > arr[max_i]) max_i= i;

}

if(arr[n-1] != arr[max_i]){

per++;

q= arr[n-1];

arr[n-1]= arr[max_i];

arr[max_i]= q;

}

}

}

int puz_sort(int *arr, int n, int &sra, int &per) //Пузырьковый метод

{

int q;

sra= per= 0;

for(int j= 0; j < n; n--){

q=0;

for(int i= 0; i < n-1; i++){

sra++;

if(arr[i] > arr[i+1]){

per++;

q= arr[i+1];

arr[i+1]= arr[i];

arr[i]= q;

q= 1;

}

}

if(q == 0) return q;

}

return 1;

}

int randiapazon(int a, int b)

{

return a+(b-a+1)*rand()/RAND_MAX;

}

void arr_generator(int *arr1, int *arr2, int n, int a, int b) //Заполнение массива случайными элементами

{

srand( (unsigned int)time(NULL) );

rand( );

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

arr1[i]= randiapazon(a, b);

arr2[i]= arr1[i];

}

}

Анализ результатов