Форум программистов, компьютерный форум, киберфорум
Assembler для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
Assembler Вывод на экран длины введенной с клавиатуры строки https://www.cyberforum.ru/asm-beginners/thread389769.html
Граждане! Выручайте! Нужно разработать программу перевода ввода и вывода чисел в различных системах счисления, а также работы с числами в ассемблерных программах. Вывести на экран длину введенной с...
Assembler Деление двух целых пятизначных чисел(целая и дробная части)
Составить и отладить программу на ассемблере для нахождения результата деления двух целых пятизначных чисел, представленных в десятичном формате. Числа вводятся с клавиатуры. Результат вывести на...
Assembler Разбить число на цифры(тетрады)
Как на Ассемблере для процессора 80х86 разбить число на тетрады и каждую тетраду занести в отдельный регистр. Число 3EB7.
Assembler Максимальный элемент массива а(10) ... написать программу на assembler под Dos которая находит максимальный элемент массива а(10) меняет местами его с третьим по величине нечетным элементом с четным номером https://www.cyberforum.ru/asm-beginners/thread389491.html
Assembler программа должна выводить содержимое текстового файла на экран https://www.cyberforum.ru/asm-beginners/thread389487.html
программа должна выводить содержимое текстового файла на экран
Assembler Запись строки в обратной последовательности
Ребята! Помогите новичку. Нужно разработать программу, ввода строковых данных с клавиатуры. Произвести запись строки в обратной последовательности. Очень надеюсь на Вас!
Assembler Помогите сделать вывод на екран масива среднеарифмитического и минимального значения
.model small .stack 100h .data arr db 11,2,13,44,32,100,8,97,9 ;Массив. l=$-arr buf label byte ;Буфер для ввода. max db 80 ;Макс. число вводимых символов. lnt ...
Assembler Минимальный среди кратных 3 элементов массива а(15)поменять местами с первым элементом возрастающей последовательности м минимальный среди кратных 3 элементов массива а(15)поменять местами с первым элементом возрастающей последовательности массива https://www.cyberforum.ru/asm-beginners/thread389364.html
Assembler Через командную строку передать имя каталога и удалить этот каталог. https://www.cyberforum.ru/asm-beginners/thread389168.html
Здравствуйте, помогите пожалуйста с задачкой, задание в топе... Обработку командной строки необходимо организовать в виде макроса или процедуры. Пример: mov si,80h mov al,es: cmp al,0...
Assembler Заменить в строке встречающийся символ "a" на символ "k" Ввести строку символьных данных, задавая буфер равный 40 байт. Заменить в этой строке встречающийся символ "a" на символ "k". Выдать полученную строку символов в первую строку экрана, начиная с 12... https://www.cyberforum.ru/asm-beginners/thread389163.html
ФедосеевПавел
Модератор
6134 / 2926 / 1191
Регистрация: 01.02.2015
Сообщений: 9,473
Записей в блоге: 1
24.06.2019, 02:37 0

Программа для сортировки любого массива

24.06.2019, 02:37. Просмотров 46580. Ответов 14
Метки (Все метки)

Ответ

Пирамидальная сортировка, сортировка кучей (HeapSort)
массива знаковых целых чисел (Windows 32 бит)


К реализации Mikl___ из сообщения #4 добавлю собственную.
Различие лишь в подходах передачи параметров и несколько более развёрнутом пояснении источников алгоритма.

О пирамидальной сортировке и разновидностях её реализации можно почитать по ссылкам:
https://ru.wikipedia.org/wiki/Пирамидальная_сортировка
http://algolist.manual.ru/sort/pyramid_sort.php
https://www.codelab.ru/t/pyramid_sort/
Читать нужно внимательно, т.к. в статьях пояснения всегда приводятся для массива с индексацией от нуля, а примеры кода - то с индексацией от "0", то с индексацией от "1".

В Wikipedia приводится ссылка на примеры реализации в Wikibooks:
https://ru.wikibooks.org/wiki/Реализ.../Пирамидальная
https://en.wikibooks.org/wiki/Algori...rting/Heapsort
Также интересным будет ознакомление с реализациями на "розеттском коде":
http://rosettacode.org/wiki/Sorting_algorithms/Heapsort

Теория и рекурсивная реализация по данной ссылке, помогают лучше разобраться с алгоритмом:
https://evileg.com/ru/post/463/

Т.к. имеем дело с алгоритмом, а не с трюками для процессора, удобнее выбрать язык высокого уровня, реализовать на нём алгоритм и затем перевести отработанный код на ассемблер.

