Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

сортировка

74K
21 декабря 2011 года
Pechen`ka
9 / / 08.12.2011
Отсортировать массив методом пузырька. Вычислить трудоемкость.
Замерить время для отсортированного массива, отсортированного в обратном порядке
для случайного размещения элементов. Генерация больших массивов с помощью датчика
случайных чисел.

Код:
#include <math.h>
#include <locale.h>
#include <stdio.h>
#include <stdlib.h>
const int N=100;

// функция ввода исходных данных одномерного массива
void inMas1 (int &size, int A[N])
{
    //ввод size (кол-ва сортирующихся элементов)
    printf ("введите size = ");
    scanf ("%d", &size);

    //ввод одномерного массива a[N]
    for (int i=0; i<size; i++)
    {
        //ввод a
        printf ("a[%d]=", i);
        scanf ("%d", &A);
    }
}
// функция вывода результата
void outMas1 (int size, int q, int A[N])
{
    printf ("Отсортированный массив: \n");
    for (int i=0; i<size; i++)
        printf ("%d ", A);
   
    // вывод трудоёмкости q
    printf ("\nТрудоёмкость q = ");
    printf ("%d ", q);
}
// функция сортировки методом пузырька и вычисление трудоёмкости q
void SortPuz (int size, int &q, int A[N])
{
    int a, b, t;

    q=size*size;

    for (a=1; a<size; a++)
    {
        for (b=size-1; b>=a; b--)
            if (A[b-1]>A)
            {
                // элементы не упорядочены => меняем их местами
                t=A[b-1];
                A[b-1]=A;
                A=t;
            }
    }
}
int main()
{
    setlocale (LC_ALL, "russian");
    int A[N];
    int size, q;

    // ввод исходных данных одномерного массива
    inMas1 (size, A);

    // реализация сортировки методом пузырька и вычисление трудоёмкости q
    SortPuz (size, q, A);

    // вывод отсортированного массива
    outMas1 (size, q, A);

    return 0;
}

как можно её доделать?
14
21 декабря 2011 года
Phodopus
3.3K / / 19.06.2008
а что там не так?
74K
22 декабря 2011 года
Pechen`ka
9 / / 08.12.2011
всё работает, но я не знаю как выполнить полностью задачу(т.е. Замерить время для отсортированного массива, отсортированного в обратном порядке для случайного размещения элементов)
2.2K
22 декабря 2011 года
S@tana
53 / / 15.10.2009
Я так понял надо время выполнения кода замерить.
Если так, то можно таймер использовать. Хотя в мингв вроде по умолчанию к консоль время выполнения пихает(если не путаю).
74K
22 декабря 2011 года
Pechen`ka
9 / / 08.12.2011
Цитата: S@tana
Я так понял надо время выполнения кода замерить.
Если так, то можно таймер использовать. Хотя в мингв вроде по умолчанию к консоль время выполнения пихает(если не путаю).


меня интересует как замерить время выполнения кода, дописав мой код?

2.2K
22 декабря 2011 года
S@tana
53 / / 15.10.2009
Первое что в голову приходит это таймер. Включаешь где надо по окончанию выводишь время.
74K
22 декабря 2011 года
Pechen`ka
9 / / 08.12.2011
Цитата: S@tana
Первое что в голову приходит это таймер. Включаешь где надо по окончанию выводишь время.



можно показать куда его вписывать?

14
23 декабря 2011 года
Phodopus
3.3K / / 19.06.2008
запуск таймера перед началом сортировки (где оно у вас кстати?) и остановка - сразу посл окончания (а оно где у вас?)
74K
23 декабря 2011 года
Pechen`ka
9 / / 08.12.2011
Цитата: Phodopus
запуск таймера перед началом сортировки (где оно у вас кстати?) и остановка - сразу посл окончания (а оно где у вас?)


вот теперь я запуталась. значит мой код совсем не то что надо?( тогда, пожалуйста, напишите правильный.

78K
23 декабря 2011 года
AlexDark
3 / / 23.12.2011
С таймером будет так ( дописать библиотеку и поправить main ) :

Правда если сортировка будет меньше 1сек (а с таким размером массива так и будет), прога честно выведет 0 сек

Код:
......

#include <time.h>
......

int main()
{
    setlocale (LC_ALL, "russian");
    int A[N];
    int size, q;

    // ввод исходных данных одномерного массива
    inMas1 (size, A);

        time_t t1 = time(NULL);

    // реализация сортировки методом пузырька и вычисление трудоёмкости q
    SortPuz (size, q, A);

        time_t t2 = time(NULL);

        int Time = t2-t1;

       //вывод затрат времени
       printf("\n Sorting was complete in %d seconds\n",Time);


    return 0;
}
14
23 декабря 2011 года
Phodopus
3.3K / / 19.06.2008
Цитата: Pechen`ka
вот теперь я запуталась. значит мой код совсем не то что надо?( тогда, пожалуйста, напишите правильный.


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

80K
16 февраля 2012 года
NoX
4 / / 16.02.2012
Алгоритм пузырьковой сортировки с выводом колличества промежуточных результатов = сложность сортировки.
80K
16 февраля 2012 года
NoX
4 / / 16.02.2012

Код:
void initv(int* v, int n)
{
    int i = 0;
    while (i < n)
    {
        bool b = false;
        int value = rand() % n + 1;
        for (int k = i-1; k >= 0; k--)
            if (v[k] == value) b = true;
        if (b == true) continue;
        v[i++] = value;
    }
}

bool issorted(int* v, int n)
{
    for (int i = 0; i < n-1; i++)
        if (v > v[i+1])
            return false;

    return true;
}

int bsort(int* v, int n)
{
    int k = 0;
    while (!issorted(v,n))
    {
        for (int i = 0; i < n-1; i++)
            if (v > v[i+1])
            {
                int t = v;
                v = v[i+1];
                v[i+1] = t;
            }

        printf("%d - ",k);

        for (int l = 0; l < n; l++)
            printf("%d ",v[l]);

        printf("\n");
        k++;
    }

    return k;
}

80K
16 февраля 2012 года
NoX
4 / / 16.02.2012

Код:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

void initv(int*,int);
bool issorted(int*,int);
int bsort(int*,int);

void printv(int* v, int n);
void btest();

#define N 10

int main(int argc, char* argv[])
{
    btest();
    return 0;
}

void btest()
{
    int v[N];
    char ch = '\0';
    int k = 0, avg = 0;
    while (ch != 'q')
    {  
        initv(v,N);      printv(v,N);
        avg+=bsort(v,N); printv(v,N);
        ch = _getch();
        k++;
    }

    printf("Average difficulty = %4.2f\n",(float)avg/k); _getch();
}

80K
16 февраля 2012 года
NoX
4 / / 16.02.2012
Код для тестирования пузырьковой сортировки выше. Для исследования характеристик
времени используйте стандартную функцию time() вставляя ее в нужные участки кода
чтобы потом вычислить время затраченое на сортировку.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог