Лабораторная 1
.docxМИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра информационной безопасности
отчет
по лабораторной работе №1
по дисциплине «Алгоритмы и Структуры Данных»
Тема: Алгоритмы сортировки массивов
Студенты гр. 1363 |
|
Владимиров П.А. Афанасьев Д.К. |
Преподаватель |
|
Беляев А. В. |
Санкт-Петербург
2022
Цель работы: Ознакомление с алгоритмами сортировки линейных структур и оценкой эффективности данных алгоритмов.
Теоретические сведения
Упорядочение элементов множества в возрастающем или убывающем порядке называется сортировкой. Сортировка применяется при трансляции программ, при организации наборов данных на внешних носителях, при создании библиотек, каталогов, баз данных и т.д.
Сортировка выбором
Сортировка выбором состоит в том, что сначала в неупорядоченном списке выбирается и отделяется от остальных наименьший элемент. C этого этапа начинает формироваться упорядоченная часть списка. На каждом этапе из неотсортированной (остающейся) части извлекается наименьший элемент и присоединяется (справа) к отсортированной части, наращивая ее. Процесс продолжается до тех пор, пока все элементы не будут перенесены в отсортированную часть списка.
Сортировка подсчетом
Рассмотрим более эффективный метод сортировки подсчетом. Пусть в сортируемом массиве размещены целые числа из небольшого (до 10.000) диапазона значений. Введем вспомогательный одномерный массив длины равной диапазону значений и инициализируем его нулями. Первым проходом сортируемого массива подсчитаем кол-во элементов с каждым конкретным значений (храня счетчики во вспомогательном массиве), вторым проходом по вспомогательному массиву слева направо восстановим исходный массив сразу в отсортированном виде.
Сортировка Quicksort
Сортировка Quicksort состоит в том, что мы выбираем из всего массива один элемент, назовём его опорным. Затем разбиваем элементы массива таким образом, что элементы, меньшие опорного, помещаются перед ним, а большие или равные – после. Рекурсивно применяем первые два шага к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы.
Задание на лабораторную работу
Демонстрационные массивы
Провести сортировку массива (выданы по вариантам) тремя описанными методами.
Владимиров Пётр (5 вариант):
Выбором:
Подсчетом:
Quicksort:
Практическая часть
Мы разработали программу, выполняющую формирование и инициализацию массива длины N псевдослучайными и неотрицательными целыми числами, отображает первые десять и последних элементов массива, сортирует массив сортировкой выбора и подсчетом, отображает первые десять и последние десять элементы отсортированного массива, отображает время исполнения сортировки в миллисекундах.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void SelectionSort(int a[],int size) //сортировка выбором
{
for (int i = 0; i<size;i++){
for (int j = i + 1; j<size; j++){
if (a[i]>a[j]){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
void CountingSort(int unsort[],int sort[],int size) //сортировка подсчетом
{
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if (unsort[i] == j) sort[j]+=1;
}
}
int i = 0;
int k = 0;
int x, j;
while (i != size)
{
x = sort[i]; // =2
for (j = 0; j < x; j++)
{
unsort[k] = i;
k+=1;
}
i+=1;
}
}
int main()
{
const int size=150000;
int a[size];
int b[size];
int i;
srand(time(NULL));
for (int i = 0; i<size; i++){
a[i]=rand()%10000; //заполнение массивы случайными числами размером size
}
for (int i = 0; i < size; i++){
b[i]=0; //обнуление вспомогательного массива
}
printf("First 10\n");
for (int i = 0; i<10;i++){
printf("%d ",a[i]);
} //вывод первых 10 элементов неотсортированного массива
printf("\n");
printf("Last 10\n");
for (int i = 0; i<10;i++){
printf("%d ",a[size-i-1]); //вывод последних 10 элементов неотсортированного массива
}
clock_t start;
start = clock(); //начало времени отсчета сортировки
//SelectionSort(a,size);
CountingSort(a,b,size);
start=clock()-start; //конец времени отсчета сортировки
printf("\n");
printf("First 10\n");
for (int i = 0; i<10;i++){
printf("%d ",a[i]); //вывод первых 10 элементов отсортированного массива
}
printf("\n");
printf("Last 10\n");
for (int i = 10; i>0;i--){
printf("%d ",a[size-i]); //вывод последних 10 элементов отсортированного массива
}
printf("\n");
printf("Time of sort: ");
printf("%f",(double)start/CLOCKS_PER_SEC); //вывод времени сортировки массива
return 0;
}
Работа программы
Рисунок 1 – Сортировка выбором
Рисунок 2 – Сортировка подсчетом
Сравнение времени
Выбором |
Время |
||
Кол-во |
1 |
2 |
3 |
20000 |
1,468 |
1,504 |
1,488 |
40000 |
4,989 |
3,35 |
3,339 |
60000 |
6,657 |
6,568 |
6,652 |
120000 |
20,939 |
21,201 |
21,156 |
Подсчетом |
Время |
||
Кол-во |
1 |
2 |
3 |
25000 |
1,167 |
1,161 |
1,165 |
50000 |
4,714 |
4,734 |
4,711 |
75000 |
10,817 |
10,818 |
10,819 |
150000 |
43,825 |
43,791 |
43,753 |
