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

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

Восстановить пароль Регистрация
 
Kaze
Сообщений: n/a
12.05.2013, 00:51     Сравнение алгоритмов поиска и сортировки #1
Дан массив из 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 );
}
буду признателен за помощь!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.05.2013, 00:51     Сравнение алгоритмов поиска и сортировки
Посмотрите здесь:

Сравнение алгоритмов сортировок C++
C++ Сравнение алгоритмов сортировки ... алгоритм Шелла
C++ Сравнение алгоритмов сортировки массива
C++ Визуализация алгоритмов сортировки
Подскажите название алгоритмов поиска и сортировки информации C++
Разработать программу для сравнительного графического анализа алгоритмов сортировки и поиска C++
Сравнение быстродействия алгоритмов сортировки слияния с сортировкой линейной выборкой C++
Реализация алгоритмов сортировки C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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