Форум программистов, компьютерный форум, киберфорум
Delphi для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
5 / 5 / 1
Регистрация: 09.12.2020
Сообщений: 194
1

Неправильный Qsort

09.12.2020, 11:43. Показов 1345. Ответов 13

Author24 — интернет-сервис помощи студентам
==Delphi7

Если я использую классику сортировки, то все сортируется правильно, даже если я использую массив ссылок на массив входа байтов, которые надо сортировать. То есть, если в текущем коде вот это, то сортируется правильно

Delphi
1
2
while a [i] < x do i:=i+1;
while x < a [j] do j:=j-1;
Но если я меняю на простую функцию

Delphi
1
2
while CmpByte (a [i], x) do i:=i+1;
while CmpByte (x, a [j]) do j:=j-1;
то все меняется, массив сортируется не полностью, есть мусор на выходе.
Испробовал все, давал адреса в функцию, смещения и прочее, все неправильно, даже если сделать вот так, то неправильно сортирует

Delphi
1
2
3
4
Function CmpByte (a, b: byte): boolean;
begin
Result:= a < b;
end;
Не могу понять где косяк, в дебаге адреса передаются правильно.

Добавлено через 3 часа 43 минуты
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
procedure Qsort (l,r: longint); // Работает нормально, правильная сортировка
var
  i,j,x,y: longint;
begin
  i:=l; j:=r;
  x:=a [(l+r) shr 1];
  repeat
while a[i] < x do i:=i+1;
while x < a[j] do j:=j-1;
    if i<=j then begin y:=a[i]; a[i]:=a[j]; a[j]:=y;  i:=i+1; j:=j-1; end;
  until i>j;
  if l<j then qsort( l,j);
  if i<r then qsort( i,r);
end;
////////////////////////////////////////////////////////////////////////////////
Delphi
1
2
3
4
5
6
function CmpByte (a, b: byte): boolean; //Не работает
begin
  Result := false;
  if a <  b then Result := true;
  // или так // if a <  b then Result := true else Result := false; //Не работает
end;
////////////////////////////////////////////////////////////////////////////////
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 procedure Qsort2 (l,r: byte); // Не работает
var
  i,j,x,y: longint;
begin
  i:=l; j:=r;
  x:=a [(l+r) shr 1];
  repeat
while CmpByte (a [i], x)  do i:=i+1;
while CmpByte (x,  a[j])  do j:=j-1;
    if i<=j then begin y:=a[i]; a[i]:=a[j]; a[j]:=y;  i:=i+1; j:=j-1; end;
  until i>j;
  if l<j then qsort2( l,j);
  if i<r then qsort2( i,r);
end;
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.12.2020, 11:43
Ответы с готовыми решениями:

Неправильный логин и неправильный пароль, программа не выдает сообщения об ошибке
Вообщем проблема такова: DBConnect-&gt;ConnectionString = &quot;Provider=SQLOLEDB.1;Password=&quot; +...

Неправильный парсинг строки и неправильный её вывод
Добрый день! Столкнулся с непонятным поведением парсера: На вход подается вот такая строка: ...

qsort
Ребят,расскажи подробно и простенько про qsort;Видел тему,но ничего не понял.Я новичек еще можно...

qsort
Вот код программы. Посмотрите вопрос в комментарии. #include &lt;iostream&gt; #include &lt;stdlib.h&gt; ...

13
3759 / 2263 / 705
Регистрация: 29.05.2013
Сообщений: 9,613
09.12.2020, 12:11 2
Delphi
1
2
3
4
Function CmpByte (a, b: byte): boolean;
begin
Result:= a < b;
end;
Boolean имеет только 2 значения - True/False, а сравнение 3 - Меньше,Больше,Равно.
Если a>b или a=b функция будет возвращать все равно False, вот и получаете неправильный результат сортировки
0
5 / 5 / 1
Регистрация: 09.12.2020
Сообщений: 194
09.12.2020, 12:12  [ТС] 3
Сильно сомневаюсь, что настройки виноваты
Миниатюры
Неправильный Qsort  
0
5 / 5 / 1
Регистрация: 09.12.2020
Сообщений: 194
09.12.2020, 12:20  [ТС] 4
Цитата Сообщение от Пытливый Посмотреть сообщение
Если a>b или a=b функция будет возвращать все равно False, вот и получаете неправильный результат сортировки
Неправильный ?
while a[i] < x do i:=i+1; // именно так в оригинале работает нормально

Аналогично в Function CmpByte (a, b: byte): boolean;
Result:= a < b;

У меня большая просьба проверить этот код в Дельфи, пжлста )))
0
3759 / 2263 / 705
Регистрация: 29.05.2013
Сообщений: 9,613
09.12.2020, 12:28 5
Массив А у вас какого типа?
0
5 / 5 / 1
Регистрация: 09.12.2020
Сообщений: 194
09.12.2020, 12:41  [ТС] 6
Delphi
1
2
3
4
5
6
type
 ar1 = array [0..$7fffffff -1] of byte; 
 arrayByte=^ar1;
 
var
  A: arrayByte;
Проблема в том, что обычный Qsort сортирует нормально, а если подключаю функцию, то идут ошибки.

Delphi
1
2
3
begin
//QSort (0, fs-1); //нормально
QSort2 ( 0, fs-1); //ошибки на выходе
0
3759 / 2263 / 705
Регистрация: 29.05.2013
Сообщений: 9,613
09.12.2020, 12:46 7
А вы измените размерность массива
Delphi
1
2
type
ar1 = array [0..255] of byte;
что-то мне подсказывает, что сортировка будет правильной.
0
5 / 5 / 1
Регистрация: 09.12.2020
Сообщений: 194
09.12.2020, 12:50  [ТС] 8
Мне надо сортировать от 100 Мб и выше
На 10 символах в файле я трассировал, все правильно, конечно 1к байт и выше отследить невозможно.

Можете проверить код ?
0
5 / 5 / 1
Регистрация: 09.12.2020
Сообщений: 194
09.12.2020, 13:04  [ТС] 9
Проблема именно в функции. Я уже вкладывал ее в процедуру, все равно не работает, как надо, есть ошибки
Миниатюры
Неправильный Qsort  
0
5 / 5 / 1
Регистрация: 09.12.2020
Сообщений: 194
10.12.2020, 09:41  [ТС] 10
Я вспомнил, эта проблема была и раньше, но я переписал фукцию сравнения на ассемблер и проблема была решена, все сортировалось правильно. Листинг ассемблера остался, но как переписать на Вин32-64 даже не знаю, немного погуглил, 4 регистра точно надо сохранять, но как добраться к адресу данных через AllocMem, я не знаю.
Если я понял правильно, регистры называются как AX -> EAX(32) RAX(64), но непонятно, как получить адрес и писать туда байты. Все равно придется переписывать на ассемблер для скорости, может кто поможет ?
0
Модератор
3751 / 2251 / 782
Регистрация: 15.11.2015
Сообщений: 8,964
10.12.2020, 12:43 11
Цитата Сообщение от West2000 Посмотреть сообщение
Result := false;
if a < b then Result := true;
Лучше так:
Delphi
1
2
3
4
function CmpByte (a, b: byte): boolean; 
begin
  Result := a <  b;
end;
0
5 / 5 / 1
Регистрация: 09.12.2020
Сообщений: 194
10.12.2020, 12:46  [ТС] 12
Цитата Сообщение от AzAtom Посмотреть сообщение
Лучше так:
Все равно не работает, массив конечно сортируется, но на выходе есть частично мусор.
0
Модератор
3751 / 2251 / 782
Регистрация: 15.11.2015
Сообщений: 8,964
10.12.2020, 13:33 13
Лучший ответ Сообщение было отмечено West2000 как решение

Решение

Цитата Сообщение от West2000 Посмотреть сообщение
но на выходе есть частично мусор.
Цитата Сообщение от West2000 Посмотреть сообщение
У меня большая просьба проверить этот код в Дельфи, пжлста )))
Где минимальный проект, в котором это проявляется? Или предлагаешь нам самостоятельно додумать и собирать проект?
1
5 / 5 / 1
Регистрация: 09.12.2020
Сообщений: 194
10.12.2020, 18:52  [ТС] 14
Мдя уж... Вычистил все, чтобы минимально получилось.
Все заработало нормально... Непонятно..

Delphi
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
unit Unit1;
{$APPTYPE CONSOLE}
 
interface
 
uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs;
 
type
  TForm1 = class(TForm)
    procedure FormCreate(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;
 
var
  Form1: TForm1;
 
implementation
 
{$R *.dfm}
 
 
 
 
 
  type
 ar1 = array [0..$7fffffff -1] of byte; arrayByte=^ar1;
 
var
 fs, n,  i: longint;
 A, aa, aBin: arrayByte;
 
 
 
 
/////////////////////////////////////////////////////////////////////////////////////////////
 procedure Qsort (l,r: longint);
var
  i,j,x,y: longint;
begin
  i:=l; j:=r;
  x:=a [(l+r) shr 1];
  repeat
while a[i] < x do i:=i+1;
while x < a[j] do j:=j-1;
    if i<=j then begin y:=a[i]; a[i]:=a[j]; a[j]:=y;  i:=i+1; j:=j-1; end;
  until i>j;
  if l<j then qsort( l,j);
  if i<r then qsort( i,r);
end;
 
 
////////////////////////////////////////////////////////////////////////////////
function CmpByte (a, b: byte): boolean;
begin
  Result := a <  b;
end;
////////////////////////////////////////////////////////////////////////////////
 procedure Qsort2 (l,r: longint); //
var
  i,j,x,y: longint;
begin
  i:=l; j:=r;
  x:=a [(l+r) shr 1];
  repeat
while CmpByte (a[i], x) do i:=i+1;
while CmpByte (x, a[j]) do j:=j-1;
    if i<=j then begin y:=a[i]; a[i]:=a[j]; a[j]:=y;  i:=i+1; j:=j-1; end;
  until i>j;
  if l<j then qsort( l,j);
  if i<r then qsort( i,r);
end;
 
 
 
 
 
 
//////////////////////////////////////////////////////////////////
Procedure Sort ( s, ss:longint);
 var x,y: longint;
begin
//QSort (0, fs-1); //OK Sort
QSort2 ( 0, fs-1); //Not work
end;
 
 
 
 
 
/////////////////////////////////////////////////////////////////
var
f, ff, fbin:file;
yy, z, x: longint;
s, sf: string;
 
procedure TForm1.FormCreate(Sender: TObject);
begin
sf:='enwik5'; //100 Kb
 
AssignFile (f,sf); Reset(f,1); fs:= FileSize(f);
AssignFile (ff,'out.txt');     Rewrite(ff,1);
A:=AllocMem(fs);               Blockread (f, A[0], fs); CloseFile(f);
 
writeln('Sorting:');
//for x:=0 to fs-1 do   write (IntToStr(aaa[x]) + '-'); writeln;
 
Sort (0, fs-1);
writeln(s);
 
 
BlockWrite(ff, a[0], fs); CloseFile(ff);
FreeMem(A); //, fs);
 
writeln('Press any key...');
readln;
halt;
end;
 
end.
Добавлено через 4 часа 49 минут
В общем, я подумал и у меня только одна версия - компилятор сохранил настройки неправильно, хотя код вроде работает, но частично не совсем так. Такое уже было, только сейчас об этом вспомнил.
Код я почистил от лишнего, сделал новый проект и вставил туда код, только тогда заработало правильно. Наверное и с исходным кодом все работать будет, надо проверить.
Итого - код работает правильно, но крови мне компилятор Дельфи7 попил много, неделя впустую, я уже подумал, что чего-то не понимаю, поэтому обратился сюда на сайт.
Но и Дельфи10.2 тоже не идеал, глючит иногда, вот почему я проверяю критичный код в 2 компиляторах.
Почему Дельфи7 ? Все равно надо делать 32-64 бит версии, а 7 быстрей будет работать, ну и размер меньше, это не суть важно, но все таки.
Сейчас проверил сортировку на 100 МБ, заодно подключил таймер, все работает правильно. Ну и собсно хочу сказать спасибо сайту, проблему решили вместе. )))

Просто когда много кода, сложно понять, где косяк, начинаю упрощать код для проверки и опять ошибка, мозг кипит..

В качестве последней информации, которую недавно проверил. В тырнете не все так однозначно описано...
MergeSort, ну да, работает быстро, но мне не применить его. Еще быстрее работает пирамидальная сортировка, уже можно применить для меня, там линейная скорость. Но в любом случае, Qsort работает быстрее, но там другая проблема - он затыкается на одинаковых строках и начинает тормозить. Это решается предсортировкой AnySort или сортировка выбором, а потом уже применить Qsort, вполне нормальная скорость сортировки получается. Ну а если Qsort переписать на ассемблер, то скорость повышается 10-100 раз, причем не весь сорт, а только процедуру сравнения строк, проверял раньше практически.
До RadixSort еще не добрался, наверное не слишком быстро будет, подожду. Стал делать свою сортировку, но пока логику обдумываю, код будет короткий, но надо все продумать.
Вот так незаметно накопилось много кода и компилятор глюкнул. Если включена Оптимизация, то скорость увеличивается примерно на 20%, но есть опасность генерации неправильного кода, поэтому я пишу черновик без Оптимизации и проверяю. Ну вот добавилось еще неправильное сохранение настроек...

Ну что же, может еще что спрошу, сильно не ругайте меня )))
0
10.12.2020, 18:52
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.12.2020, 18:52
Помогаю со студенческими работами здесь

qSort
Есть класс: class Student { public: QString name; QString last_name; QString phone_number;...

qsort C++
Помогите, плиз,разобраться с этой функцией, я прогу написала, но мало чего понимаю в ней, я...

qsort
Вот код: #include &lt;cstdio&gt; #include &lt;algorithm&gt; int compare(const void *s1, const void *s2) {...

qsort
int *noth_ar=new int ; //-------------------------------------------- int noth_cmp(const void...

qsort
читал, что с помощю QSORT можно упорядочить масив, но не пишет как. помогите!!

Вопрос по ()qsort
есть массив, который разбивает предложение на слова. надо отсортировать все слова в порядке ...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru