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

Сравнение алгоритмов поиска и сортировки - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Массив: функции getchar и putchar http://www.cyberforum.ru/cpp-beginners/thread862043.html
Задан массив. «Фамилия_стаж работы_зарплата». Преобразовать массив так: стаж работы увеличить на год, если он станет равен 10, то зарплату увеличить в 2 раза, если 15 – в 3 раза. Как такое сделать? Хотя бы примерно...
C++ Возврат итератора из функции в чем заключается проблема с возвратом итератора и как ее исправить? заранее спасибо за ответ =) (ожидаемый от программы ответ "Yes", но получаю "No") #include <iostream> #include <string> #include <vector> using namespace std; vector<string>::iterator f(vector<string> str) http://www.cyberforum.ru/cpp-beginners/thread862041.html
C++ Как подключить модуль ?
Microsoft Visual Studio 2012, куда нужно добавить .h и .cpp файлы? Я просто подключаю #include <что-то там.h>, а он пишет мол не удается открыть источник-файл
C++ GraphViz
Доброго времени суток! Нарисовалась проблема: Имеется матрица смежности, я могу вынести в отдельный файл (типа .txt), так вот вопрос стоит в том, чтобы программно подать эту матрицу в GraphViz. Как лучше\проще это сделать? Передать напрямую в конфиг файл сабжа или для начала передать матрицу в .txt файл а потом ее оттуда считать, и собственно как это сделать. Самая главная трудность...
C++ Количество цифр в массиве строк http://www.cyberforum.ru/cpp-beginners/thread862030.html
Помогите, очень нужна программа считающая количество цифр в массиве строк мне писали такую,но в ней много ошибок...// ?????????? ?????????? ????????? ???? ? ??????? ????? #include <stdafx.h/> #include "stdring" #include "iostream" #include "locale" using namespace std; int main() { string str;
C++ что значит static char? подскажите что означает static char ret; подробнее

Показать сообщение отдельно
Kaze
Сообщений: n/a
12.05.2013, 00:51     Сравнение алгоритмов поиска и сортировки
Дан массив из N целых элементов. Элементы генерируются случайным образом. Провести сравнительный анализ алгоритмов последовательного поиска с определением ближайших узлов и бинарного поиска с определением ближайших узлов при N = 1000, 10000, 100000, 1000000. Для сортировки массива использовать метод qsort. Для каждого N искать элемент, расположенный в начале, в середине и в конце массива. Вывести на экран следующую информацию в виде таблицы: количество элементов N, время поиска T, количество итераций K, расположение искомого элемента Х (Х=1, если элемент расположен в начале последовательности; Х=2, если элемент расположен в середине последовательности; Х=3, если элемент расположен в конце последовательности). Сравнить результаты эксперимента с теоретической эффективностью алгоритмов.

задача состоит из 3 частей: 1 заголовочного файла dataflow.h
C++
1
2
3
4
5
const int BUFFER = 100;
 
void StdQSort(char** argv, int argc, bool flag = false);
char* StdBinarySearch(char* key, char** argv, int argc);
char* SequentialFind(char* key, char** argv, int argc)

и 2 cpp файлов
sort.cpp
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
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <conio.h>
#include <sys/timeb.h>
 
#include "dataflow.h"
 
extern unsigned long int Iterations;
 
void printArray(int* arr, int count)
{
    // Вывод результатов на экран
   for( int i = 0; i < count; i++ )
      printf( " %i", arr[i] );
   printf( "\n" );
}
 
int* createArray(int* arr, int count)
{
    arr = (int *) malloc(count*sizeof(int));
    for (int i=0; i < count; i++)
        arr[i] = rand();
    return arr;
}
 
int* copyArray(const int* source, int* dest, int count)
{
    dest = (int *) malloc(count*sizeof(int));
    return (int*) memcpy(dest, source, count*sizeof(int));
}
 
int main( int argc, char **argv )
{
    srand( (unsigned)time( NULL ) );
    int count = 100;
    int* arr = NULL;
    struct _timeb tstruct0, tstruct1;
 
    printf("\n\tN\t\tT\t\t\tK\t   TEOR\n");
    for (int i=0; i<12;i++)
    {
    arr = createArray(arr, count);
    int *copyArr=NULL;
    copyArr = copyArray(arr, copyArr, count);
    Iterations = 0; 
    _ftime( &tstruct0 );
    //printf("%s",ctime(&tstruct0.time));
    StdQSortInt(arr, count);
    _ftime( &tstruct1 );
 
    //printf("%s",ctime(&tstruct0.time));
    StdQSortInt(copyArr, count);
 
 
    double Tsec=_difftime64(tstruct1.time, tstruct0.time);
    int Tmsec = abs(tstruct1.millitm-tstruct0.millitm);
    int teor = (count*log((float)count)/log(2.0));
 
    printf( "%15ld %5.0lf sec %u msec %15ld %15ld\n", count, Tsec, Tmsec, Iterations, teor);
    free(arr);
    free(copyArr);
    if (count<1e+6)
      count*=10;
    //else
      //count*=2;
    }
    _getche();
}
и

dataprocess.cpp
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
#include <string.h>
#include <stdlib.h>
#include "dataflow.h"
 
unsigned long int Iterations = 0;
 
 
int* SequentialFind(char* key, char** argv, int argc)
{
    for (int i=0; i<count; i++)
        if (array[i]==key)
            return &array[i];
    return 0;
}
 
 
 
char* BinarySearch (char* key, char** argv, int argc)
{
  int lb = 0, ub = argc - 1;
  do 
  {
    int m = (lb + ub)/2;
    if (strcmp(key, argv[m])<0)
      ub = m - 1;
    else 
        if (strcmp(key, argv[m])>0)
          lb = m + 1;
    else
      return argv[m];
    if (lb > ub)
      return NULL;
  } while(true);
}
 
void StdQSort(char** argv, int argc, bool flag)
{
    if (!flag)
        qsort( (void *)argv, (size_t)argc, sizeof( char * ), (int (*)(const void *, const void *))AscendingCompare );
    else
        qsort( (void *)argv, (size_t)argc, sizeof( char * ), (int (*)(const void *, const void *))DescendingCompare );
}
 
char* StdBinarySearch(char* key, char** argv, int argc)
{
  StdQSort(argv, argc);
  char **result = (char **)bsearch( (char *) &key, (char *)argv, argc,
                              sizeof( char * ), (int (*)(const void*, const void*))AscendingCompare );
  return *result;
}
 
int AscendingCompareInt( int* arg1, int* arg2 )
{
    Iterations++;
    if (*arg1 < *arg2)
        return -1;
    else
        if (*arg1 > *arg2)
            return +1;
        else
            return 0;
}
 
void StdQSortInt(int* argv, int argc)
{
    qsort( (void *)argv, (size_t)argc, sizeof( int ), (int (*)(const void *, const void *))AscendingCompareInt );
}
буду признателен за помощь!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 16:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru