VPF::Сортировка массива через функцию

Metalex

Дата 17.12.2009, 14:56 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 635
Регистрация: 22.10.2008
Где: Украина-ZPсity

Репутация: нет
Всего: нет

Отсортировать динамический массив методом вставки передачей в функию. Функция должна вернуть время, затраченное на сортировку.
Мой код:

Код

#include <iostream.h>
#include <stdio.h>

//сортировка методом вставки
int Mvstavki (int *matrix, int n)
{
    clock_t time;
    time = clock();
    
    int x, i, j;
    for(i=0;i<n;i++)
    {
        x=matrix[i];
        j=i;
        while(x<matrix[j-1]&&j!=0)
        {
                matrix[j]=matrix[j-1]; 
                j--;
        }
        matrix[j]=x;
    }
    time = clock() - time;
return (time);
}

int main()
{
    int n, i, j;
    cout <<"Vvedite n"<<endl;
    cin >>n;
    int *matrix;
    matrix=new int [n];
    
    srand(time(NULL));
    for (i=0; i<n; i++)
    matrix[i]=rand()%100-50;
    
    cout<<"Nachal'nui massiv:"<<endl;
    for (i=0; i<n; i++)
    cout<<matrix[i]<<" ";
    cout<<endl;

    cout<<"Vremya vupolnenya"<<endl;
    printf("%s", "Time1 = \0");
    printf("%f", (double)Mvstavki(matrix, n)/CLK_TCK);
    printf("%s", " - sortirovka metodom vstavki\0");
    printf("\n");
    
    cout<<"Otsortirovanyi massiv:"<<endl;
    for (i=0; i<n; i++)
    cout<<matrix[i]<<" ";
    cout<<endl;   
    
    delete [] matrix;
    matrix=0;
    
system ("Pause");
return 0;
}

Но время равно 0.000000. Почему? И можно ли как-то printf слить в одну строку? Я пытался, но тогда даже эти нули не выводятся. Спасибо.

--------------------

Don't let the system get you down.

azesmcar

Дата 17.12.2009, 15:17 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 9
Всего: 211

потому что сортирует быстро, попробуй большой обьем данных.

Дополняй, изменяй..

Код


#include <iostream>
#include <ctime>
#include <cstdlib>

unsigned int sort(int * a, unsigned int size)
{
    time_t now = time(0);
    for (unsigned int j = 2; j < size; ++j)
    {
        for (unsigned int k = 0; k < j; ++k)
        {
            if (a[j] < a[k])
            {
                int temp = a[k];
                a[k] = a[j];
                a[j] = temp;
            }
        }
    }
    return (unsigned int)(time(0) - now);
}

int main() {
    const int size = 30000;
    int* a = new int[size];
    for (int i = 0; i < size; ++i)
        a[i] = rand() % 1000;

    unsigned int duration = sort(a, size);

    /*for (unsigned int i = 0; i < size; ++i)
        std::cout << a[i] << std::endl;*/

    std::cout << "sort duration: " << duration << std::endl;

    delete [] a;
}

Metalex

Дата 17.12.2009, 16:20 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 635
Регистрация: 22.10.2008
Где: Украина-ZPсity

Репутация: нет
Всего: нет

azesmcar, спасибо огромное!
Еще вопросик: если мне нужно применить всего 3 метода сортировки (это был только первый) в одной программе (функциями) и сравнить значения длительности исполнения сортировок. Но уже при первой массив будет упорядочен. Нужно заранее копировать первоначальный массив еще 2 раза? И можно ли сделать так:

Код

massiv1=massiv2;

То есть присвоить одному массиву другой?

Добавлено через 14 секунд
Или через цикл?

--------------------

Don't let the system get you down.

azesmcar

Дата 17.12.2009, 16:22 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 9
Всего: 211

Цитата(Metalex @ 17.12.2009, 16:20

)

Нужно заранее копировать первоначальный массив еще 2 раза? И можно ли сделать так:

нет, так нельзя (точнее можно, но так скопируется указатель).

