Реализация весовой функции для qsort (crt_qsort) из msvcrt.dll

ФедосеевПавел · Регистрация: 01.02.2015

Студворк — интернет-сервис помощи студентам

Столкнулся с неожиданным поведением функции qsort из msvcrt.dll.

Собрал тестовый пример для массива чисел со знаком
Весовую функцию сделал упрощённую, всего на 2 варианта (как видел в некоторых примерах)

C
1
2
3
4
5
6
7
int Compare(int * a, int * b)
{
  if(*a > *b)
    return 1;
  else
    return 0;
};

Получил такой исходник для тестового массива на 8 элементов

Кликните здесь для просмотра всего текста

Assembler
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
.686
.model flat, stdcall
option casemap :none
        .nolist
        include \masm32\include\windows.inc
 
        include \masm32\include\user32.inc
        include \masm32\include\kernel32.inc
        include \masm32\include\msvcrt.inc
        include \masm32\include\masm32.inc
        include \masm32\macros\macros.asm
 
        includelib \masm32\lib\user32.lib
        includelib \masm32\lib\kernel32.lib
        includelib \masm32\lib\msvcrt.lib
        includelib \masm32\lib\masm32.lib
        .list
.const
        aszPressAnyKey          db      0Dh, 0Ah, 0Dh, 0Ah, "Press any key to exit", 0
.data
        Array                   dd      1, 8, -5, 97, 100, -5, 8, -15
        n                       dd      LENGTHOF Array
.data?
 
.code
 
ShowArray       proc    lpArray:DWORD, nCount:DWORD
        mov     esi,    [lpArray]
        mov     ecx,    [nCount]
        @@:
                push    ecx
                push    esi
                printf("%8d", dword ptr[esi])
                pop     esi
                pop     ecx
                add     esi,    4
        loop    @b
        ret
ShowArray       endp
 
;весовая функция
Compare proc    ;lpA:DWORD, lpB:DWORD
        mov     eax,    [esp+4]
        mov     edx,    [esp+8]
        mov     eax,    [eax]
        mov     edx,    [edx]
        cmp     eax,    edx
        setg    al
        movzx   eax,    al
        ret
Compare endp
 
main    proc
 
        ;вывод исходного массива
        printf("Before sort (length=%d):\n", [n])
        invoke  ShowArray,      ADDR Array, [n]
        ;сортировка массива
        invoke  crt_qsort,      ADDR Array,  [n], TYPE Array, ADDR Compare
        ;вывод обработанного массива
        printf("\n\nAfter sort (length=%d):\n", [n])
        invoke  ShowArray,      ADDR Array, [n]
        ;ожидание нажатия любой клавиши
        invoke  crt_printf,     ADDR aszPressAnyKey
        invoke  crt__getch
        ;завершение программы
        invoke  ExitProcess,    0
main    endp
 
end     main

Результат прогона вполне ожидаемый

Code
1
2
3
4
5
6
7
Before sort (length=8):
       1       8      -5      97     100      -5       8     -15
 
After sort (length=8):
     -15      -5      -5       1       8       8      97     100
 
Press any key to exit

Увеличиваю размер массива до 10 элементов - заменяю строку

Assembler
21
        Array                   dd      1, 8, -5, 97, 100, -5, 8, -15, 31, -1

Результат прогона уже удивляет

Code
1
2
3
4
5
6
7
Before sort (length=10):
       1       8      -5      97     100      -5       8     -15      31      -1
 
After sort (length=10):
      -5     -15      -5      -1       1       8       8      31      97     100
 
Press any key to exit

В результате экспериментов пришёл к выводу, что для корректной работы qsort из msvcrt при длине сортируемого массива более 8 элементов требуется полная реализация весовой функции - с тремя вариантами выходных значений

C
1
2
3
4
5
6
7
8
9
int Compare(int * a, int * b)
{
  if(*a > *b)
    return 1;
  if(*a == *b)
    return 0;
  if(*a < *b)
    return -1;
};

Для чисел с учётом знака получил

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
;весовая функция
Compare proc    ;lpA:DWORD, lpB:DWORD
        mov     eax,    [esp+4]
        mov     edx,    [esp+8]
        mov     eax,    [eax]
        mov     edx,    [edx]
        cmp     eax,    edx
        setg    al
        setl    ah
        sub     al,     ah
        movsx   eax,    al
        ret
Compare endp

Весь код в сборе

Кликните здесь для просмотра всего текста

Assembler
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
.686
.model flat, stdcall
option casemap :none
        .nolist
        include \masm32\include\windows.inc
 
        include \masm32\include\user32.inc
        include \masm32\include\kernel32.inc
        include \masm32\include\msvcrt.inc
        include \masm32\include\masm32.inc
        include \masm32\macros\macros.asm
 
        includelib \masm32\lib\user32.lib
        includelib \masm32\lib\kernel32.lib
        includelib \masm32\lib\msvcrt.lib
        includelib \masm32\lib\masm32.lib
        .list
.const
        aszPressAnyKey          db      0Dh, 0Ah, 0Dh, 0Ah, "Press any key to exit", 0
.data
        Array                   dd      1, 8, -5, 97, 100, -5, 8, -15, 31, -1
        n                       dd      LENGTHOF Array
.data?
 
.code
 
ShowArray       proc    lpArray:DWORD, nCount:DWORD
        mov     esi,    [lpArray]
        mov     ecx,    [nCount]
        @@:
                push    ecx
                push    esi
                printf("%8d", dword ptr[esi])
                pop     esi
                pop     ecx
                add     esi,    4
        loop    @b
        ret
ShowArray       endp
 
;весовая функция
Compare proc    ;lpA:DWORD, lpB:DWORD
        mov     eax,    [esp+4]
        mov     edx,    [esp+8]
        mov     eax,    [eax]
        mov     edx,    [edx]
        cmp     eax,    edx
        setg    al
        setl    ah
        sub     al,     ah
        movsx   eax,    al
        ret
Compare endp
 
main    proc
 
        ;вывод исходного массива
        printf("Before sort (length=%d):\n", [n])
        invoke  ShowArray,      ADDR Array, [n]
        ;сортировка массива
        invoke  crt_qsort,      ADDR Array,  [n], TYPE Array, ADDR Compare
        ;вывод обработанного массива
        printf("\n\nAfter sort (length=%d):\n", [n])
        invoke  ShowArray,      ADDR Array, [n]
        ;ожидание нажатия любой клавиши
        invoke  crt_printf,     ADDR aszPressAnyKey
        invoke  crt__getch
        ;завершение программы
        invoke  ExitProcess,    0
main    endp
 
end     main

И результат прогона

Code
1
2
3
4
5
6
7
Before sort (length=10):
       1       8      -5      97     100      -5       8     -15      31      -1
 
After sort (length=10):
     -15      -5      -5      -1       1       8       8      31      97     100
 
Press any key to exit

Вот такое неожиданное поведение подпрограммы - а в документации нет ни слова об обязательной реализации всех ветвей весовой функции.
Или же я что-то упускаю в реализации.

@Jin X · 19.05.2021, 19:34

Ну как же нет?

Подпрограмма сравнивает элементы и возвращает одно из следующих значений.

Сравнение возвращаемого значения функции	Описание
< 0	elem1 меньше elem2
0	elem1 эквивалентно elem2
> 0	elem1 больше elem2

P.S.

Сообщение от ФедосеевПавел

Assembler
32
push    esi

Зачем это? EBX, ESI, EDI, EBP вызываемые функции менять не будут.

ФедосеевПавел · 19.05.2021, 21:09 **[ТС]**

С весовой функцией получилось так
- по инерции аналогий - в алгоритмах сортировки всё решается одним сравнением
- в документации не требуется обязательность трёх ветвей
- на форуме нашёл всего несколько примеров этой функции и все от одного авторитетного пользователя - нет и не было здесь других образцов
https://www.cyberforum.ru/fasm/thread1396080.html
Error: expression syntax error, NASM
Не удается найти указаный файл при попытке запуска драйвера
- проверка упрощённой весовой функции на 5-8 (количества, удобно размещённого на экране в одну строку) элементах дала корректный результат.

push/pop esi - это в сердцах - цикл правильной но зависает (портит или ecx или esi) - что с ним разбираться, с медленным выводом на экран. Вот и сохранил esi.

@Jin X · 20.05.2021, 11:51

Вообще, алгоритм QuickSort можно, конечно, построить и на сравнении в одну сторону ("больше" или "меньше"). Но мы не знаем, как это реализовано внутри. Если бы это было неважно, тогда и требовалось бы возвратить только 0 или 1 (например, как в C++ делаются сравнения обычно по "меньше" <). А раз сделали функцию полного сравнения, значит это может иметь значение.

Добавлено через 4 минуты

Сообщение от ФедосеевПавел

в документации не требуется обязательность трёх ветвей

Как же не требуется, если написано, что функция должна возвращать -1, 0 или 1 ?

То, что на 5-8 сработало ни о чём не говорит. Может быть в данном примере ложные результаты сравнения по факту не повлияли на результат. А при других данных те же 5 значений могут быть отсортированы неправильно. Можете поэкспериментировать, если интересно (например, отсортировать 5,4,3,2,1 или 5,1,4,2,3 или 1,5,2,4,3 или ещё какие-то данные).
Более того, в одной версии библиотеки msvcrt может быть реализовано так, а в другой – иначе. И кто будет виноват в случае ошибки? Тот, кто не реализовал полную функцию, потому что в документации написано, что функция возвращает 3 значения.

Новые блоги и статьи Все статьи Все блоги /
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .

ФедосеевПавел Модератор 8644 / 4479 / 1669 Регистрация: 01.02.2015 Сообщений: 13,883 Записей в блоге: 11
	19.05.2021, 21:09 [ТС]
	С весовой функцией получилось так - по инерции аналогий - в алгоритмах сортировки всё решается одним сравнением - в документации не требуется обязательность трёх ветвей - на форуме нашёл всего несколько примеров этой функции и все от одного авторитетного пользователя - нет и не было здесь других образцов https://www.cyberforum.ru/fasm/thread1396080.html Error: expression syntax error, NASM Не удается найти указаный файл при попытке запуска драйвера - проверка упрощённой весовой функции на 5-8 (количества, удобно размещённого на экране в одну строку) элементах дала корректный результат. push/pop esi - это в сердцах - цикл правильной но зависает (портит или ecx или esi) - что с ним разбираться, с медленным выводом на экран. Вот и сохранил esi. 0