Мне удобнее реализовывать на Pascal.
Тестовая программа на Free Pascal
Pascal
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
program test_HeapSort;
 
const
  N = 10;
type
  TArray = array [0..N - 1] of integer;
 
 { алгоритм процедуры восстановления баланса пирамиды
  при добавлении нового A[k]
 
  A[]   - исходный массив
  K     - индекс добавляемого/просеиваемого элемента
  N     - максимальное значение индекса массива
 }
  procedure siftDown(var A: TArray; K, N: integer);
  var
    temp: integer;
    childPos: integer;
  begin
    {Это чтобы при K=0 И N=0 не делалось лишней перестановки}
    if 0 = N then
      exit;
(*
    while K * 2 + 1 <= N do
    begin
      childPos := 2 * K + 1;  // Индекс левого ребенка
 
      // выбираем в childPos индекс большего ребенка
      if (childPos + 1 <= N) and (A[childPos] < A[childPos + 1]) then
        Inc(childPos);
 
      // Если A[K] больше максимального ребенка - завершение
      if (A[K] >= A[childPos]) then
        break;
 
      // иначе - меняем его с наибольшим ребенком
      temp := A[K];
      A[K] := A[childPos];
      A[childPos] := temp;
 
      K := childPos;
    end;
*)
    temp := A[K];        // Оставляем копию
    while K * 2 + 1 <= N do
    begin
      childPos := 2 * K + 1;    // Индекс левого ребенка
 
      // выбираем в childPos индекс большего ребенка
      if (childPos + 1 <= N) and (A[childPos] < A[childPos + 1]) then
        Inc(childPos);
 
      // Если A[K] больше максимального ребенка - завершение
      if (temp >= A[childPos]) then
        break;
 
      // иначе - меняем его с наибольшим ребенком
      A[K] := A[childPos];
 
      K := childPos;
    end;
    {В конце восстанавливаем просеянному элементу
    его первоначальное значение}
    A[K] := temp;
  end;
 
  procedure HeapSort(var A: TArray; N: integer);
  var
    i: integer;
    temp: integer;
  begin
    { Построение пирамиды }
    for i := (N div 2) - 1 downto 0 do
      siftDown(A, i, N - 1);
    {Формирование конечной отсортированной
     последовательности + "балансирование"
     пирамиды }
    i := N - 1;
    while i > 0 do
    begin
      {меняем первый с последним}
      temp := A[0];
      A[0] := A[i];
      A[i] := temp;
      {Восстановление баланса для пирамиды A[0..i-1]}
      Dec(i);
      siftDown(A, 0, i);
    end;
  end;
 
  procedure ShowArray(const A: TArray; N: integer);
  var
    i: integer;
  begin
    for i := 0 to N - 1 do
      Write(A[i]: 3);
    writeln;
  end;
 
var
  A: TArray;
  i: integer;
begin
  randomize;
  for i := 0 to N - 1 do
    A[i] := random(100);
  ShowArray(A, N);
  HeapSort(A, N);
  ShowArray(A, N);
end.
Сделаю несколько примечаний по этой реализации.
За основу реализации был взят псевдокод по ссылке
https://www.codelab.ru/t/pyramid_sort/
Этот псевдокод содержит ошибки, исправить которые помогли сравнения с псевдокодом и реализацией по ссылке
http://rosettacode.org/wiki/Sorting_algorithms/Heapsort
Но в образцовом псевдокоде присутствует любопытная оптимизация процедуры siftDown - вместо обмена значений между "текущим корнем" и его "детьми", предлагается в корень помещать число, а само значение корня только хранить в переменной, чтобы по завершению цикла записать его в последнего просмотренного "ребёнка". Так несколько сокращается обращение к памяти и увеличивается скорость выполнения программы.

В моей реализации менее оптимальный (но более понятный) вариант заключён в комментарии.

Аккуратно перенося алгоритм на Ассемблер, получаем
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
;вспомогательная процедура для сортировки кучей
;алгоритм процедуры восстановления баланса пирамиды при добавлении нового A[K]
;  A[]   - исходный массив
;  K     - индекс добавляемого/просеиваемого элемента
;  N     - максимальное значение индекса массива
;процедура просеивания следующего элемента:
;До процедуры: A[K+1]...A[N]  - пирамида
;После:  A[K]...A[N]  - пирамида
siftDown        proc      lpArray:DWORD, K:DWORD, N:DWORD       ;procedure siftDown(var A: TArray; K, N: integer);
                                                                ;  var
                                                                ;    temp: integer;
                                                                ;    childPos: integer;
        pushad                                                  ;  begin
        mov     ebx,    [N]
        mov     esi,    [lpArray]
        mov     ecx,    [K]
                                                                ;    {Это чтобы при K=0 И N=0 не делалось лишней перестановки}
        test    ebx,    ebx                                     ;    if 0 = N then
        jz      _exit                                           ;      exit;
        mov     edi,    [esi+ecx*4]                             ;    temp := A[K];
        _while:                                                 ;    while K * 2 + 1 <= N do
                                                                ;    begin
                mov     edx,    ecx                             ;      childPos := 2 * K + 1;  // Индекс левого ребенка
                add     edx,    edx
                inc     edx
                cmp     edx,    ebx
                ja      _break
                                                                ;      // выбираем в childPos индекс большего ребенка
                mov     eax,    edx                             ;      if (childPos + 1 <= N) and (A[childPos] < A[childPos + 1]) then
                inc     eax
                cmp     eax,    ebx
                ja      @f
                mov     eax,    [esi+eax*4]
                cmp     eax,    [esi+edx*4]
                jle     @f
                inc     edx                                     ;        Inc(childPos);
        @@:                                                     ;
                                                                ;      // Если A[K] больше максимального ребенка - завершение
                cmp     edi,    [esi+edx*4]                     ;      if (temp >= A[childPos]) then
                jge     _break                                  ;        break;
                                                                ;
                                                                ;      // иначе - меняем его с наибольшим ребенком
                mov     eax,    [esi+edx*4]                     ;      A[K] := A[childPos];
                mov     [esi+ecx*4],    eax
                                                                ;
                mov     ecx,    edx                             ;      K := childPos;
        jmp     _while                                          ;    end;
_break:
        mov     [esi+ecx*4],    edi                             ;    A[K] := temp;
_exit:                                                          ;  end;
        popad
        ret
siftDown        endp
 
;сортировка кучей (пирамидальная сортировка)
;на входе:
;  lpArray  - адрес массива
;  uiAmount - длина массива
HeapSort        proc    lpArray:DWORD, uiAmount:DWORD                   ;  procedure HeapSort(var A: TArray; N: integer);
                                                                        ;  var
                                                                        ;    i: integer;
                                                                        ;    temp: integer;
        pushad                                                          ;  begin
        mov     esi,    [lpArray]
        mov     ebx,    [uiAmount]
        ;Построение пирамиды                                            ;    { Построение пирамиды }
        mov     ecx,    ebx                                             ;    for i := (N div 2) - 1 downto 0 do
        shr     ecx,    1
        dec     ebx     ;т.к. в дальнейшем нужно только значение (N-1)
        jmp     _next
        _for:
                invoke  siftDown,       esi, ecx, ebx                   ;      siftDown(A, i, N - 1);
        _next:
                dec     ecx
        jns     _for
                                                                        ;    {Формирование конечной отсортированной
                                                                        ;     последовательности + "балансирование"
                                                                        ;     пирамиды }
        mov     ecx,    ebx                                             ;    i := N - 1;
        jmp     _test_while                                             ;    while i > 0 do
        _while:                                                         ;    begin
                ;меняем первый с последним                              ;      {меняем первый с последним}
                push    dword ptr [esi]                                 ;      temp := A[0];
                push    dword ptr [esi+4*ecx]                           ;      A[0] := A[i];
                pop     dword ptr [esi]                                 ;      A[i] := temp;
                pop     dword ptr [esi+4*ecx]
                ;Восстановление баланса для пирамиды A[0..i-1]          ;      {Восстановление баланса для пирамиды A[0..i-1]}
                dec     ecx                                             ;      Dec(i);
                invoke  siftDown,       esi, 0, ecx                     ;      siftDown(A, 0, i);
        _test_while:                                                    ;    end;
                test    ecx,    ecx
        jnz     _while
        popad                                                           ;  end;
        ret
HeapSort        endp
Пример вызова
Assembler
1
2
3
4
        Array           dd      22,  8, 42,  7, 43, 81, 51, 14, 49,  7
        ASize           dd      LENGTHOF Array
....................................
        invoke  HeapSort,       ADDR Array, [ASize]
Тестовая программа
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
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
.686
.model flat, stdcall
option casemap :none
 
        include \masm32\include\windows.inc
 
        include \masm32\include\user32.inc
        include \masm32\include\kernel32.inc
        include \masm32\include\masm32.inc
 
        includelib \masm32\lib\user32.lib
        includelib \masm32\lib\kernel32.lib
        includelib \masm32\lib\masm32.lib
.data
        aszMsgInstant   db      0Dh, 0Ah, 'The data before sorting:', 0Dh, 0Ah, 0
        aszMsgResult    db      0Dh, 0Ah, 'The data after sorting:', 0Dh, 0Ah, 0
        aszInteger      db      '%4d', 0
        aszPressEnter   db      0Dh, 0Ah, 0Dh, 0Ah, "Press ENTER to exit", 0
        aszCrLf         db      0Dh, 0Ah, 0
        Array           dd      22,  8, 42,  7, 43, 81, 51, 14, 49,  7
        ASize           dd      LENGTHOF Array
 
.data?
        hConsoleOutput  HANDLE  ?
        hConsoleInput   HANDLE  ?
        Buffer          db      1024 dup(?)
        BufLen          dd      ?
 
.code
 
;вспомогательная процедура для сортировки кучей
;алгоритм процедуры восстановления баланса пирамиды при добавлении нового A[K]
;  A[]   - исходный массив
;  K     - индекс добавляемого/просеиваемого элемента
;  N     - максимальное значение индекса массива
;процедура просеивания следующего элемента:
;До процедуры: A[K+1]...A[N]  - пирамида
;После:  A[K]...A[N]  - пирамида
siftDown        proc      lpArray:DWORD, K:DWORD, N:DWORD       ;procedure siftDown(var A: TArray; K, N: integer);
                                                                ;  var
                                                                ;    temp: integer;
                                                                ;    childPos: integer;
        pushad                                                  ;  begin
        mov     ebx,    [N]
        mov     esi,    [lpArray]
        mov     ecx,    [K]
                                                                ;    {Это чтобы при K=0 И N=0 не делалось лишней перестановки}
        test    ebx,    ebx                                     ;    if 0 = N then
        jz      _exit                                           ;      exit;
        mov     edi,    [esi+ecx*4]                             ;    temp := A[K];
        _while:                                                 ;    while K * 2 + 1 <= N do
                                                                ;    begin
                mov     edx,    ecx                             ;      childPos := 2 * K + 1;  // Индекс левого ребенка
                add     edx,    edx
                inc     edx
                cmp     edx,    ebx
                ja      _break
                                                                ;      // выбираем в childPos индекс большего ребенка
                mov     eax,    edx                             ;      if (childPos + 1 <= N) and (A[childPos] < A[childPos + 1]) then
                inc     eax
                cmp     eax,    ebx
                ja      @f
                mov     eax,    [esi+eax*4]
                cmp     eax,    [esi+edx*4]
                jle     @f
                inc     edx                                     ;        Inc(childPos);
        @@:                                                     ;
                                                                ;      // Если A[K] больше максимального ребенка - завершение
                cmp     edi,    [esi+edx*4]                     ;      if (temp >= A[childPos]) then
                jge     _break                                  ;        break;
                                                                ;
                                                                ;      // иначе - меняем его с наибольшим ребенком
                mov     eax,    [esi+edx*4]                     ;      A[K] := A[childPos];
                mov     [esi+ecx*4],    eax
                                                                ;
                mov     ecx,    edx                             ;      K := childPos;
        jmp     _while                                          ;    end;
_break:
        mov     [esi+ecx*4],    edi                             ;    A[K] := temp;
_exit:                                                          ;  end;
        popad
        ret
siftDown        endp
 
