Форум программистов, компьютерный форум, киберфорум
Assembler для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
Assembler Вывод на экран длины введенной с клавиатуры строки https://www.cyberforum.ru/ asm-beginners/ thread389769.html
Граждане! Выручайте! Нужно разработать программу перевода ввода и вывода чисел в различных системах счисления, а также работы с числами в ассемблерных программах. Вывести на экран длину введенной с клавиатуры строки, систему счисления результата выбирает пользователь (двоичная, восьмеричная, десятичная, шестнадцатеричная). Программу перевода в 16-ричную систему я собрал. А вот как в ней сделать...
Assembler Деление двух целых пятизначных чисел(целая и дробная части)
Составить и отладить программу на ассемблере для нахождения результата деления двух целых пятизначных чисел, представленных в десятичном формате. Числа вводятся с клавиатуры. Результат вывести на дисплей в виде Z = xxx.yyy xxx- целая часть ууу - дробная
Assembler Разбить число на цифры(тетрады) Как на Ассемблере для процессора 80х86 разбить число на тетрады и каждую тетраду занести в отдельный регистр. Число 3EB7. https://www.cyberforum.ru/ asm-beginners/ thread389572.html Assembler Максимальный элемент массива а(10) ... https://www.cyberforum.ru/ asm-beginners/ thread389491.html
написать программу на assembler под Dos которая находит максимальный элемент массива а(10) меняет местами его с третьим по величине нечетным элементом с четным номером
программа должна выводить содержимое текстового файла на экран Assembler
программа должна выводить содержимое текстового файла на экран
Assembler Запись строки в обратной последовательности Ребята! Помогите новичку. Нужно разработать программу, ввода строковых данных с клавиатуры. Произвести запись строки в обратной последовательности. Очень надеюсь на Вас! https://www.cyberforum.ru/ asm-beginners/ thread389474.html
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 db ? ;Число реально введенных символов. string db 80 dup(?) ;Здесь будет сама строка. .code https://www.cyberforum.ru/ asm-beginners/ thread389402.html Assembler Минимальный среди кратных 3 элементов массива а(15)поменять местами с первым элементом возрастающей последовательности м
минимальный среди кратных 3 элементов массива а(15)поменять местами с первым элементом возрастающей последовательности массива
Assembler Заменить в строке встречающийся символ "a" на символ "k" https://www.cyberforum.ru/ asm-beginners/ thread389163.html
Ввести строку символьных данных, задавая буфер равный 40 байт. Заменить в этой строке встречающийся символ "a" на символ "k". Выдать полученную строку символов в первую строку экрана, начиная с 12 позиции. Можно её решить как нибудь?) От неё зависит мой зачёт)
Assembler Assembler ввод/вывод,преобразование числовых данных вычислить величину C= \frac{(a+2*b)^2}{2*d}-\frac{d^2}{3a} a,b,d - вводится с клавиатуры.результат выводится на экран. и вычислить величину с использованием сдвигов D=\frac{(a*5+b)}{4}+c*11 https://www.cyberforum.ru/ asm-beginners/ thread389014.html
Assembler Инициализация элементов матрицы
записать в сегменте данных двумерный массив МАТR с элементами длинной в слово и размерностью 5*6 и инициализировать его элементами 2х-1, где х-индекс.Использовать команду Loop для организации цикла.
Assembler Вывод на экран монитора в режиме эмуляции DOS содержимого двух регистров https://www.cyberforum.ru/ asm-beginners/ thread388833.html
Привет! Кто-нибудь! Помогите пожалуйста, отзовитесь) Вывести на экран монитора в режиме эмуляции DOS содержимого двух регистров di, bh. Если при выводе значение регистра равно нулевому значению, то предусмотреть в коде программы (без ввода с клавиатуры) возможность записи в данный регистр произвольного значения. Задать в программе как минимум четыре переменные, две из которых будет...
Ушел с форума
Автор FAQ
 Аватар для Mikl___
16347 / 7664 / 1077
Регистрация: 11.11.2010
Сообщений: 13,720
25.11.2011, 05:03 0

Программа для сортировки любого массива - Assembler - Ответ 2210209

25.11.2011, 05:03. Показов 90669. Ответов 15
Метки (Все метки)

Ответ

Сортирую двойные слова
Пузырьковая
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
.data
R dd n-1;количество неотсортированных элементов минус один
array  dd 10,450,320,120,180,600,50,230,340,460,550,500,130
      dd 80,390,410,20,800,670,60,730,610,310,0,360,200
n = ($-array)/4
.code
    mov esi,offset array    ;позиционируемся на массив
a2:    mov ecx,R    
    xor ebx,ebx        ;флаг – были/не были перестановки в проходе
a3:    mov eax,[esi+ecx*4-4]    ;получаем значение очередного элемента    
    cmp [esi+ecx*4],eax    ;сравниваем со значением соседнего элемента
    jnb a4    ;если больше или равен - идем к следующему элементу
    setna bl    ;была перестановка - взводим флаг
    xchg eax,[esi+ecx*4]    ;меняем значение элементов местами
    mov [esi+ecx*4-4],eax
a4:    loop a3    ;двигаемся вверх до границы массива
    add esi,4    ;сдвигаем границу отсортированного массива
    dec ebx    ;проверяем были ли перестановки
    jnz exit    ;если перестановок не было - заканчиваем сортировку
    dec R        ;уменьшаем количество неотсортированных элементов
    jnz a2;если есть еще неотсортированные элементы - начинаем новый проход
exit:
При упорядочении массива из n элементов произойдет в лучшем случае, если массив отсортирован — n-1 сравнений. В худшем случае, если массив отсортирован в обратном порядке — при сортировке произойдет n*(n-1)/2 сравнений. (для n=26 элементов лучший случай — 25, средний — 289, худший — 325)
Шейкер
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
.data
H dd 0    ;верхняя граница неотсортированного массива
L dd n-1    ;нижняя граница неотсортированного массива
.code
    xor esi,esi        ;нижняя граница неотсортированного массива
    xor ebx,ebx        ;флаг - были/не были перестановки в проходе
    mov ecx,L;количество неотсортированных элементов снизу минус один
a4:    inc esi
      call Compare_and_Swapping    ;сравнение и обмен значений элементов
    loop a4                ;двигаемся вниз до границы массива
    dec ebx                ;проверяем были ли перестановки
    jnz exit        ;если перестановок не было - сортировка закончена 
    dec L        ;уменьшаем количество неотсортированных элементов снизу
    jz exit    ;достигли границы массива
    dec esi        ;esi=L
    mov ecx,esi
    sub ecx,H;количество неотсортированных элементов сверху минус один
    jecxz exit    ;если граница снизу равна границе сверху - выходим
a2:    call Compare_Swapping        ;сравнение и обмен значений элементов
    dec esi
    loop a2                ;двигаемся вверх до границы массива
    dec ebx                ;проверяем были ли перестановки
    jnz exit    ;если перестановок не было - заканчиваем сортировку
    inc H    ;уменьшаем количество неотсортированных элементов сверху
    inc esi        ;esi=H
    mov ecx,L    
    sub ecx,esi    ;если граница снизу больше, чем граница сверху – значит 
    ja a4;есть еще неотсортированные элементы - начинаем новый проход
exit:    . . .
Compare_Swapping proc;сравнение и обмен значений соседних элементов
    mov eax,array[esi*4]    ;получаем значение очередного элемента
    cmp array[esi*4-4],eax    ;сравниваем его с соседним элементом
    jna a3    ;если меньше или равен - идем к следующему элементу
    seta bl    ;если была перестановка - взводим флаг
    xchg eax,array[esi*4-4]        ;меняем значения элементов местами
    mov array[esi*4],eax
a3:    ret
Compare_Swapping endp
n=26 элементов лучший случай — 25, средний — 259 (лучше пузырьковой сортировки на 20%), худший — 325
Пирамидальная
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
.data
L dd n/2-1    ;левая граница неотсортированного массива
R dd n-1        ;правая граница неотсортированного массива
.code
;массив преобразуется в отображение пирамиды – вызвать процедуру
;down_heap n/2 раз для преобразования массива  в пирамиду
b0:     call down_heap
        dec L        ;while ( L > 0 ) L--;
        jnz short b0
;собственно пирамидальная сортировка
       dec L        ;L=0
       dec R        ;R=n-2
b1:     mov edx,R   ;отправляем значение максимального
       mov eax,array    ;элемента в конец массива
        xchg eax,array[edx*4+4] ; array[0] <--> array[R];
        mov array,eax
        call down_heap   ;восстанавливаем пирамиду - на ее 
;вершине появляется новое максимальное значение      
        dec R        ;уменьшаем индекс последнего элемента
        jnz short b1    ;while ( R > 0 ) R--;
b2:        ...
;-----------------------------------------------------
down_heap proc; процедура вставки элемента на свое место в пирамиду
        mov eax,L
        mov ebx,eax            ;i = L;
        shl eax,1            ;j = 2*L;
        mov esi,array[eax*2]    ;item = array[L]; 
        cmp eax,R     ;if( j<R && array[j] < array[j+1]) j++; 
        jnb short a0
        mov edx,array[eax*4]
        cmp edx,array[eax*4+4]    ;array[j] < array[j+1] ?
        jnb short a0
; условие j<R && array[j]<array[j+1] выполнилось
        inc eax              ;j++
a0:     cmp eax,R           ;while( j<=R && item < array[j])
        ja short a1
        mov edi,array[eax*4]
        cmp esi,edi        ;item < array[j] ?
        jnb short a1
; условие j<=R && item < array[j] выполнилось
       mov array[ebx*4],edi    ;array[i] = array[j];
        mov ebx,eax        ;i = j;                                    
        shl eax,1            ;j = 2*j;
        cmp eax,R
        jnb short a0;if( j<R && array[j] < array[j+1]) j++;
        mov edx,array[eax*4]
        cmp edx,array[eax*4+4]
        jnb short a0
; условие j<R && array[j] < array[j+1] выполнилось
        inc eax            ;j++
       jmp short a0
a1:       mov array[ebx*4],esi    ;array[i] = item;
        retn
down_heap endp
n=26 элементов средний случай— 109 (лучше пузырьковой сортировки почти в 3 раза)

Добавлено через 3 минуты
сортировка прямым включением
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
mov esi,4       ;i=1
a4:    push esi
a3:    mov eax,array[esi-4]
     cmp eax,array[esi]
    jb a2
    xchg eax,array[esi]
    sub esi,4    ;двигаемся к началу массива
    mov array[esi],eax
    jnz a3
a2:    pop esi
     add esi,4       ;двигаемся к концу массива
    cmp esi,n*4     ;просмотрели весь массив?
    jb a4
n=26 элементов лучший случай — 25, средний — 172 (лучше пузырьковой сортировки на 40%), худший — 325
Алгоритм можно улучшить пользуясь тем, что готовая последовательность уже упорядочена. Место вставки нового элемента можно найти значительно быстрее, если применить бинарный поиск, исследовав сперва средний элемент упорядоченной последовательности и продолжая деление пополам, пока не будет найдено место вставки. Для n=26 элементов лучший случай — 25, средний и худший — 106 (лучше пузырьковой сортировки почти в 3 раза)
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
mov ebx,1  ;ebx - граница неотсортированного массива
b1:    mov edi,ebx
    mov edx,edi;edi индекс первого элемента отсортированного массива
    xor esi,esi;esi индекс последнего элемента отсортированного массива
    mov eax,array[ebx*4]
    cmp eax,array[ebx*4-4]
    jnb b2
b6:    cmp esi,edi        ;проверка esi>edi на завершение поиска
    jg b5    ;проверены все элементы, вставляем новый элемент 
    shr edx,1 ;индекс центрального элемента равен (edi+esi)/2
    cmp array[edx*4],eax;сравниваем с искомым значением
    ja b3               ;array[edx*4]<eax
    jz b5               ;array[edx*4]=eax
     inc edx        ;учтем только что проверенное значение
    mov esi,edx    ;изменяем нижнюю границу поиска
    add edx,edi    ;создаем индекс центрального элемента
    jmp short b6    ;переходим к следующему элементу
b3:    dec edx        ;учтем только что проверенное значение
    mov edi,edx    ;изменяем верхнюю границу поиска
    add edx,esi    ;создаем индекс центрального элемента
    jmp b6        ;переходим к следующему элементу
b5:    mov ecx,ebx    ;сдвигаем отсортированные элементы, чтобы
    sub ecx,esi    ;освободить место для нового элемента
    shl esi,2; esi=esi*4
    push eax
b7:    mov eax,array[esi+ecx*4-4];сдвиг отсортированных элементов
    mov array[esi+ecx*4],eax
    loop b7
    pop eax
    mov array[esi],eax;вставляем новый элемент
b2:  inc ebx
    cmp ebx,n
    jb b1
сортировка прямым выбором
На массиве из n элементов время выполнения в худшем, среднем и лучшем случае n*(n-1)/2
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
mov edi,offset array    ;edi = указатель на массив
       mov ecx,N            ;ecx = количество элементов
a0:    lea ebx,[edi+ecx*4]    ;ebx = максимальный индекс в проходе+1
     mov eax,[edi]    ;eax=min=величина первого элемента в проходе
a1:     sub ebx,4        ;двигаемся по проходу вверх
     cmp eax,[ebx]
     jbe a2        ;min > array[ebx] ?
     xchg eax,[ebx]    ;swap(array[ebx],min)
a2:     cmp ebx,edi
     jnz a1        ;проход закончился?
     stosd ;mov [edi],eax edi=+4 на первой позиции минимальный элемент
     loop a0
сортировка Шелла
Среднее время работы алгоритма зависит от длин промежутков, на которых будут находится сортируемые элементы исходного списка на каждом шаге алгоритма
при выборе последовательности значений d1=n/2, d2=d1/2,...,1 в худшем случае алгоритм выполнит O(n2) — сравнений 140
Table dd 32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2,1
все значения (3^j−1)/2 < n, такая последовательность шагов приводит к алгоритму класса O(n^(3/2)) — сравнений 108
Table dd 797161,265720,88573,29524,9841,3280,1093,364,121,40,13,4,1
последовательности вида N=2*N+1 — сравнений 118
Table dd 32767,16383,8191,4095,2047,1023,511,255,127,63,31,15,7,3,1
последовательность Дж.Инсерпи и Р.Седгевика — сравнений 115:
Table dd 198768,86961,33936,13776,4592,1968,861,336,112,48,21,7,3,1
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
.data
Table dd 797161,265720,88573,29524,9841,3280,1093,364,121,40,13,4,1
.code
mov ecx,-14;в таблице приращений 13 элементов
entry: inc ecx
jz exit; если последний элемент в таблице - выход из программы
cmp [Table+ecx*4+13*4],n; ищем максимальное приращение (gap), 
jge entry;соответствующее размеру нашего массива
a6:    mov edx,[Table+ecx*4+13*4];получаем очередное приращение из таблицы
shl edx,2;выбрали интервал,у нас двойные слова,поэтому edx=edx*4
a2:    mov ebx,edx;i=gap
a3:    mov esi,ebx
sub esi,edx;j=i-gap
a4:    mov eax,array[esi];for(i=gap;i<dim;i++)/*проход массива*/
    cmp eax,array[esi+edx];сравнение пар,отстоящих 
jbe a5;на gap друг от друга
xchg eax,array[esi+edx];swap(a[j],a[j+gap])
mov array[esi],eax
sub esi,edx  ;j-=gap
jge a4 
a5:    add ebx,4    ;i++
cmp ebx,n*4  ;i < dim
jb a3        ;for(j=i-gap; j>=0 && a[j] > a[j+gap]
inc ecx
jnz a6
exit:
сортировка Хоара (быстрая сортировка)
Сортировка даёт в среднем O(n log n) сравнений
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
push    offset array+n*4-4;указатель на последний элемент
        push    offset array;указатель на первый элемент массива
        call    quick_sort      ; quicksort (data, data+n-1)
;-----------------------------------------------------
partition proc    Lb:dword,    Ub:dword
; функция partition возвращает адрес pivot 
        mov edx,Ub
       sub edx,eax             ;eax=Lb
       shr edx,3             ;(Ub-Lb)/2
; После завершения этого цикла все значения слева от элемента pivot 
; будут меньше значения элемента pivot, а все значения справа от 
; элемента pivot будут больше, чем значение элемента pivot
        mov edi,[eax+edx*4]   ;получаем указатель на pivot
;pivot = *(Lb+(Ub-Lb)/2)
        cmp eax,Ub         ;eax=Lb
        ja short b0             ;return Lb;
; Поиск значения, большего чем pivot, в нижней части массива
b1:     mov eax,Lb        
        cmp [eax],edi        ;edi=pivot
        jnl short b3        ;while (*Lb < pivot)
       add Lb,4            ;Lb++;   
       jmp short b1
; Поиск значения, меньшего чем pivot, в верхней части массива
b4:     sub Ub,4        
b3:     mov eax,Ub
        cmp [eax],edi        ;while (*Ub > pivot)
        jg short b4             ;Ub-- 
        mov ecx,Lb
       cmp ecx,eax             ;eax=Ub
        ja short b5           ;if(Lb <= Ub)
        sub Ub,4        ;swap( Lb++, Ub-- )
        add Lb,4        
        mov edx,[eax]        ;eax=Ub
        xchg edx,[ecx]        ;ecx=Lb
        mov [eax],edx        ;*Ub<-->*Lb;
b5:     mov eax,Lb
        cmp eax,Ub
        jbe short b1        ;while (*Lb < pivot)
b0:     pop ebp
        retn 8
partition endp
;------------------------------------------------------------
quick_sort proc Lb:dword, Ub:dword
         mov eax,Lb
         cmp eax,Ub ; if (Lb >= Ub)
         jnb short exit1    ;сортировать нечего
         push Ub
         push eax        ;eax=Lb
         call partition  
        mov edi,eax     ;eax=pivot_ptr
         sub eax,4        ;pivot_ptr-1
         push eax
         push Lb    
         call quick_sort ;отсортируем то, что слева от pivot
         push Ub
         push edi        ;edi=pivot_ptr
         call quick_sort ; и то, что справа от pivot
exit1:   pop ebp
         retn 8
quick_sort endp


Вернуться к обсуждению:
Программа для сортировки любого массива Assembler
29
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
25.11.2011, 05:03
Готовые ответы и решения:

Программа для сортировки массива на c51asm
Доброго дня всем! Возникла необходимость сделать следующее: разместить в резидентной памяти данных последовательность из N символов цифр в...

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

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

15
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
25.11.2011, 05:03
Помогаю со студенческими работами здесь

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

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

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

Не работает программа сортировки массива
Помогите найти ошибку program pas1; var i, j, n, k, t: integer; ax: array of integer; c: array of integer; sum: array of...

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

0
Новые блоги и статьи
Микросервис с нуля на Go с Kafka
stackoverflow 12.02.2025
Когда я впервые столкнулся с необходимостью разделить монолитное приложение на микросервисы, передо мной встал вопрос выбора правильных технологий и подходов. После долгих экспериментов с различными. . .
Микросервис с нуля на C# с RabbitMQ
stackoverflow 12.02.2025
Переход от монолитной архитектуры к микросервисной - это не просто модное веяние, а закономерный этап эволюции программных систем. В отличие от монолита, где все компоненты тесно связаны между собой. . .
Docker для начинающих
stackoverflow 12.02.2025
В современном мире разработки программного обеспечения все чаще возникает необходимость быстро и надежно разворачивать приложения в различных средах. Разработчики постоянно сталкиваются с проблемой. . .
Создание бота для Телеграм на C#
stackoverflow 12.02.2025
В современном мире корпоративных коммуникаций Telegram-боты становятся незаменимым средством автоматизации бизнес-процессов и взаимодействия с сотрудниками. Как создать такого бота, который сможет. . .
Операторы сравнения (== и ===) в JavaScript
hw_wired 12.02.2025
JavaScript предоставляет два основных оператора сравнения - оператор нестрогого равенства (==) и оператор строгого равенства (===). На первый взгляд они могут показаться очень похожими, но их. . .
Определение адреса, откуда репозиторий Git был клонирован
hw_wired 12.02.2025
Система контроля версий Git хранит всю информацию о репозитории в специальной директории . git, включая данные об удаленных источниках. Эта информация необходима для синхронизации изменений между. . .
Объединение нескольких коммитов Git в один
hw_wired 12.02.2025
Представьте, что вы работаете над новой функциональностью и создали десяток небольших коммитов: исправление опечатки, форматирование кода, добавление комментариев, реализация основной логики. Каждый. . .
Как добавить локальную ветку в удалённый репозиторий Git
hw_wired 12.02.2025
Локальная ветка в Git - это изолированная линия разработки, существующая только на вашем компьютере. Представьте себе дерево с множеством веток - каждая ветка может расти в своем направлении, не. . .
Статическое отражение в C++
stackoverflow 12.02.2025
Статическое отражение представляет собой мощный механизм, позволяющий программам анализировать и манипулировать своей собственной структурой во время компиляции. Эта возможность открывает. . .
C++ в 21 веке - Бьярне Страуструп
stackoverflow 12.02.2025
В современном мире разработки программного обеспечения C++ продолжает оставаться одним из ключевых языков программирования, несмотря на свой солидный возраст - более 45 лет с момента создания. За это. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru