I have started studying Design and Analysis of Algorithms. While going through, I encountered many sorting algorithms. As best way to learn anything is to implement it, I thought of developing a Dynamic link library of different algorithms. I have used assembly language for coding. Till now I have written 3 sorting algorithms
1. Insertion sort
2. Merge Sort
3 Bubble Sort.
I will give the code and also try to explain about the algorithms. I will also try to list the difficulties I faced while developing it.
1. Insertion Sort.
InsertionSort proc pArray:DWORD, nSize:DWORD
LOCAL temp:DWORD
mov ecx, 1
mov esi, pArray
assume esi:ptr DWORD
START_WHILE:
mov eax, nSize
;dec eax
cmp ecx, eax
jge END_WHILE
mov eax, ecx
imul eax, 4
mov ebx, [esi + eax]
mov temp, ebx
mov edx, ecx
dec edx
mov eax, temp
mov ebx, edx
imul ebx, 4
;.while edx >= 0 && [esi+ebx] > eax
START_WHILE2:
cmp edx, 0
jl END_WHILE2
cmp [esi+ebx], eax
jle END_WHILE2
;mov eax, temp
;mov temp2, edx
;.if [esi+edx*4] >eax
mov ebx, edx
imul ebx,4
mov eax, [esi+ebx]
mov ebx, eax
mov eax, edx
inc eax
imul eax,4
mov [esi+eax], ebx
dec edx
mov ebx, edx
imul ebx,4
mov eax, temp
;.endif
jmp START_WHILE2
END_WHILE2:
mov eax, edx
inc eax
imul eax, 4
mov ebx, temp
mov [esi+eax], ebx
inc ecx
jmp START_WHILE
END_WHILE:
Ret
InsertionSort EndP
I could have written it in a much better form. Like i have calculated the index of the array first and placed it in the eax register. Instead of that i could have directly written as [esi + ecx*4].
Insertion sort takes Big Oh(n^2) and it sorts in place. For small number of elements its a good algorithm.
Insertion sort is like arranging a pile of cards. Take a single card from the table and find the correct position for that card among the cards you are holding in your hand. Suppose there are 6 elements in the order
4 7 2 9 1 3
Then I will first chose 4 as it is the first element, I will hold it, then I will pick 7 from set. As compared to 4 it should come after 4. So my ordered array is 4 7. Left random array is 2 9 1 3
Now I will pick 2, 2 should come before 4. So my ordered array would be now 2 4 7 and remaining are 9 1 3. Similarly if we continue we get the ordered array 1 2 3 4 7 9
But important thing is that usually the unordered part and ordered part will be present in the single array. So the order of element movement will be like this
4 7 2 9 1 3
4 7 2 9 1 3
2 4 7 9 1 3
2 4 7 9 1 3
1 2 4 7 9 3
1 2 3 4 7 9
While writing the code, some of the mistakes I did was addressing. As it is a DWORD, it is 4 times the bytes. And addressing is always byte addressing. So we need to multiply the index each time by 4 and then I can add it to base address to get the actual address. I forgot to multiply it by 4. After 1st round of running the program I got to know my stupid mistake. Apart from that some logical mistakes in the algorithm I had done while coding. Another mistake is I forgot that in the mul instruction both eax and edx will be used. so if you have anything in edx after mul instruction it will be lost.
Well remaining algorithms details I will update it as soon as possible.
1. Insertion sort
2. Merge Sort
3 Bubble Sort.
I will give the code and also try to explain about the algorithms. I will also try to list the difficulties I faced while developing it.
1. Insertion Sort.
InsertionSort proc pArray:DWORD, nSize:DWORD
LOCAL temp:DWORD
mov ecx, 1
mov esi, pArray
assume esi:ptr DWORD
START_WHILE:
mov eax, nSize
;dec eax
cmp ecx, eax
jge END_WHILE
mov eax, ecx
imul eax, 4
mov ebx, [esi + eax]
mov temp, ebx
mov edx, ecx
dec edx
mov eax, temp
mov ebx, edx
imul ebx, 4
;.while edx >= 0 && [esi+ebx] > eax
START_WHILE2:
cmp edx, 0
jl END_WHILE2
cmp [esi+ebx], eax
jle END_WHILE2
;mov eax, temp
;mov temp2, edx
;.if [esi+edx*4] >eax
mov ebx, edx
imul ebx,4
mov eax, [esi+ebx]
mov ebx, eax
mov eax, edx
inc eax
imul eax,4
mov [esi+eax], ebx
dec edx
mov ebx, edx
imul ebx,4
mov eax, temp
;.endif
jmp START_WHILE2
END_WHILE2:
mov eax, edx
inc eax
imul eax, 4
mov ebx, temp
mov [esi+eax], ebx
inc ecx
jmp START_WHILE
END_WHILE:
Ret
InsertionSort EndP
I could have written it in a much better form. Like i have calculated the index of the array first and placed it in the eax register. Instead of that i could have directly written as [esi + ecx*4].
Insertion sort takes Big Oh(n^2) and it sorts in place. For small number of elements its a good algorithm.
Insertion sort is like arranging a pile of cards. Take a single card from the table and find the correct position for that card among the cards you are holding in your hand. Suppose there are 6 elements in the order
4 7 2 9 1 3
Then I will first chose 4 as it is the first element, I will hold it, then I will pick 7 from set. As compared to 4 it should come after 4. So my ordered array is 4 7. Left random array is 2 9 1 3
Now I will pick 2, 2 should come before 4. So my ordered array would be now 2 4 7 and remaining are 9 1 3. Similarly if we continue we get the ordered array 1 2 3 4 7 9
But important thing is that usually the unordered part and ordered part will be present in the single array. So the order of element movement will be like this
4 7 2 9 1 3
4 7 2 9 1 3
2 4 7 9 1 3
2 4 7 9 1 3
1 2 4 7 9 3
1 2 3 4 7 9
While writing the code, some of the mistakes I did was addressing. As it is a DWORD, it is 4 times the bytes. And addressing is always byte addressing. So we need to multiply the index each time by 4 and then I can add it to base address to get the actual address. I forgot to multiply it by 4. After 1st round of running the program I got to know my stupid mistake. Apart from that some logical mistakes in the algorithm I had done while coding. Another mistake is I forgot that in the mul instruction both eax and edx will be used. so if you have anything in edx after mul instruction it will be lost.
Well remaining algorithms details I will update it as soon as possible.
