Форум программистов, компьютерный форум CyberForum.ru

Как в одномерном массиве проводится сравнение и сколько времени потребовалось на выполнение программы - C++

Восстановить пароль Регистрация
 
Feytan
1 / 1 / 0
Регистрация: 09.12.2010
Сообщений: 93
16.05.2011, 13:17     Как в одномерном массиве проводится сравнение и сколько времени потребовалось на выполнение программы #1
Подскажите, как доделать программу:

Задание: Дан одномерный массив длиной N. Массив заполняется датчиком случайных чисел (лучше использовать любое распределение, кроме нормального).
Требуется:
1) отсортировать массив со случайными числами;
2) в отсортированный массив, вставить случайное число, чтобы он оставался отсортированным;
3) также на экране после выполнения программы должно появляться сообщение, о том, сколько сравнений элементов сделано программой;
4) также программа должна выдавать сколько времени потребовалось ПК на выполнение программы

Сделал толко 1 и 2 пункт, а как сделать 3 и 4 пункт незнаю, поэтому прошу о помощи...

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
#include <iostream>
#include<time.h>
using namespace std;
 
int main ()
{
        srand (time(NULL));
        int i, N, j, k;
        //Задаем количество элементов
        cout<<endl<<"Dlina massiva - N: "; //N - длина одномерного массива
        cin>>N;
        cout<<"\n";  
    if(N > 0)
    {
        //Резервируем место на диске под количество элементов
        int *a = new int[N+1];// резервируем память под массив на 1 элемент больше
 
 
        cout << "Vremennii massiv: " << endl;
                for(i=0; i<N; i++)
        {
                a[i]=rand()%20;
                
                cout<<a[i]<<" ";
        }            
        cout<<"\n";
 
        for (int i = 0; i < N - 1; i++)
                {
                        for(j = N-1; j>i; j--)
                        if (a[j-1] > a[j])
                        {
                                swap(a[j], a[j-1]);
                        }           
        }
        cout << "Massiv otsortirovannii po vozrastaniu: " << endl;        
        for (int i = 0; i < N; i++)
                cout << a[i] << " ";
 
                cout<<endl<<"k: "; //k - случайное число
        cin>>k;
        cout<<endl;
 
                i=0;
                while ((a[i]<k) && (i<N)) //ищем место, куда поставить случайное число
                        i++;
                for (j=N; j>i; j--) //сдвигаем все элементы массива на 1 в конец, чтобы вставить случайный элемент
                        a[j]=a[j-1];
 
                a[i]=k; //вставляем на найденное место случайный элемент
 
                cout << "Konechnii massiv: " << endl;        
        for (int i = 0; i < N+1; i++)
                cout << a[i] << " ";
 
        delete [] a;
        }
        
        else cout<<"\n Chislo elementov ne mozhet byt <=0";
 
    system("pause");
    
        return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.05.2011, 13:17     Как в одномерном массиве проводится сравнение и сколько времени потребовалось на выполнение программы
Посмотрите здесь:

не могу понять как решить в одномерном массиве в c++ C++
Как найти среднее значение в одномерном массиве? C++
C++ Как в одномерном массиве проводится сравнение
C++ Как измерить, сколько времени считала программа?
Как посчитать сумму и разность чисел в одномерном массиве? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
16.05.2011, 15:55     Как в одномерном массиве проводится сравнение и сколько времени потребовалось на выполнение программы #2
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
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <iostream>
 
struct Compare {
  Compare() : count(0) {}
  bool operator()(int a, int b) {
    ++count;
    return a < b;
  }
  size_t count;
};
 
void QuickSort(int left, int right, int *array, Compare &compare) {
  int i = left, j = right;
  int pivot = array[(left + right) / 2];
 
  // partition
  while (i <= j) {
    while (compare(array[i], pivot))
      i++;
    while (compare(pivot, array[j]))
      j--;
    if (i <= j) {
      int tmp = array[i];
      array[i] = array[j];
      array[j] = tmp;
      i++;
      j--;
    }
  };
 
  // recursion
  if (left < j)
    QuickSort(left, j, array, compare);
  if (i < right)
    QuickSort(i, right, array, compare);
}
 
void BubbleSort(int left, int right, int *array, Compare &compare) {
  for (size_t i = left; i < right; ++i)
    for (size_t j = i; j <= right; ++j)
      if (!compare(array[i], array[j]))
        std::swap(array[i], array[j]);
}
 
int main(int argc, char *argv[]) {
  time_t start_time = clock();
  srand(time(NULL));
  size_t array_size = 10;
  int *array = new int[array_size];
  for (int i = 0; i < array_size; ++i)
    std::cout << (array[i] = rand() % 100) << " ";
  std::cout << std::endl;
  Compare comparator;
  QuickSort(0, array_size - 1, array, comparator);
 
  std::cout << "Compare count: " << comparator.count << std::endl;
 
  for (int i = 0; i < array_size; ++i)
    std::cout << array[i] << " ";
  std::cout << std::endl;
 
  time_t end_time = clock();
  std::cout << "Program took " << std::fixed
            << (float)(end_time - start_time) / (float)CLOCKS_PER_SEC
            << " seconds." << std::endl;
 
  return 0;
}
Feytan
1 / 1 / 0
Регистрация: 09.12.2010
Сообщений: 93
16.05.2011, 17:25  [ТС]     Как в одномерном массиве проводится сравнение и сколько времени потребовалось на выполнение программы #3
Чего много всего и сложновато все это, а можно ли попроще как-то?
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
16.05.2011, 17:52     Как в одномерном массиве проводится сравнение и сколько времени потребовалось на выполнение программы #4
Чем сложно-то?

Один функтор сравнения со счетчиком операций, две функции сортировки (quick и bubble), использующие функтор сравнения, ну и собственно программа, считающая количество действий и затраченное время. Чуть больше строк, чем у вас.

Для примера там две функции сортировки -- quick и bubble. Можете одну убрать. Проще не станет, но кода будет меньше. QuickSort в данной задаче более подходящ, поскольку количество сравнений зависит от исходных данных. С другой стороны, bubblesort всегда будет показывать одно и то же значение количества перестановок - (N*(N-1)) / 2, где N -- количество элементов в массиве.
Feytan
1 / 1 / 0
Регистрация: 09.12.2010
Сообщений: 93
16.05.2011, 18:05  [ТС]     Как в одномерном массиве проводится сравнение и сколько времени потребовалось на выполнение программы #5
Да, но в твоей программе кое-что исчезло - пункт 2, а именно: в отсортированный массив, вставить случайное число, чтобы он оставался отсортированным.
Я видел схожую программу, но я хочу попытаться доделать эту задачу. Хотя тот у кого я видел схожую задачу вроде тоже делал через QuickSort. Но я пока этим элементом неумею пользоваться, если можно что-то раскажите об этом. Ктому же она была как бы гибрид, часть от меня, часть от вашей, хотя точно неуверен.
Мои познания в с++ еще очень малы, вот почему я говорил что нельзяли попроще.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
16.05.2011, 19:03     Как в одномерном массиве проводится сравнение и сколько времени потребовалось на выполнение программы #6
Он не исчез. Я его не делал.
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
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <iostream>
 
struct Compare {
  Compare() : count(0) {}
  bool operator()(int a, int b) {
    ++count;
    return a < b;
  }
  size_t count;
};
 
void QuickSort(int left, int right, int *array, Compare &compare) {
  int i = left, j = right;
  int pivot = array[(left + right) / 2];
 
  // partition
  while (i <= j) {
    while (compare(array[i], pivot))
      i++;
    while (compare(pivot, array[j]))
      j--;
    if (i <= j) {
      int tmp = array[i];
      array[i] = array[j];
      array[j] = tmp;
      i++;
      j--;
    }
  };
 
  // recursion
  if (left < j)
    QuickSort(left, j, array, compare);
  if (i < right)
    QuickSort(i, right, array, compare);
}
 
void BubbleSort(int left, int right, int *array, Compare &compare) {
  for (size_t i = left; i < right; ++i)
    for (size_t j = i + 1; j <= right; ++j)
      if (!compare(array[i], array[j]))
        std::swap(array[i], array[j]);
}
 
void InsertSorted(int *array, size_t &array_size, int value) {
  size_t position;
  for (position = 0; position < array_size
       && array[position] < value; ++position);
  ++array_size;
  for (size_t i = array_size - 1; i > position; --i)
    array[i] = array[i - 1];
  array[position] = value;
}
 
int main(int argc, char *argv[]) {
  time_t start_time = clock();
  srand(time(NULL));
  size_t array_size = 10;
  int *array = new int[array_size + 1];
  for (int i = 0; i < array_size; ++i)
    std::cout << (array[i] = rand() % 100) << " ";
  std::cout << std::endl;
 
  Compare comparator;
  BubbleSort(0, array_size - 1, array, comparator);
  std::cout << "Compare count: " << comparator.count << std::endl;
 
  for (int i = 0; i < array_size; ++i)
    std::cout << array[i] << " ";
  std::cout << std::endl;
 
  InsertSorted(array, array_size, 55);
  for (int i = 0; i < array_size; ++i)
    std::cout << array[i] << " ";
  std::cout << std::endl;
 
  time_t end_time = clock();
  std::cout << "Program took " << std::fixed
            << (float)(end_time - start_time) / (float)CLOCKS_PER_SEC
            << " seconds." << std::endl;
 
  return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.05.2011, 12:14     Как в одномерном массиве проводится сравнение и сколько времени потребовалось на выполнение программы
Еще ссылки по теме:

C++ Не могу найти ошибку с подсчетом суммы элементов в интервале[a,b] в динамическом одномерном массиве массиве.
как вывести индекс в одномерном массиве C++
C++ Ускорить выполнение программы как минимум в два раза

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

Или воспользуйтесь поиском по форуму:
Feytan
1 / 1 / 0
Регистрация: 09.12.2010
Сообщений: 93
25.05.2011, 12:14  [ТС]     Как в одномерном массиве проводится сравнение и сколько времени потребовалось на выполнение программы #7
А вот мои конечные варианты:

Первый:
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
#include <iostream>
#include <cstdlib>
#include<windows.h>
 
using namespace std;
 
int compare_count = 0;
int compare(const void* a, const void *b) 
{
  ++compare_count;
  return (*(int*)a - *(int*)b);
}
 
int main ()
{
    
        DWORD t1, t2, d_time;
         
        srand (time(NULL));
        int i, N, j, k;
        t1 = GetTickCount();
        //Задаем количество элементов
        
        N=rand()%100;
        cout<<endl<<"Dlina massiva - N: " <<N <<endl; //N - длина одномерного массива
    
        cout<<"\n";  
        
        //Резервируем место на диске под количество элементов
        int *a = new int[N+1];// резервируем память под массив на 1 элемент больше
 
        int size = N;
 
 
        cout << "Vremennii massiv: " << endl;
                for(i=0; i<N; i++)
        {
                a[i]=rand()%100;
                
                cout<<a[i]<<" ";
        }            
        cout<<"\n";
        
        t1 = GetTickCount();
        
        qsort(a, size, sizeof(int), compare);
 
                cout << "\nOtsortirovannii massiv: " << endl;        
        for (i = 0; i < N; i++)
                cout << a[i] << " ";
                cout << "\n";
                
                cout << "\nKolichestvo sravnenii: " << compare_count <<endl;
 
        k=rand()%100;
        cout<< endl << "Sluchainoe chislo - k: " << k <<endl; //k - случайное число
        cout<< endl;
                i=0;
                while ((a[i]<k) && (i<N)) //ищем место, куда поставить случайное число
                        i++;
                for (j=N; j>i; j--) //сдвигаем все элементы массива на 1 в конец, чтобы вставить случайный элемент
                        a[j]=a[j-1];
 
                a[i]=k; //вставляем на найденное место случайный элемент
 
                cout << "Konechnii massiv: " << endl;        
        for (i = 0; i < N+1; i++)
                cout << a[i] << " ";
                cout << endl;
 
        t2 = GetTickCount();
        d_time = t2 - t1;
                        
                cout<<"\nVremia raboti: "<<d_time<<" milisek\n";
 
        delete [] a;
 
    system("pause");
    
        return 0;
}
Второй:

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
#include <iostream>
#include <cstdlib>
#include<windows.h>
 
using namespace std;
 
int compare_count = 0;
int compare(const void* a, const void *b) 
{
  ++compare_count;
  return (*(int*)a - *(int*)b);
}
 
int main ()
{
    
        DWORD t1, t2, d_time;
         
        srand (time(NULL));
        int i, N, j, k;
        
        //Задаем количество элементов
        
        cout<<endl<<"Dlina massiva - N: "; //N - длина одномерного массива
        
        cin>>N;
        
        cout<<"\n";  
        
    if(N > 0)
    {
        //Резервируем место на диске под количество элементов
        int *a = new int[N+1];// резервируем память под массив на 1 элемент больше
 
        int size = N;
 
 
        cout << "Vremennii massiv: " << endl;
                for(i=0; i<N; i++)
        {
                a[i]=rand()%100;
                
                cout<<a[i]<<" ";
        }            
        cout<<"\n";
        
        t1 = GetTickCount();
        
        qsort(a, size, sizeof(int), compare);
 
                cout << "\nOtsortirovannii massiv: " << endl;        
        for (i = 0; i < N; i++)
                cout << a[i] << " ";
                cout << "\n";
                
                cout << "\nKolichestvo sravnenii: " << compare_count <<endl;
 
        k=rand()%100;
        cout<< endl << "Sluchainoe chislo - k: " << k <<endl; //k - случайное число
        cout<< endl;
                i=0;
                while ((a[i]<k) && (i<N)) //ищем место, куда поставить случайное число
                        i++;
                for (j=N; j>i; j--) //сдвигаем все элементы массива на 1 в конец, чтобы вставить случайный элемент
                        a[j]=a[j-1];
 
                a[i]=k; //вставляем на найденное место случайный элемент
 
                cout << "Konechnii massiv: " << endl;        
        for (i = 0; i < N+1; i++)
                cout << a[i] << " ";
                cout << endl;
 
        t2 = GetTickCount();
        d_time = t2 - t1;
                        
                cout<<"\nVremia raboti: "<<d_time<<" milisek\n";
 
        delete [] a;
        }
        
        else cout<<"Chislo elementov ne mozhet byt <=0" << endl;
 
    system("pause");
    
        return 0;
}
Третий:

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
#include <iostream>
#include<time.h>
#include<windows.h>
 
using namespace std;
 
int main ()
{
        DWORD t1, t2, d_time;
        
        srand (time(NULL));
        
        int i, N, j, k;
        
        //Задаем количество элементов
        
        cout<<endl<<"Dlina massiva - N: "; //N - длина одномерного массива
        
        cin>>N;
        
        cout<<"\n"; 
         
    if(N > 0)
    {
         
        //Резервируем место на диске под количество элементов
        
        int *a = new int[N+1];// резервируем память под массив на 1 элемент больше
 
         cout << "Vremennii massiv: " << endl;
         for(i=0; i<N; i++)
        {
                a[i]=rand()%100;
                cout<<a[i]<<" ";
        }            
        cout<<"\n";
        cout<< endl;
        
        t1 = GetTickCount();
        
        int count=0;
        for (i = 0; i < N - 1; i++)
                {
                        for(j = N-1; j>i; j--)
                        if (a[j-1] > a[j])
                        {
                                swap(a[j], a[j-1]); count++;
                        }           
        }
        cout << "Otsortirovannii massiv: " << endl;        
        for (i = 0; i < N; i++)
                cout << a[i] << " ";
                cout<< endl;
                
        cout<<"\nKolichestvo perestanovok: "<<count;   
        cout<< endl;
        
        k=rand()%100;
        cout<< endl << "Sluchainoe chislo - k: " << k <<endl; //k - случайное число
        cout<< endl;
 
                i=0;
                while ((a[i]<k) && (i<N)) //ищем место, куда поставить случайное число
                        i++;
                for (j=N; j>i; j--) //сдвигаем все элементы массива на 1 в конец, чтобы вставить случайный элемент
                        a[j]=a[j-1];
 
                a[i]=k; //вставляем на найденное место случайный элемент
 
                cout << "Konechnii massiv: " << endl;        
        for (i = 0; i < N+1; i++)
                cout << a[i] << " ";
                cout <<"\n";
                
                t2 = GetTickCount();
                d_time = t2 - t1;
                        
                cout<<"\nVremia raboti: "<<d_time<<" milisek\n";
                
        delete [] a;
        }
        
        else cout<<"Chislo elementov ne mozhet byt <=0" << endl;
 
    system("pause");
    
        return 0;
}
Отличаются тем что в первом все задается случайно, даже длина массива, чего нет во втором и в третьем, а третье отличается от первого и второго другим способом сортировки массива и подсчета количества перестановок. А так эти три задачи почти полностью идентичны.

P.S. Если у кого есть еще какие варианты решения данной задачи пишите.

Всем спасибо за помощь в решении задачи.
Yandex
Объявления
25.05.2011, 12:14     Как в одномерном массиве проводится сравнение и сколько времени потребовалось на выполнение программы
Ответ Создать тему
Опции темы

Текущее время: 11:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru