Форум программистов, компьютерный форум, киберфорум
C++ Builder
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
DeadZone
3 / 3 / 1
Регистрация: 03.10.2009
Сообщений: 157
1

Быстрая сортировка

13.07.2013, 13:56. Просмотров 830. Ответов 3
Метки нет (Все метки)

Добрый день.
Задание такое :
1) Для “быстрой сортировки” получить зависимость затрат машинного времени от длины массива.
2)Получить также указанную зависимость для пересортировки упорядоченного массива.

1-е сделано, и работает нормально. 2-е сделано, на работает не правильно (почему-то не сортирует).
Для 1 задания массив a , для второго массив b.

Вопрос: как заполнить массив b, например из Edit1?Может я заполняю его не правильно?

Вот код:
Класс:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class array{
        public:
          array(int);                   //êîíñòðóêòîð 1 (ñ ïàðàìåòðîì)
          array(array&);                //êîíñòðóêòîð 2 (êîïèè)
          void swap(int&,int&);  //îáìåí ýëåìåíòîâ â ñîðòèðóåìîì ìàññèâå
          void QuickSort(int,int,int);         //áûñòðàÿ ñîðòèðîâêà
          void out_mass_a()const; //âûâîä èñõîäíîãî è
                                                  //îòñîðòèðîâàííîãî ìàññèâîâ a
          int get_sr()const{return sr;}  //ïîëó÷èòü ñðàâíåíèÿ
          int get_obm()const{return obm;}//ïîëó÷èòü îáìåíû
          void out_mass_b()const; // âûâîä èñõîäíîãî è îòñîðòèðîâàííîãî ìàññèâà b
          ~array(){delete[]a;delete[]b;}          //äåñòðóêòîð
        private:
          int*a,  //óêàçàòåëü äëÿ èñõîäíîãî ñîðòèðóåìîãî ìàññèâà
             *b, // óêàçàòåëü äëÿ 2-ãî ìàññèâà
             chet,  //ñ÷åò÷èê äëÿ âòîðîãî ìàññèâà
             sr,  //ñðàâíåíèÿ
             obm, //îáìåíû
             n; //ðàçìåð èñõîäíîãî ñîðòèðóåìîãî ìàññèâà
           };
Код :

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
int razm_min,razm_max,d,m,max_d,min_d,razm_out;
//---------------------------------------------------------------------------
array::array(int p)
{n=p;
 a=new int[n];
 b=new int[n];
 sr=0;
 obm=0;
 chet=n;
 for(int i=0;i<n;i++) a[i]=random(max_d-min_d+1)+min_d;
 for(int j=0;j<n;j++) b[j]=--chet;
}
//---------------------------------------------------------------------------
array::array(array&c)
{n=c.n; sr=c.sr; obm=c.obm;
 a=new  int[n];
 b=new int[n];
 for(int i=0;i<n;i++)a[i]=c.a[i];
 for(int j=0;j<n;j++)b[j]=c.b[j];
}
//---------------------------------------------------------------------------
void array::swap(int&x,int&y)
{int z=x;x=y;y=z;}
//---------------------------------------------------------------------------
 
//---------------------------------------------------------------------------
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 array::out_mass_a()const
{
AnsiString str="";
for(int i=0;i<n;i++)str+="   "+IntToStr(a[i]);
Form1->Memo1->Lines->Add(str);
 
}
 
void array::out_mass_b()const
{
AnsiString str1="";
for(int j=0;j<n;j++)str1+="   "+IntToStr(b[j]);
Form1->Memo1->Lines->Add(str1);
 
}
//---------------------------------------------------------------------------
void __fastcall TForm1::BitBtn1Click(TObject *Sender)
{
Memo1->Clear();
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]="áûñòðàÿ2";
StringGrid2->Cells[0][0]="ðàçìåð";
StringGrid2->Cells[1][0]="áûñòðàÿ";
StringGrid2->Cells[2][0]="áûñòðàÿ2";
Series1->Clear();
Series2->Clear();
Series9->Clear();
Series10->Clear();
 
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;
Button1->Enabled=true;
}
 
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button1Click(TObject *Sender)
{
StringGrid1->RowCount=m;
StringGrid2->RowCount=m;
for(int k=0;k<m;k++){
                array arr(razm_min+k*d);
        array arr_quick1=arr;
        if(razm_min+k*d==razm_out){
                Form1->Memo1->Lines->Add("Исходный массив");
                arr_quick1.out_mass_a();}
        arr_quick1.QuickSort(0,razm_min+k*d-1,k);
        Form1->Series9->AddXY(razm_min+k*d,arr_quick1.get_sr(),"",clRed);
        Form1->Series10->AddXY(razm_min+k*d,arr_quick1.get_obm(),"",clGreen);
        if(razm_min+k*d==razm_out){
                Form1->Memo1->Lines->Add("Полученный массив");
                arr_quick1.out_mass_a();}
              Form1->StringGrid1->Cells[0][k*d+1]=IntToStr(razm_min+k*d);
              Form1->StringGrid2->Cells[0][k*d+1]=IntToStr(razm_min+k*d);
              Form1->StringGrid1->Cells[1][k*d+1]=IntToStr(arr_quick1.get_sr());
              Form1->StringGrid2->Cells[1][k*d+1]=IntToStr(arr_quick1.get_obm());
//------------------------------------------------------------------------------
        array arr_quick2=arr;
        if(razm_min+k*d==razm_out){
                Form1->Memo1->Lines->Add("Исходный массив(пересортировка)");
                arr_quick2.out_mass_b();}
        arr_quick2.QuickSort(0,razm_min+k*d-1,k);
        Form1->Series1->AddXY(razm_min+k*d,arr_quick2.get_sr(),"",clRed);
        Form1->Series2->AddXY(razm_min+k*d,arr_quick2.get_obm(),"",clGreen);
        if(razm_min+k*d==razm_out){
                Form1->Memo1->Lines->Add("Полученный массив(пересортировка)");
                arr_quick2.out_mass_b();}
              Form1->StringGrid1->Cells[2][k*d+1]=IntToStr(arr_quick2.get_sr());
              Form1->StringGrid2->Cells[2][k*d+1]=IntToStr(arr_quick2.get_obm());
        }
Button1->Enabled=false;
}
//---------------------------------------------------------------------------
Почему не выполняется сортировка 2-го массива?Может размер задан не правильно? или ошибка в коде?
0
Миниатюры
Быстрая сортировка   Быстрая сортировка  
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.07.2013, 13:56
Ответы с готовыми решениями:

Сортировка Хоара (быстрая сортировка) по убыванию
Помогите найти/написать/понять/отобразить как пишется код для данного задания или хотя бы часть...

Сортировка методом Шелла и быстрая сортировка
Помогите найти код для функций в виде кусков кода сортировок...

Быстрая сортировка
Написал алгоритм точнее собрал его из выложенных кодов на просторах сети.... Но не пойму в чем...

Быстрая сортировка.!!!!
помогите написать программу быстрой сортировки массива из 12 чисел.!

3
DeadZone
3 / 3 / 1
Регистрация: 03.10.2009
Сообщений: 157
13.07.2013, 14:46  [ТС] 2
Понял что сортировка вызывается второй раз для массива a.
0
DeadZone
3 / 3 / 1
Регистрация: 03.10.2009
Сообщений: 157
13.07.2013, 15:00  [ТС] 3
Вроде все нормально сортирует, но почему центральный элемент остается первым?

Добавил ещё одну сортировку, для массива b

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void array::QuickSort1(int lb,int hb ,int kb)
{ int sub,sdb,mb,pb;
  if(hb-lb<=0) return;
    else if(hb-lb==1) {
                     if(b[hb]<b[lb]) {swap(b[lb],b[hb]); obm++;}
                     sr++;
                     return;
                    }
  mb=(lb+hb)/2;  pb=b[mb];  swap(b[mb],b[lb]); obm++; sub=lb+1;sdb=hb;
  do{
        while(sub<=sdb && b[sub]<=pb) {sub++; sr++;}
        while(pb<b[sdb]) {sdb--; sr++;}
        if(sub<sdb) {swap(b[sub],b[sdb]); obm++; }
    } while(sub<sdb);
  b[lb]=b[sdb]; b[sdb]=pb; obm++;
  if(lb<sdb-1) QuickSort(lb,sdb-1,kb);
  if(sdb+1<hb) QuickSort(sdb+1,hb,kb);
}
0
Миниатюры
Быстрая сортировка  
DeadZone
3 / 3 / 1
Регистрация: 03.10.2009
Сообщений: 157
13.07.2013, 21:15  [ТС] 4
Можно ли сделать это все через один массив?
сначала массив заполнить одними значениями, отсортировать вывести, потом этот же массив другими заполнить другими значениями, отсортировать, вывести?

Добавлено через 1 час 9 минут
Все сделал
0
13.07.2013, 21:15
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.07.2013, 21:15

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

Быстрая сортировка массива
Анализ процедуры &quot;быстрой&quot; сортировки. Получить временные данные по сортировке разновеликих...

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

Быстрая сортировка строки StringGrid
Ребят, помогите, нужен код Быстрой сортировки одной строки StringGrid.

Разработать программу сортировки: сортировка перестановкой, сортировка вставкой, быстрая сортировка
Задание: Разработать программу сортировки: - сортировка перестановкой - сортировка...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.