Цитата(Metalex @ 17.12.2009, 16:20

)

Или через цикл?

а также std::copy, memcpy ...

Metalex

Дата 17.12.2009, 17:46 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 635
Регистрация: 22.10.2008
Где: Украина-ZPсity

Репутация: нет
Всего: нет

Цитата(azesmcar @ 17.12.2009, 16:22

)

а также std::copy, memcpy ...

ну это мне не грозит smile

все равно не понятно

--------------------

Don't let the system get you down.

Metalex

Дата 17.12.2009, 18:09 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 635
Регистрация: 22.10.2008
Где: Украина-ZPсity

Репутация: нет
Всего: нет

И еще одно: зачем

Код

unsigned int

--------------------

Don't let the system get you down.

Dancer

Дата 17.12.2009, 18:31 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 537
Регистрация: 29.4.2005
Где: Nizhniy Novgorod

Репутация: 4
Всего: 37

Код


.....
   const int size = 30000;
    int* a = new int[size];
    for (int i = 0; i < size; ++i)
        a[i] = rand() % 1000;

    int * bArray = new int[size];
    int * cArray = new int[size];
    memcpy(bArray, a, size*sizeof(int));
    memcpy(cArray, a, size*sizeof(int));

   unsigned int duration = sort(a, size);
.....

--------------------

У программистов есть великая тайна: всё, что только можно, было давно кем-то когда-то написано. Разработчику только нужно знать в какое место кода какие строчки вставить! smile

Metalex

Дата 17.12.2009, 18:41 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 635
Регистрация: 22.10.2008
Где: Украина-ZPсity

Репутация: нет
Всего: нет

Гляньте че тут.. Теперь у меня 2 функции, но считает либо вторая либо первая.. Грубые ошибки есть?

Код

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>

//сортировка методом вставки
int Sort1 (int *matrix, int n)
{
    clock_t time;
    time = clock();
    
    int x, i, j;
    for(i=0;i<n;i++)
    {
        x=matrix[i];
        j=i;
        while(x<matrix[j-1]&&j!=0)
        {
                matrix[j]=matrix[j-1]; 
                j--;
        }
        matrix[j]=x;
    }
    time = clock() - time;
return (time);
}

//сортировка методом простого выбора
int Sort2 (int *matrix, int n)
{
    clock_t time;
    time = clock();
    
    int x, k, i, j;
    for(i=0;i<n;i++)
    {
        k=i;
        x=matrix[i];
        for(j=i+1; j<n; j++)
        if (matrix[j]<x) 
        {
                k=j; 
                x=matrix[k];
        }
        matrix[k]=matrix[i];
        matrix[i]=x;
    }
    time = clock() - time;
return (time);
}

int main()
{
    int n, i, j;
    cout <<"Vvedite n"<<endl;
    cin >>n;
    int *matrix=new int [n];
    int *matrixx=new int [n];
    
    srand(time(NULL));
    for (i=0; i<n; i++)
    {
        matrix[i]=rand()%10000-5000;
    }
    
    memcpy(matrixx, matrix, n*sizeof(int));
    
    cout<<"Nachal'nui massiv:"<<endl;
    for (i=0; i<n; i++)
    cout<<matrix[i]<<" ";
    cout<<endl;

    cout<<"Vremya vupolnenya"<<endl;
    printf("%s", "Time1 = \0");
    printf("%f", (double)Sort1(matrix, n)/CLK_TCK);
    printf("%s", " - sortirovka metodom vstavki\0");
    printf("\n");
    
    cout<<"Vremya vupolnenya"<<endl;
    printf("%s", "Time2 = \0");
    printf("%f", (double)Sort2(matrixx, n)/CLK_TCK);
    printf("%s", " - sortirovka metodom vstavki\0");
    printf("\n");
    
    cout<<"Otsortirovanyi massiv:"<<endl;
    for (i=0; i<n; i++)
    cout<<matrix[i]<<" ";
    cout<<endl;   
    
    delete [] matrix;
    matrix=0;
    
system ("Pause");
return 0;
}

--------------------

Don't let the system get you down.

azesmcar

Дата 18.12.2009, 09:20 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 9
Всего: 211

не пойму я чего-то..либо printf используй, либо cout.. апридилайса да © smile

Цитата(Metalex @ 17.12.2009, 18:41

)

Гляньте че тут.. Теперь у меня 2 функции, но считает либо вторая либо первая.. Грубые ошибки есть?

нормально должно работать, убери вывод массива и сгенерируй массив побольше..вот так

Код


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>

using namespace std;

//сортировка методом вставки
int Sort1 (int *matrix, int n)
{
    clock_t time;
    time = clock();

    int x, i, j;
    for(i=0;i<n;i++)
    {
        x=matrix[i];
        j=i;
        while(x<matrix[j-1]&&j!=0)
        {
            matrix[j]=matrix[j-1]; 
            j--;
        }
        matrix[j]=x;
    }
    return time = clock() - time;
}
//сортировка методом простого выбора
int Sort2 (int *matrix, int n)
{
    clock_t time;
    time = clock();

    int x, k, i, j;
    for(i=0;i<n;i++)
    {
        k=i;
        x=matrix[i];
        for(j=i+1; j<n; j++)
            if (matrix[j]<x) 
            {
                k=j; 
                x=matrix[k];
            }
            matrix[k]=matrix[i];
            matrix[i]=x;
    }
    return clock() - time;
}
int main()
{
    int n;
    cout <<"Vvedite n"<<endl;
    cin >>n;
    int *matrix=new int [n];
    int *matrixx=new int [n];

    srand((unsigned int)time(NULL));
    for (int i=0; i<n; i++)
        matrix[i]=rand()%10000-5000;

    memcpy(matrixx, matrix, n*sizeof(int));

    cout<<"Vremya vipolnenya sort 1"<<endl;
    cout << ((double)Sort1(matrix, n)/CLK_TCK) << endl;

    cout<<"Vremya vipolnenya sort 2"<<endl;
    cout << ((double)Sort2(matrix, n)/CLK_TCK) << endl;

    delete [] matrix;
    matrix=0;

    system ("Pause");
}

Цитата

Vvedite n
50000
Vremya vipolnenya sort 1
2.922
Vremya vipolnenya sort 2
3.896

Metalex

Дата 18.12.2009, 14:31 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 635
Регистрация: 22.10.2008
Где: Украина-ZPсity

Репутация: нет
Всего: нет

azesmcar, благодарю еще раз!

--------------------

Don't let the system get you down.

Dancer

Дата 18.12.2009, 14:38 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 537
Регистрация: 29.4.2005
Где: Nizhniy Novgorod

Репутация: 4
Всего: 37

думаю, там ошибочка небольшая закралась (точнее описочка) smile

.
Оба раза один и тот же массив сортируется.
наверное должно в одном быть matrix (sort1), в другой раз matrixx (sort2).
и освобождение памяти только из под одного массива (не Айс smile

)
наверное должно быть как-то так:

Код


......
  memset(matrix, 0, n*sizeof(int));
  memset(matrixx, 0, n*sizeof(int));
  delete[] matrix;
  delete[] matrixx;
.....

--------------------

Rodman

Дата 19.12.2009, 13:04 (ссылка)

(нет голосов)

Загрузка ...

CIO

Профиль
Группа: Участник
Сообщений: 6144
Регистрация: 7.5.2006
Где: Ukraine ⇛ Kyiv ci ty

Репутация: 26
Всего: 122

M
Rodman

Модератор: Название темы должно содержать язык написания!

--------------------

CRM с функцией АвтоОбзвона

Лотереи мира

Metalex

Дата 20.12.2009, 21:44 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 635
Регистрация: 22.10.2008
Где: Украина-ZPсity

Репутация: нет
Всего: нет

Dancer, да, действительно smile

Rodman, недоглядел, прошу прощения

--------------------

Don't let the system get you down.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »