Сортировки Числовых Массивов.

Тема в разделе "C/C++/C#", создана пользователем Miller85, 7 фев 2012.

  1. Miller85

    Miller85 Гость

    Всем привет! Нужна помощь!
    Задание:

    1) Отсортировать по возрастанию числовой массив обменами, выбором, вставками, пузырьком и быстрой сортировкой. Получить зависимости временных затрат от размера массива. Временные затраты оценивать количеством сравнений и количеством обменов элементов массива. Сортировку выполнять на месте исходного массива.

    вот мой код:
    загаловочный (.h):
    Код (C++):
    #ifndef LR_3H
    #define LR_3H
    //---------------------------------------------------------------------------
    #include <Classes.hpp>
    #include <Controls.hpp>
    #include <StdCtrls.hpp>
    #include <Forms.hpp>
    #include "CSPIN.h"
    #include <ComCtrls.hpp>
    #include <Menus.hpp>
    #include <Buttons.hpp>
    #include <ExtCtrls.hpp>
    #include <Grids.hpp>
    #include <Chart.hpp>
    #include <TeEngine.hpp>
    #include <TeeProcs.hpp>
    #include <Series.hpp>
    #include <Dialogs.hpp>
    #include <ExtDlgs.hpp>
    //---------------------------------------------------------------------------
    class TForm1 : public TForm
    {
    __published:    // IDE-managed Components
    TMainMenu *MainMenu1;
    TMenuItem *file;
    TMenuItem *N2;
    TMenuItem *N3;
    TMenuItem *sort;
    TMenuItem *rec;
    TMenuItem *rep;
    TMenuItem *help;
    TMenuItem *exit;
    TGroupBox *GroupBox1;
    TGroupBox *GroupBox2;
    TLabel *Label1;
    TLabel *Label2;
    TLabel *Label3;
    TPageControl *PageControl1;
    TTabSheet *TabSheet1;
    TTabSheet *TabSheet2;
    TCSpinEdit *CSpinEdit1;
    TCSpinEdit *CSpinEdit2;
    TCSpinEdit *CSpinEdit3;
    TCSpinEdit *CSpinEdit4;
    TCSpinEdit *CSpinEdit5;
    TLabel *Label4;
    TLabel *Label5;
    TLabel *Label6;
    TCSpinEdit *CSpinEdit6;
    TPanel *Panel1;
    TBitBtn *BitBtn1;
    TMemo *Memo1;
    TStringGrid *StringGrid1;
    TStringGrid *StringGrid2;
    TProgressBar *ProgressBar1;
    TCSpinEdit *CSpinEdit7;
    TTabSheet *TabSheet3;
    TTabSheet *TabSheet4;
    TTabSheet *TabSheet5;
    TTabSheet *TabSheet6;
    TTabSheet *TabSheet7;
    TChart *Chart5;
    TLineSeries *Series9;
    TLineSeries *Series10;
    TChart *Chart4;
    TLineSeries *Series7;
    TLineSeries *Series8;
    TChart *Chart3;
    TLineSeries *Series5;
    TLineSeries *Series6;
    TChart *Chart1;
    TLineSeries *Series1;
    TLineSeries *Series2;
    TChart *Chart2;
    TLineSeries *Series3;
    TLineSeries *Series4;
    TImage *Image1;
    TImage *Image2;
    TImage *Image3;
    TImage *Image4;
    TImage *Image5;
    TPopupMenu *PopupMenu1;
    TPopupMenu *PopupMenu2;
    TPopupMenu *PopupMenu3;
    TPopupMenu *PopupMenu4;
    TPopupMenu *PopupMenu5;
    TMenuItem *N1;
    TMenuItem *N4;
    TMenuItem *N5;
    TMenuItem *N6;
    TMenuItem *N7;
    TMenuItem *N8;
    TMenuItem *N9;
    TMenuItem *N10;
    TMenuItem *N11;
    TMenuItem *N12;
    TLabel *Label7;
    TLabel *Label8;
    TLabel *Label9;
    TGroupBox *GroupBox3;
    void __fastcall exitClick(TObject *Sender);
    void __fastcall BitBtn1Click(TObject *Sender);
    void __fastcall recClick(TObject *Sender);
    void __fastcall N2Click(TObject *Sender);
    void __fastcall N3Click(TObject *Sender);
    void __fastcall N1Click(TObject *Sender);
    void __fastcall N4Click(TObject *Sender);
    void __fastcall N5Click(TObject *Sender);
    void __fastcall N6Click(TObject *Sender);
    void __fastcall N7Click(TObject *Sender);
    void __fastcall N8Click(TObject *Sender);
    void __fastcall N9Click(TObject *Sender);
    void __fastcall N10Click(TObject *Sender);
    void __fastcall N11Click(TObject *Sender);
    void __fastcall N12Click(TObject *Sender);
    void __fastcall helpClick(TObject *Sender);
    private:    // User declarations
    public:     // User declarations
    __fastcall TForm1(TComponent* Owner);
    };
    //---------------------------------------------------------------------------
    extern PACKAGE TForm1 *Form1;
    //---------------------------------------------------------------------------
    class array{
    public:
    array(int);               //конструктор 1 (с параметром)
    array(array&);              //конструктор 2 (копии)
    void swap(int&,int&);     //обмен элементов в сортируемом массиве
    void SwapSort(int,int,int);      //сортировка обменами
    void SelectSort(int,int,int,int);    //сортировка выбором
    void InsertSort(int,int,int,array&); //сортировка вставками
    void BubbleSort(int,int,int,int);   //сортировка пузырьком
    void QuickSort(int,int,int);         //быстрая сортировка
    void out_mass_a()const; //вывод исходного и отсортированного массивов
    int get_sr()const{return sr;} //получить сравнения
    int get_obm()const{return obm;}//получить обмены
    ~array(){delete[]a;}         //деструктор
    private:
    int*a, //указатель для исходного сортируемого массива
    sr, //сравнения
    obm, //обмены
    n;  //размер исходного сортируемого массива
    };
    #endif
    Программа:
    Код (C++):
    #include <vcl.h>
    #pragma hdrstop

    #include "LR_3.h"
    //---------------------------------------------------------------------------
    #pragma package(smart_init)
    #pragma link "CSPIN"
    #pragma resource "*.dfm"
    TForm1 *Form1;
    //---------------------------------------------------------------------------
    __fastcall TForm1::TForm1(TComponent* Owner)
    : TForm(Owner)
    {
    }
    //---------------------------------------------------------------------------
    int razm_min,razm_max,d,m,max_d,min_d,razm_out,t;
    //---------------------------------------------------------------------------
    array::array(int p)
    {n=p;
    a=new int[n];
    sr=0;
    obm=0;
    for(int i=0;i<n;i++) a[i]=random(max_d-min_d+1)+min_d;
    }
    //---------------------------------------------------------------------------
    array::array(array&c)
    {n=c.n; sr=c.sr; obm=c.obm;
    a=new int[n];
    for(int i=0;i<n;i++)a[i]=c.a[i];
    }
    //---------------------------------------------------------------------------
    void array::swap(int&x,int&y)
    {int z=x;x=y;y=z;}
    //---------------------------------------------------------------------------
    void array::SwapSort(int i,int j,int k)
    { if(i==n-1) return;
    if(j<n) {
    if(a[i]>a[j]) {swap(a[i],a[j]); obm++;}
    sr++; SwapSort(i,j+1,k);
    }
    else SwapSort(i+1,i+2,k);
    }
    //---------------------------------------------------------------------------
    void array::SelectSort(int i,int j,int min,int k)
    { if(i==n-1) return;
    if(j<n) {
    if(a[min]>a[j]) min=j;
    sr++; SelectSort(i,j+1,min,k);
    }
    else {
    swap(a[i],a[min]); obm++;
    SelectSort(i+1,i+2,i+1,k);
    }
    }
    //---------------------------------------------------------------------------
    void array::InsertSort(int i,int j,int k,array&c)
    { if(i==n) return;
    int z=c.a[i];
    if(j>0&&z<a[j-1]) {
    a[j]=a[j-1]; sr++;
    InsertSort(i,j-1,k,c);
    }
    else {
    a[j]=z; sr++;
    InsertSort(i+1,i+1,k,c);
    }
    }
    //---------------------------------------------------------------------------
    void array::BubbleSort(int i,int j,int last,int k)
    { if(i<=0) return;
    if(j<i) {
    if(a[j]>a[j+1]) {swap(a[j],a[j+1]); obm++; last=j;}
    sr++; BubbleSort(i,j+1,last,k);
    }
    else BubbleSort(last,0,0,k);
    }
    //---------------------------------------------------------------------------
    void array::QuickSort(int l,int h,int k)
    { int su,sd,m,p;
    if(h-l<=0) return;
    else if(h-l==1) {
    if(a[h]<a[l]) {swap(a[l],a[h]); obm++;}
    sr++;
    return;
    }
    m=(l+h)/2; p=a[m]; swap(a[m],a[l]); obm++; su=l+1;sd=h;
    do{
    while(su<=sd && a[su]<=p) {su++; sr++;}
    while(p<a[sd]) {sd--; sr++;}
    if(su<sd) {swap(a[su],a[sd]); obm++; }
    } while(su<sd);
    a[l]=a[sd]; a[sd]=p; obm++;
    if(l<sd-1) QuickSort(l,sd-1,k);
    if(sd+1<h) QuickSort(sd+1,h,k);
    }
    //---------------------------------------------------------------------------
    void __fastcall TForm1::exitClick(TObject *Sender)
    {
    Close();
    }

    //---------------------------------------------------------------------------
    void array::out_mass_a()const
    {
    AnsiString str="";
    for(int i=0;i<n;i++)str+="  "+IntToStr(a[i]);
    Form1->Memo1->Lines->Add(str);
    }
    //---------------------------------------------------------------------------
    void __fastcall TForm1::BitBtn1Click(TObject *Sender)
    {
    Memo1->Clear();
    Panel1->Caption="";
    for(int i=0;i<StringGrid1->RowCount;i++)
    for(int j=0;j<StringGrid1->ColCount;j++)
    {StringGrid1->Cells[j][i]="";
    StringGrid2->Cells[j][i]="";}
    StringGrid1->Cells[0][0]="размер";
    StringGrid1->Cells[1][0]="обменами";
    StringGrid1->Cells[2][0]="выбором";
    StringGrid1->Cells[3][0]="вставками";
    StringGrid1->Cells[4][0]="пузырьком";
    StringGrid1->Cells[5][0]="быстрая";
    StringGrid2->Cells[0][0]="размер";
    StringGrid2->Cells[1][0]="обменами";
    StringGrid2->Cells[2][0]="выбором";
    StringGrid2->Cells[3][0]="вставками";
    StringGrid2->Cells[4][0]="пузырьком";
    StringGrid2->Cells[5][0]="быстрая";
    Series1->Clear();
    Series2->Clear();
    Series3->Clear();
    Series4->Clear();
    Series5->Clear();
    Series6->Clear();
    Series7->Clear();
    Series8->Clear();
    Series9->Clear();
    Series10->Clear();
    ProgressBar1->Position=0;
    if(CSpinEdit1->Value>CSpinEdit2->Value){Panel1->Caption=
    "мин размер не м б больше макс!"; return;}
    if(CSpinEdit5->Value>CSpinEdit4->Value){Panel1->Caption=
    "мин число не м б больше макс!"; return;}
    if(CSpinEdit7->Value%CSpinEdit3->Value){Panel1->Caption=
    "t/d должно быть целым!"; return;}
    razm_min=CSpinEdit1->Value;
    razm_max=CSpinEdit2->Value;
    d=CSpinEdit3->Value;
    m=(razm_max-razm_min)/d+1;
    max_d=CSpinEdit4->Value;
    min_d=CSpinEdit5->Value;
    razm_out=CSpinEdit6->Value;
    t=CSpinEdit7->Value;
    sort->Enabled=true;
    }
    //---------------------------------------------------------------------------
    void __fastcall TForm1::recClick(TObject *Sender)
    {
    StringGrid1->RowCount=(razm_max-razm_min)/t+2;
    StringGrid2->RowCount=(razm_max-razm_min)/t+2;
    int count=m,current=0;
    for(int k=0;k<m;k++){
    array arr(razm_min+k*d);
    if(razm_min+k*d==razm_out)
    Form1->Memo1->Lines->Add("              Сортировка обменами");
    array arr_swap=arr;
    if(razm_min+k*d==razm_out){
    Form1->Memo1->Lines->Add("Исходный массив");
    arr_swap.out_mass_a();}
    arr_swap.SwapSort(0,1,k);
    Form1->Series1->AddXY(razm_min+k*d,arr_swap.get_sr(),"",clBlack);
    Form1->Series2->AddXY(razm_min+k*d,arr_swap.get_obm(),"",clBlack);
    if(razm_min+k*d==razm_out){
    Form1->Memo1->Lines->Add("Отсортированный массив");
    arr_swap.out_mass_a();}
    if(razm_min+k*d==razm_out)
    Form1->Memo1->Lines->Add("               Сортировка выбором");
    array arr_select=arr;
    if(razm_min+k*d==razm_out){
    Form1->Memo1->Lines->Add("Исходный массив");
    arr_select.out_mass_a();}
    arr_select.SelectSort(0,1,0,k);
    Form1->Series3->AddXY(razm_min+k*d,arr_select.get_sr(),"",clBlack);
    Form1->Series4->AddXY(razm_min+k*d,
    arr_select.get_obm()*100,"",clBlack);
    if(razm_min+k*d==razm_out){
    Form1->Memo1->Lines->Add("Отсортированный массив");
    arr_select.out_mass_a();}
    if(razm_min+k*d==razm_out)
    Form1->Memo1->Lines->Add("              Сортировка вставками");
    array arr_insert=arr;
    if(razm_min+k*d==razm_out){
    Form1->Memo1->Lines->Add("Исходный массив");
    arr_insert.out_mass_a();}
    arr_insert.InsertSort(1,1,k,arr);
    Form1->Series5->AddXY(razm_min+k*d,arr_insert.get_sr(),"",clBlack);
    Form1->Series6->AddXY(razm_min+k*d,arr_insert.get_obm(),"",clBlack);
    if(razm_min+k*d==razm_out){
    Form1->Memo1->Lines->Add("Отсортированный массив");
    arr_insert.out_mass_a();}
    if(razm_min+k*d==razm_out)
    Form1->Memo1->Lines->Add("              Сортировка пузырьком");
    array arr_bubble=arr;
    if(razm_min+k*d==razm_out){
    Form1->Memo1->Lines->Add("Исходный массив");
    arr_bubble.out_mass_a();}
    arr_bubble.BubbleSort(razm_min+k*d-1,0,0,k);
    Form1->Series7->AddXY(razm_min+k*d,arr_bubble.get_sr(),"",clBlack);
    Form1->Series8->AddXY(razm_min+k*d,arr_bubble.get_obm(),"",clBlack);
    if(razm_min+k*d==razm_out){
    Form1->Memo1->Lines->Add("Отсортированный массив");
    arr_bubble.out_mass_a();}
    if(razm_min+k*d==razm_out)
    Form1->Memo1->Lines->Add("              Быстрая сортировка");
    array arr_quick=arr;
    if(razm_min+k*d==razm_out){
    Form1->Memo1->Lines->Add("Исходный массив");
    arr_quick.out_mass_a();}
    arr_quick.QuickSort(0,razm_min+k*d-1,k);
    Form1->Series9->AddXY(razm_min+k*d,arr_quick.get_sr(),"",clBlack);
    Form1->Series10->AddXY(razm_min+k*d,arr_quick.get_obm(),"",clBlack);
    if(razm_min+k*d==razm_out){
    Form1->Memo1->Lines->Add("Отсортированный массив");
    arr_quick.out_mass_a();}
    if(k*d%t==0){
    Form1->StringGrid1->Cells[0][k*d/t+1]=IntToStr(razm_min+k*d);
    Form1->StringGrid2->Cells[0][k*d/t+1]=IntToStr(razm_min+k*d);
    Form1->StringGrid1->Cells[1][k*d/t+1]=IntToStr(arr_swap.get_sr());
    Form1->StringGrid2->Cells[1][k*d/t+1]=IntToStr(arr_swap.get_obm());
    Form1->StringGrid1->Cells[2][k*d/t+1]=IntToStr(arr_select.get_sr());
    Form1->StringGrid2->Cells[2][k*d/t+1]=IntToStr(arr_select.get_obm());
    Form1->StringGrid1->Cells[3][k*d/t+1]=IntToStr(arr_insert.get_sr());
    Form1->StringGrid2->Cells[3][k*d/t+1]=IntToStr(arr_insert.get_obm());
    Form1->StringGrid1->Cells[4][k*d/t+1]=IntToStr(arr_bubble.get_sr());
    Form1->StringGrid2->Cells[4][k*d/t+1]=IntToStr(arr_bubble.get_obm());
    Form1->StringGrid1->Cells[5][k*d/t+1]=IntToStr(arr_quick.get_sr());
    Form1->StringGrid2->Cells[5][k*d/t+1]=IntToStr(arr_quick.get_obm());
    }
    current+=1;
    ProgressBar1->Position=100*current/count;
    }
    sort->Enabled=false;
    }
    //---------------------------------------------------------------------------
    AnsiString fn1="swap.bmp",fn2="select.bmp",fn3="insert.bmp",
    fn4="bubble.bmp",fn5="quick.bmp";
    void __fastcall TForm1::N2Click(TObject *Sender)
    {
    Form1->Image1->Picture->LoadFromFile(fn1);
    Form1->Image2->Picture->LoadFromFile(fn2);
    Form1->Image3->Picture->LoadFromFile(fn3);
    Form1->Image4->Picture->LoadFromFile(fn4);
    Form1->Image5->Picture->LoadFromFile(fn5);
    }
    //---------------------------------------------------------------------------
    void __fastcall TForm1::N3Click(TObject *Sender)
    {
    Form1->Chart1->SaveToBitmapFile(fn1);
    Form1->Chart2->SaveToBitmapFile(fn2);
    Form1->Chart3->SaveToBitmapFile(fn3);
    Form1->Chart4->SaveToBitmapFile(fn4);
    Form1->Chart5->SaveToBitmapFile(fn5);
    MessageBox(NULL,"Все графики выведены в файлы!","5 пар графиков!",MB_OK);
    }
    //---------------------------------------------------------------------------
    void __fastcall TForm1::N1Click(TObject *Sender)
    {
    Form1->Chart1->SaveToBitmapFile(fn1);
    MessageBox(NULL,"Графики (обменами) выведены в файл!","Сортировка обменами",MB_OK);
    }
    //---------------------------------------------------------------------------
    void __fastcall TForm1::N4Click(TObject *Sender)
    {
    Form1->Image1->Picture->LoadFromFile(fn1);
    }
    //---------------------------------------------------------------------------
    void __fastcall TForm1::N5Click(TObject *Sender)
    {
    Form1->Chart2->SaveToBitmapFile(fn2);
    MessageBox(NULL,"Графики (выбором) выведены в файл!","Сортировка выбором",MB_OK);
    }
    //---------------------------------------------------------------------------
    void __fastcall TForm1::N6Click(TObject *Sender)
    {
    Form1->Image2->Picture->LoadFromFile(fn2);
    }
    //---------------------------------------------------------------------------
    void __fastcall TForm1::N7Click(TObject *Sender)
    {
    Form1->Chart3->SaveToBitmapFile(fn3);
    MessageBox(NULL,"Графики (вставками) выведены в файл!","Сортировка вставками",MB_OK);
    }
    //---------------------------------------------------------------------------

    void __fastcall TForm1::N8Click(TObject *Sender)
    {
    Form1->Image3->Picture->LoadFromFile(fn3);
    }
    //---------------------------------------------------------------------------

    void __fastcall TForm1::N9Click(TObject *Sender)
    {
    Form1->Chart4->SaveToBitmapFile(fn4);
    MessageBox(NULL,"Графики (пузырьком) выведены в файл!","Сортировка пузырьком",MB_OK);
    }
    //---------------------------------------------------------------------------

    void __fastcall TForm1::N10Click(TObject *Sender)
    {
    Form1->Image4->Picture->LoadFromFile(fn4);
    }
    //---------------------------------------------------------------------------

    void __fastcall TForm1::N11Click(TObject *Sender)
    {
    Form1->Chart5->SaveToBitmapFile(fn5);
    MessageBox(NULL,"Графики (быстрая) выведены в файл!","Быстрая сортировка",MB_OK);
    }
    //---------------------------------------------------------------------------

    void __fastcall TForm1::N12Click(TObject *Sender)
    {
    Form1->Image5->Picture->LoadFromFile(fn5);
    }
    //---------------------------------------------------------------------------

    void __fastcall TForm1::helpClick(TObject *Sender)
    {
    MessageBox(NULL,"Разработаны в 2012 г. ","Рекурсивные функции для сортировки массивов",MB_OK);
    }
    //--------------------------------------------------------------------------
    Это я сделал...

    Второе задание:

    6. Разработайте алгоритмы сортировок с помощью циклов (кроме быстрой сортировки) и напишите код для подраздела циклами с последующей отладкой и получением графически представляемых зависимостей, увеличив не менее чем на порядок размер сортируемых массивов и диапазон значений элементов массивов. Объясните полученные результаты.

    Вот сдесь я и встал... Не знаю что делать! Кто поможет?
    Если что файлы прикреплены. Посмотреть вложение Программа.rar
     
  2. Miller85

    Miller85 Гость

    Кто-нибудь поможет?
     
Загрузка...

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