Задача: Сортировка методом шелла

Тема в разделе "C/C++/C#", создана пользователем zlosend, 2 ноя 2010.

  1. zlosend

    zlosend Гость

    Разработать программу для расчета времени, необходимого для выполнения сортировки методом Шелла, массив данных должен быть считан из файла, указанного пользователем, и отображен в диалоге до и после сортировки.
    Кто может помочь в icq 364288 ;) На си естественно

    Добавлено: Если будет антиспам, тогда вконтакт zlosend.vkontakte.ru <_<
    Пи.эс:язык С++ естественно
     
  2. flashkpi

    flashkpi Гость

    Отписал в аську
    icq: 588002847 если что
     
  3. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    2 zlosend : Если не надумал еще ни у кого заказывать, помогу, но при условии что сам хотя бы что-то напишишь....
     
  4. zlosend

    zlosend Гость

    Код (C++):
    #include<iostream>
    #include<iomanip>
    #include<conio.h>
    #include<time.h>
    #include<stdlib.h>
    #include<fstream>

    using namespace std;

    int *A; // указатель на неотсортированный массив
    int *C; // указатель на отсортированный массив

    void ShellSort(int); // наша сортировка, методом шелла

    bool ShellSortChec(int); // проверка правильности нашей сортировки

    bool QwickSortChec(int); // проверка правильности встроенной быстрой сортировки

    int Sravni(const void*,const void*); // функция сравнения для qsort()

    void main()
    {
    ofstream outs("Result.xls",ios::out); // файловый поток для записи
    srand((unsigned)time(NULL)); // генерируем случайную последовательность

    double StartTime, EndTime,Time,Time1,Time2,TimeTempPod,TimeTempQsort; // переменные для хранения времени
    long N,M; // размеры массива
    int i,j; // переменные цикла
    int proxod = 20; // количество проходов для измерения среднего времени
    bool istina; // для проверки правильности сортировки
    system("CLS");
    cout<<"\n VVEDI CHISLO ELEMENTOV MASSIVA\n N ( N>=10000 ) = ";
    cin>>N;
    while (N<10000)
    {
    cout<<"\n CHISLO \"N\" SLISHKOM MALENKOE!!!\n";
    cout<<" N ( N>10000 ) = ";
    cin>>N;
    }
    cout<<"------------------------------\n";
    cout<<" IDET OBRABOTKA MASSIVA..."<<endl<<" ";

    A=new int[N]; // выделяем память
    cout<<"------------------------------\n";
    outs<<endl; // в файл пишем пустую строку
    i=0;
    outs<<"\tSortirovka Shell (msec)\tQsort (msec)"<<endl; // пишем в выводной поток
    do
    {
    Time1=0;
    Time2=0;
    switch(i) // шесть проходов. для каждого выбираем M
    {
    case 0:M=N;     break;
    case 1:M=N/2;   break;
    case 2:M=N/5;   break;
    case 3:M=N/10;  break;
    case 4:M=N/50;  break;
    case 5:M=N/100; break;
    case 6:M=N/1000;break;
    }

    for(j=0;j<proxod;j++)// в каждом proxod проходов
    {                      
    for(int k=0;k<M;k++) A[k]=rand(); // генерируем случайный массив размера M

    StartTime = clock();

    ShellSort(M);

    EndTime = clock();
    TimeTempPod = double(EndTime-StartTime)/CLOCKS_PER_SEC;

    StartTime=clock();
    qsort(A, M, sizeof(A[0]), Sravni); // быстрая сортировка, встроенная в С++

    EndTime=clock();
    TimeTempQsort = double(EndTime-StartTime)/CLOCKS_PER_SEC;

    Time1 = Time1 + TimeTempPod; // общее время сортировок шелла
    Time2 = Time2 + TimeTempQsort; // --||-- qsort

    outs.precision (17);
    //outs<<" Time("<<j+1<<") Massiv["<<M<<"] :\t"<<1000*TimeTempPod<<'\t'<<1000*TimeTempQsort<<endl;
    //cout<<" Time("<<j+1<<") Massiv["<<M<<"] :\t"<<1000*TimeTempPod<<'\t'<<1000*TimeTempQsort<<endl;

    }
    cout<<" Srednee vremja sortirovki (in msec) dlja N = "<<setw(10)<<M<<"\t: " <<100*Time1/proxod<<'\t'<<100*Time2/proxod<<endl;
    outs.precision (17);
    outs<<M<<"\t " <<100*Time1/proxod<<'\t'<<100*Time2/proxod<<endl;

    istina=QwickSortChec(M); // проверяем qsort
    if(istina==false) cout<<" !!!FATAL ERROR!!!"<<endl; // если неверно
    if(i==6) istina=false;  // чтобы выйти из цикла do..while
    i=i+1;
    }
    while (istina);
    system("PAUSE");
    system("CLS");
    cout<<"------------------------------\n";
    cout<<" SAVE FILE \"Result.xls\" \n";
    system("PAUSE"); // ждём пользователя
    }
    void ShellSort(int N) // наша сортировка
    {
    C = new int[N]; // выделяем память под массив
    copy(&A[0],&A[N-1],C); // копируем А в С
    int i,j,k;
    int h;
    k = N>>1; // шаг сортировки, в два раза меньше размера массива
    while(k>0){ // по всем шагам до нуля
    for (i=0;i<=(N-k);i++){ // сортируем подмассивы
    j = i; // начинаем с первого элемента
    while((j>=0)&&(C[j]>C[j+k])){ // пока подмассив неотсортирован
    swap(C[j],C[j+k]); // меняем элементы местами
    j -= k; // шаг k
    }
    }
    k = k>>1; // уменьшаем шаг сортировки
    }
    }

    int Sravni(const void* x,const void* y) // x и y - просто указатели
    {
    return ((*(int*)(x))-(*(int*)(y))); // сравниваем
    }

    bool ShellSortChec(int N) // проверка сортировки, массив С
    {
    bool temp=true; // нужно проверить, если хотя бы один раз окажнтся, что элемент с меньшим индексом больше элемента с большим, сортировка неверна
    // в начале предполагаем, что она верна
    for (int i=0; i<N-1; i++)
    {
    if (C[i]>C[i+1]) temp=false; // если элемент с меньшим индексом больше элемента с большим, сортировка неверна
    }
    return temp;
    }

    bool QwickSortChec(int N) // аналогично проверяем быструю сортровку, но массив A
    {
    bool temp=true;
    {
    for (int i=0; i<N-1; i++)
    if (A[i]>A[i+1]) temp=false;
    }
    return temp;
    }
    Примерно так придумал. С прикручиванием интерфейся огромные проблемы...
     
  5. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Закинь еще входной файл данных...
    И какой именно интерфейс должен быть?
     
Загрузка...
Похожие Темы - Задача Сортировка методом
  1. Exilien
    Ответов:
    2
    Просмотров:
    3.156
  2. Янчик
    Ответов:
    0
    Просмотров:
    491
  3. TrishaRay
    Ответов:
    1
    Просмотров:
    783
  4. elzim
    Ответов:
    0
    Просмотров:
    932
  5. ShaoKahn
    Ответов:
    0
    Просмотров:
    1.131

Поделиться этой страницей