;сортировка кучей (пирамидальная сортировка)
;на входе:
;  lpArray  - адрес массива
;  uiAmount - длина массива
HeapSort        proc    lpArray:DWORD, uiAmount:DWORD                   ;  procedure HeapSort(var A: TArray; N: integer);
                                                                        ;  var
                                                                        ;    i: integer;
                                                                        ;    temp: integer;
        pushad                                                          ;  begin
        mov     esi,    [lpArray]
        mov     ebx,    [uiAmount]
        ;Построение пирамиды                                            ;    { Построение пирамиды }
        mov     ecx,    ebx                                             ;    for i := (N div 2) - 1 downto 0 do
        shr     ecx,    1
        dec     ebx     ;т.к. в дальнейшем нужно только значение (N-1)
        jmp     _next
        _for:
                invoke  siftDown,       esi, ecx, ebx                   ;      siftDown(A, i, N - 1);
        _next:
                dec     ecx
        jns     _for
                                                                        ;    {Формирование конечной отсортированной
                                                                        ;     последовательности + "балансирование"
                                                                        ;     пирамиды }
        mov     ecx,    ebx                                             ;    i := N - 1;
        jmp     _test_while                                             ;    while i > 0 do
        _while:                                                         ;    begin
                ;меняем первый с последним                              ;      {меняем первый с последним}
                push    dword ptr [esi]                                 ;      temp := A[0];
                push    dword ptr [esi+4*ecx]                           ;      A[0] := A[i];
                pop     dword ptr [esi]                                 ;      A[i] := temp;
                pop     dword ptr [esi+4*ecx]
                ;Восстановление баланса для пирамиды A[0..i-1]          ;      {Восстановление баланса для пирамиды A[0..i-1]}
                dec     ecx                                             ;      Dec(i);
                invoke  siftDown,       esi, 0, ecx                     ;      siftDown(A, 0, i);
        _test_while:                                                    ;    end;
                test    ecx,    ecx
        jnz     _while
        popad                                                           ;  end;
        ret
HeapSort        endp
 
ShowArray       proc    lpArray:DWORD, uiAmount:DWORD
        pushad
 
        mov     ecx,    [uiAmount]
        mov     esi,    [lpArray]
        @@ForI:
                push    ecx
                lodsd
                invoke  wsprintf,       ADDR Buffer, ADDR aszInteger, eax
                mov     [BufLen],       eax
                invoke  WriteConsole,   hConsoleOutput, ADDR Buffer,\
                                        BufLen, ADDR BufLen, NULL
                pop     ecx
        loop    @@ForI
 
        popad
        ret
ShowArray       endp
 
main    proc
 
        ; получение описателей ввода и вывода консоли
        invoke  GetStdHandle,   STD_INPUT_HANDLE
        mov     hConsoleInput,  eax
 
        invoke  GetStdHandle,   STD_OUTPUT_HANDLE
        mov     hConsoleOutput, eax
 
        invoke  ClearScreen
 
        ;вывод исходных данных
        invoke  WriteConsole,   hConsoleOutput, ADDR aszMsgInstant,\
                                LENGTHOF aszMsgInstant - 1,\
                                ADDR BufLen, NULL
        invoke  ShowArray,      ADDR Array, [ASize]
 
        ;обработка массива - сортировка
        invoke  HeapSort,       ADDR Array, [ASize]
        ;вывод результата
        invoke  WriteConsole, hConsoleOutput, ADDR aszMsgResult,\
                LENGTHOF aszMsgResult - 1, ADDR BufLen, NULL
        invoke  ShowArray,      ADDR Array, [ASize]
 
        ;ожидание нажатия ENTER
        invoke  WriteConsole,   hConsoleOutput, ADDR aszPressEnter,\
                                LENGTHOF aszPressEnter - 1, ADDR BufLen, NULL
        invoke  ReadConsole,    hConsoleInput, ADDR Buffer,\
                                LENGTHOF Buffer, ADDR BufLen, NULL
 
        invoke  ExitProcess,    0
main    endp
 
end     main


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

Возможные пути улучшения данной реализации:
1. Т.к. и HeapSort и siftDown работают с одним массивом, то можно не передавать адрес массива отдельным параметром, условившись, что он будет неизменно находится в одном из регистров (например, в esi).
2. Т.к. при выполнении сортировки фактически требуется сохранение не более двух регистров (ecx и ebx), можно заменить в siftDown инструкции pushad/popad на инструкции для двух конкретных регистров. Или же, переработать программу для передачи параметров в siftDown через глобальные переменные - как это сделано у Mikl___ - или через локальные для HeapSort, т.к. для неё siftDown является, по сути, вложенной процедурой.

Вернуться к обсуждению:
Программа для сортировки любого массива
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.06.2019, 02:37
Готовые ответы и решения:

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

Не работает программа для сортировки массива строк
Здравствуйте. Из учебника Уэйта, Прата нашел программу для сортировки массива строк. После ввода 20...

Программа для сортировки одномерного массива нуждается в доработке
var A:array of integer; i, Res:integer; f:boolean; begin for i:=1 to 5 do begin...

Работа с массивами через указатели, адреса. Функция сортировки выбором любого массива
Надо было написать программу сортировки с использованием функций из учебника. соответственно...

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