
Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort


Task

Sort an array of positive integers using the Bead Sort Algorithm.

A   bead sort   is also known as a   gravity sort.



Algorithm has   O(S),   where   S   is the sum of the integers in the input set:   Each bead is moved individually.

This is the case when bead sort is implemented without a mechanism to assist in finding empty spaces below the beads, such as in software implementations.




 
 
/* ARM assembly Raspberry PI  */
/*  program beadSort.s */
/* En français tri par gravité ou tri par bille (ne pas confondre 
   avec tri par bulle (bubble sort) */
 
 /* REMARK 1 : this program use routines in a include file 
   see task Include a file language arm assembly 
   for the routine affichageMess conversion10 
   see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes                       */
/************************************/
.include "../constantes.inc"
 
/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessSortOk:       .asciz "Table sorted.\n"
szMessSortNok:      .asciz "Table not sorted !!!!!.\n"
sMessResult:        .asciz "Value  : @ \n"
szCarriageReturn:   .asciz "\n"
 
.align 4
TableNumber:      .int   1,3,6,2,5,9,10,8,4,7
#TableNumber:     .int   10,9,8,7,6,5,4,3,2,1
                  .equ NBELEMENTS, (. - TableNumber) / 4
           @.equ NBELEMENTS, 4 @ for others tests
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:            .skip 24
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                         @ entry of program 
 
1:
    ldr r0,iAdrTableNumber    @ address number table
    mov r1,#NBELEMENTS        @ number of élements 
    bl beadSort
    ldr r0,iAdrTableNumber    @ address number table
    mov r1,#NBELEMENTS        @ number of élements 
    bl displayTable
 
    ldr r0,iAdrTableNumber    @ address number table
    mov r1,#NBELEMENTS        @ number of élements 
    bl isSorted               @ control sort
    cmp r0,#1                 @ sorted ?
    beq 2f
    ldr r0,iAdrszMessSortNok  @ no !! error sort
    bl affichageMess
    b 100f
2:                            @ yes
    ldr r0,iAdrszMessSortOk
    bl affichageMess
100:                          @ standard end of the program 
    mov r0, #0                @ return code
    mov r7, #EXIT             @ request to exit program
    svc #0                    @ perform the system call
 
iAdrszCarriageReturn:     .int szCarriageReturn
iAdrsMessResult:          .int sMessResult
iAdrTableNumber:          .int TableNumber
iAdrszMessSortOk:         .int szMessSortOk
iAdrszMessSortNok:        .int szMessSortNok
/******************************************************************/
/*     control sorted table                                   */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the number of elements  > 0  */
/* r0 return 0  if not sorted   1  if sorted */
isSorted:
    push {r2-r4,lr}              @ save registers
    mov r2,#0
    ldr r4,[r0,r2,lsl #2]        @ load A[0]
1:
    add r2,#1
    cmp r2,r1                    @ end ?
    movge r0,#1                  @ yes -> ok -> return
    bge 100f
    ldr r3,[r0,r2, lsl #2]       @ load A[i]
    cmp r3,r4                    @ compare A[i],A[i-1]
    movlt r0,#0                  @ smaller ?
    blt 100f                     @ yes -> error -> return
    mov r4,r3                    @ no -> A[i-1] = A[i]
    b 1b                         @ and loop 
100:
    pop {r2-r4,lr}
    bx lr                        @ return 
/******************************************************************/
/*         bead sort                                              */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the number of element */
beadSort:
    push {r1-r12,lr}          @ save registers
    mov r12,r1                @ save elements number
    @search max
    ldr r10,[r0]              @ load value A[0] in max
    mov r4,#1
1:                            @ loop search max
    cmp r4,r12                @ end ?
    bge 21f                   @ yes
    ldr r2,[r0,r4,lsl #2]     @ load value A[i]
    cmp r2,r10                @ compare with max
    movgt r10,r2              @ if greather
    add r4,r4,#1
    b 1b                      @ loop
21:
    mul r5,r10,r12            @ max * elements number
    lsl r5,r5,#2              @ 4 bytes for each number
    sub sp,sp,r5              @ allocate on the stack
    mov fp,sp                 @ frame pointer = stack address
                              @ marks beads
    mov r3,r0                 @ save table address
    mov r0,#0                 @ start index x
2:
    mov r1,#0                 @ index y
    ldr r7,[r3,r0,lsl #2]     @ load A[x]
    mul r6,r0,r10             @ compute bead x
3:
    add r9,r6,r1              @ compute bead y
    mov r4,#1                 @ value to store
    str r4,[fp,r9,lsl #2]     @ store to stack area
    add r1,r1,#1
    cmp r1,r7
    blt 3b
31:                           @ init to zéro the bead end 
    cmp r1,r10                @ max ?
    bge 32f
    add r9,r6,r1              @ compute bead y
    mov r4,#0
    str r4,[fp,r9,lsl #2]
    add r1,r1,#1
    b 31b
32:
    add r0,r0,#1              @ increment x
    cmp r0,r12                @ end ?
    blt 2b
                              @ count beads
    mov r1,#0                 @ y
4:
    mov r0,#0                 @ start index x
    mov r8,#0                 @ sum
5:
    mul r6,r0,r10             @ compute bead x
    add r9,r6,r1              @ compute bead y
    ldr r4,[fp,r9,lsl #2]
    add r8,r8,r4
    mov r4,#0
    str r4,[fp,r9,lsl #2]
    add r0,r0,#1
    cmp r0,r12
    blt 5b
    sub r0,r12,r8
6:
    mul r6,r0,r10             @ compute bead x
    add r9,r6,r1              @ compute bead y
    mov r4,#1
    str r4,[fp,r9,lsl #2]
    add r0,r0,#1
    cmp r0,r12
    blt 6b
 
    add r1,r1,#1
    cmp r1,r10
    blt 4b
 
    @ suite
    mov r0,#0                 @ start index
7:
    mov r1,#0
    mul r6,r0,r10             @ compute bead x
8:
    add r9,r6,r1              @ compute bead y
    ldr r4,[fp,r9,lsl #2]
    add r1,r1,#1              @ add to r1 before str (index start at zéro)
    cmp r4,#1
    streq r1,[r3,r0, lsl #2]  @ store A[i]
    cmp r1,r10                @ compare max
    blt 8b
    add r0,r0,#1
    cmp r0,r12                @ end ?
    blt 7b
 
    mov r0,#0
    add sp,sp,r5              @ stack alignement
100:
    pop {r1-r12,lr}
    bx lr                     @ return 
/******************************************************************/
/*      Display table elements                                */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains elements number  */
displayTable:
    push {r0-r4,lr}              @ save registers
    mov r2,r0                    @ table address
    mov r4,r1                    @ elements number
    mov r3,#0
1:                               @ loop display table
    ldr r0,[r2,r3,lsl #2]
    ldr r1,iAdrsZoneConv
    bl conversion10              @ décimal conversion 
    ldr r0,iAdrsMessResult
    ldr r1,iAdrsZoneConv         @ insert conversion
    bl strInsertAtCharInc
    bl affichageMess             @ display message
    add r3,r3,#1
    cmp r3,r4                    @ end ?
    blt 1b                       @ no -> loop
    ldr r0,iAdrszCarriageReturn
    bl affichageMess
100:
    pop {r0-r4,lr}
    bx lr
iAdrsZoneConv:           .int sZoneConv
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
.include "../affichage.inc"
 
 