Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
0 / 0 / 0
Регистрация: 31.10.2018
Сообщений: 7
1

Сортировка массивов: оценить быстродействие разных методов

29.11.2018, 20:13. Просмотров 440. Ответов 1
Метки нет (Все метки)

Написать программу, в которой реализуются различные методы сортиров¬ки (для одинаковых массивов случайных чисел в диапазоне от 0 до 65535).
Каждый из методов сортировки, а также генерацию массива, необходимо реализовать в виде отдельной функции, принимающей на вход массив и его размер. Предусмотреть возможность работы программы с выводом отсортированного массива и без вывода.
Сравнить реализованные методы по быстродействию (только функции сортировки, т.е. без учёта времени на генерацию и вывод массива). Провести исследование быстродействия для различного числа элементов в массиве (n=10000, 30000, 90000, 270000, 810000). Результаты исследования отразить в отчете в виде таблицы значений T(n) и графика в двойном логарифмическом масштабе (т.е. log(T(n)) от log(n)).
Для оценки быстродействия можно использовать функцию clock() из библиотеки <time.h>, возвращающую число тактов процессора, прошедшее с момента запуска приложения. Возвращаемые значения функции clock() следует присваивать переменной типа unsigned long.

Методы: SelectionSort,HeapSort,CountingSort

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

Вот код, который таки смогла написать, буду очень благодарна, если поможете:


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
void creation (  int *& A , int  n )
{A= new int [n];}
void fill (int *A , int n )
{for (int i = 0 ; i <n ; i++)
{A [i]= rand ()% 65536 ;
 cout <<A [ i] <<endl ; }}
 
void selectionsort(int *& A , int n)
{
 
for ( int i = 0 ; i<n ; i++)
{int  k = i ;
int c= A[i];
{for ( int j = i+1 ; j<n ; j++ )
{if (A [j] < A [k])
{k = j ;
 
}
if (k != i)
{swap (A[k] , A [i]);
 
}
}
}
 
 
}
 
//cout <<"Result massiv:";
//for (int i=0 ; i<n ; i++)
    //{cout <<A[i]<<"  ";}//
}
 
void heapify(int *& A , int n , int i)
{ int largest = i ;
int l= 2*i +1 ;
int r = 2* i + 2 ;
if (l <n && A[l] > A[largest])
{largest = l ;}
if (r<n && A[r]> A[largest])
{largest= r;}
if (largest!= i )
{swap (A[i], A[largest]);
 heapify (A , n, largest);
}
}
void heapsort (int *& A , int n)
{
    int i;
    for ( i= n/2 -1 ; i>= 0 ;i--)
{heapify(A , n , i );}
 
 
for ( i= n-1 ; i>= 0 ;i--)
{swap (A[ 0] , A[i]);
heapify (A , i ,0);}
 
}
 
 
void Countersort (int *& A , int n , int r ,int lower)
{int i,j=0 ;
int m;
 
int counter [r];
 
for (i=0 ; i<n ; i++)
m= A[i ] - lower;
counter [m] ++ ;
i=0 ;
while (i <r)
{ flag :
A[j]= lower+i ;
j++;
counter [i] -- ;
    if (counter [i]> 0 )
    goto flag;
    i++;
}
}
 
 
void print (int *& A , int n)
{ int i  ;
for (i=0 ; i <n ; i++)
cout <<A[i]<<" ";
    cout << " \n";
}
 
 
 
 
int main() {
setlocale(LC_ALL , "russian");
    cout<<"Введите число "<<endl;
    int n ;
    int *A = 0 ;
    cin >>n ;
    creation  (A , n );
 
 
    fill (A ,  n ) ;
 
    selectionsort(A , n );
    heapsort(A , n);
 
 
    cout <<"\nEnter the lower and upper limit of the data to be entered:";
    int llimit , ulimit , range ;
    cin >>llimit >>ulimit;
    range = ulimit - llimit + 1 ;
 
    Countersort(A , n , range , llimit);
        print( A , n);
    return 0;
 
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.11.2018, 20:13
Ответы с готовыми решениями:

Сортировка массивов разных типов
пытаюсь создать игру на LibGDX. Столкнулся со следующей проблемой: графика изометрическая, а...

Не работает сортировка разных массивов
Надо отсортировать массивы, по убыванию возраста. Я их отсортировал, но почему они не...

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

Сборка проекта для разных клиентов. Использование единых методов с различными реализациями для разных
Здравствуйте уважаемые! Помогите пожалуйста. Есть проек, он состоинт из 10 подпроектов и...

1
443 / 329 / 172
Регистрация: 01.07.2015
Сообщений: 1,162
29.11.2018, 20:34 2
оценка времени работы функции
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.11.2018, 20:34

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

Метод выполнить в 11 разных потоках, соответственно для разных входных массивов
Здравствуйте, начал потихоньку разбираться в многопоточном программирование и не могу до конца...

Вызовы методов из разных потоков
Вдруг внезапно встал вопрос по вызову методов из разных потоков. Мне казалось что такой проблемы...

Замер времени из разных методов
Здравствуйте, нужна помощь, есть два метода, нужно замерить время в первом, и остановить во втором...

Обращение к ArrayList из разных методов
Добрый день. Подскажите, если в одном классе есть два метода и один метод создает ArrayList, то...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.