8086-ASSEMBLY-LANGUAGE-PROGRAMS/Source Code/Sorting/selection_sort.asm at main · Amey-Thakur/8086-ASSEMBLY-LANGUAGE-PROGRAMS · GitHub

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
; =============================================================================
; TITLE: Selection Sort
; DESCRIPTION: Implementation of Selection Sort algorithm for an 8-bit
;              byte array.
; AUTHOR: Amey Thakur (https://github.com/Amey-Thakur)
; REPOSITORY: https://github.com/Amey-Thakur/8086-ASSEMBLY-LANGUAGE-PROGRAMS
; LICENSE: MIT License
; =============================================================================

.MODEL SMALL
.STACK 100H

; -----------------------------------------------------------------------------
; DATA SEGMENT
; -----------------------------------------------------------------------------
.DATA
    ARR DB 64, 25, 12, 22, 11            ; Input Data
    LEN EQU 5
    MSG DB 'Selection Sort execution finished.$'

; -----------------------------------------------------------------------------
; CODE SEGMENT
; -----------------------------------------------------------------------------
.CODE
MAIN PROC
    ; Segment registers
    MOV AX, @DATA
    MOV DS, AX

    ; Selection Sort Procedure:
    ; Repeatedly find the minimum element in the unsorted part
    ; and swap it with the first unsorted element.

    MOV CX, LEN - 1                     ; Outer loop counter (passes)
    XOR SI, SI                          ; SI = current boundary (i)

    ; -------------------------------------------------------------------------
    ; OUTER BATCH LOOP
    ; -------------------------------------------------------------------------
OUTER_PASS:
    PUSH CX

    MOV DI, SI                          ; min_idx = i
    MOV BX, SI
    INC BX                              ; j = i + 1

    ; Calculate inner loop limit: (Length - 1 - i)
    MOV AX, LEN
    SUB AX, SI
    DEC AX
    MOV CX, AX
    JZ CHECK_SWAP                       ; If no neighbors left, skip search

    ; -------------------------------------------------------------------------
    ; INNER MINIMUM FINDER
    ; -------------------------------------------------------------------------
SEARCH_MIN:
    MOV AL, ARR[BX]
    CMP AL, ARR[DI]                     ; If current < current_min
    JAE NOT_NEW_MIN
    MOV DI, BX                          ; Update min_idx

NOT_NEW_MIN:
    INC BX                              ; Next element
    LOOP SEARCH_MIN

CHECK_SWAP:
    ; Swap ARR[i] with ARR[min_idx]
    CMP DI, SI
    JE NO_SWAP                          ; Skip if current is already the min

    MOV AL, ARR[SI]
    MOV DL, ARR[DI]
    MOV ARR[SI], DL
    MOV ARR[DI], AL

NO_SWAP:
    INC SI                              ; Move boundary to right
    POP CX
    LOOP OUTER_PASS                     ; Repeat for remaining elements

    ; Final display
    LEA DX, MSG
    MOV AH, 09H
    INT 21H

    ; Exit code
    MOV AH, 4CH
    INT 21H
MAIN ENDP
END MAIN

; =============================================================================
; TECHNICAL NOTES
; =============================================================================
; 1. SELECTION SORT:
;    - Selection sort never makes more than O(N) swaps, which is beneficial
;      if the write operation is expensive.
;    - Total comparisons: O(N^2).
;    - Simple to implement but not adaptive (same work regardless of initial order).
; = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =