Sorting algorithms/Patience sort: Difference between revisions
Content deleted Content added
m added Category:Sorting |
add task to arm assembly raspberry pi |
||
Line 9:
:* [[Longest increasing subsequence]]
<br><br>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<lang ARM Assembly>
/* ARM assembly Raspberry PI */
/* program patienceSort.s */
/* 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"
.include "../../ficmacros.s"
/*******************************************/
/* Structures */
/********************************************/
/* structure Doublylinkedlist*/
.struct 0
dllist_head: @ head node
.struct dllist_head + 4
dllist_tail: @ tail node
.struct dllist_tail + 4
dllist_fin:
/* structure Node Doublylinked List*/
.struct 0
NDlist_next: @ next element
.struct NDlist_next + 4
NDlist_prev: @ previous element
.struct NDlist_prev + 4
NDlist_value: @ element value or key
.struct NDlist_value + 4
NDlist_fin:
/*********************************/
/* 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,11,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
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: @ entry of program
ldr r0,iAdrTableNumber @ address number table
mov r1,#0 @ first element
mov r2,#NBELEMENTS @ number of élements
bl patienceSort
ldr r0,iAdrTableNumber @ address number table
bl displayTable
ldr r0,iAdrTableNumber @ address number table
mov r1,#NBELEMENTS @ number of élements
bl isSorted @ control sort
cmp r0,#1 @ sorted ?
beq 1f
ldr r0,iAdrszMessSortNok @ no !! error sort
bl affichageMess
b 100f
1: @ 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]
1:
add r2,#1
cmp r2,r1
movge r0,#1
bge 100f
ldr r3,[r0,r2, lsl #2]
cmp r3,r4
movlt r0,#0
blt 100f
mov r4,r3
b 1b
100:
pop {r2-r4,lr}
bx lr @ return
/******************************************************************/
/* patience sort */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains first start index
/* r2 contains the number of elements */
patienceSort:
push {r1-r9,lr} @ save registers
lsl r9,r2,#1 @ compute total size of piles (2 list pointer by pile )
lsl r10,r9,#2 @ 4 bytes by number
sub sp,sp,r10 @ reserve place to stack
mov fp,sp @ frame pointer = stack
mov r3,#0 @ index
mov r4,#0
1:
str r4,[fp,r3,lsl #2] @ init piles area
add r3,r3,#1 @ increment index
cmp r3,r9
blt 1b
mov r3,#0 @ index value
mov r4,#0 @ counter first pile
mov r8,r0 @ save table address
2:
ldr r1,[r8,r3,lsl #2] @ load value
add r0,fp,r4,lsl #3 @ pile address
bl isEmpty
cmp r0,#0 @ pile empty ?
bne 3f
add r0,fp,r4,lsl #3 @ pile address
bl insertHead @ insert value r1
b 5f
3:
add r0,fp,r4,lsl #3 @ pile address
ldr r5,[r0,#dllist_head]
ldr r5,[r5,#NDlist_value] @ load first list value
cmp r1,r5 @ compare value and last value on the pile
blt 4f
add r0,fp,r4,lsl #3 @ pile address
bl insertHead @ insert value r1
b 5f
4: @ value is smaller créate a new pile
add r4,r4,#1
add r0,fp,r4,lsl #3 @ pile address
bl insertHead @ insert value r1
5:
add r3,r3,#1 @ increment index value
cmp r3,r2 @ end
blt 2b @ and loop
/* step 2 */
mov r6,#0 @ index value table
6:
mov r3,#0 @ index pile
mov r5,# 1<<30 @ min
7: @ search minimum
add r0,fp,r3,lsl #3
bl isEmpty
cmp r0,#0
beq 8f
add r0,fp,r3,lsl #3
bl searchMinList
cmp r0,r5 @ compare min global
movlt r5,r0 @ smaller -> store new min
movlt r7,r1 @ and pointer to min
addlt r9,fp,r3,lsl #3 @ and head list
8:
add r3,r3,#1 @ next pile
cmp r3,r4 @ end ?
ble 7b
str r5,[r8,r6,lsl #2] @ store min to table value
mov r0,r9 @ and suppress the value in the pile
mov r1,r7
bl suppressNode
add r6,r6,#1 @ increment index value
cmp r6,r2 @ end ?
blt 6b
add sp,sp,r10 @ stack alignement
100:
pop {r1-r9,lr}
bx lr @ return
/******************************************************************/
/* Display table elements */
/******************************************************************/
/* r0 contains the address of table */
displayTable:
push {r0-r3,lr} @ save registers
mov r2,r0 @ table address
mov r3,#0
1: @ loop display table
ldr r0,[r2,r3,lsl #2]
ldr r1,iAdrsZoneConv @
bl conversion10S @ décimal conversion
ldr r0,iAdrsMessResult
ldr r1,iAdrsZoneConv @ insert conversion
bl strInsertAtCharInc
bl affichageMess @ display message
add r3,#1
cmp r3,#NBELEMENTS - 1
ble 1b
ldr r0,iAdrszCarriageReturn
bl affichageMess
mov r0,r2
100:
pop {r0-r3,lr}
bx lr
iAdrsZoneConv: .int sZoneConv
/******************************************************************/
/* list is empty ? */
/******************************************************************/
/* r0 contains the address of the list structure */
/* r0 return 0 if empty else return 1 */
isEmpty:
ldr r0,[r0,#dllist_head]
cmp r0,#0
movne r0,#1
bx lr @ return
/******************************************************************/
/* insert value at list head */
/******************************************************************/
/* r0 contains the address of the list structure */
/* r1 contains value */
insertHead:
push {r1-r4,lr} @ save registers
mov r4,r0 @ save address
mov r0,r1 @ value
bl createNode
cmp r0,#-1 @ allocation error ?
beq 100f
ldr r2,[r4,#dllist_head] @ load address first node
str r2,[r0,#NDlist_next] @ store in next pointer on new node
mov r1,#0
str r1,[r0,#NDlist_prev] @ store zero in previous pointer on new node
str r0,[r4,#dllist_head] @ store address new node in address head list
cmp r2,#0 @ address first node is null ?
strne r0,[r2,#NDlist_prev] @ no store adresse new node in previous pointer
streq r0,[r4,#dllist_tail] @ else store new node in tail address
100:
pop {r1-r4,lr} @ restaur registers
bx lr @ return
/******************************************************************/
/* search value minimum */
/******************************************************************/
/* r0 contains the address of the list structure */
/* r0 return min */
/* r1 return address of node */
searchMinList:
push {r2,r3,lr} @ save registers
ldr r0,[r0,#dllist_head] @ load first node
mov r3,#1<<30
mov r1,#0
1:
cmp r0,#0 @ null -> end
moveq r0,r3
beq 100f
ldr r2,[r0,#NDlist_value] @ load node value
cmp r2,r3 @ min ?
movlt r3,r2 @ value -> min
movlt r1,r0 @ store pointer
ldr r0,[r0,#NDlist_next] @ load addresse next node
b 1b @ and loop
100:
pop {r2,r3,lr} @ restaur registers
bx lr @ return
/******************************************************************/
/* suppress node */
/******************************************************************/
/* r0 contains the address of the list structure */
/* r1 contains the address to node to suppress */
/* r0 return address of node or -1 if not found */
suppressNode:
push {r2,r3,lr} @ save registers
ldr r2,[r1,#NDlist_next] @ load addresse next node
ldr r3,[r1,#NDlist_prev] @ load addresse prev node
cmp r3,#0
strne r2,[r3,#NDlist_next]
streq r3,[r0,#NDlist_next]
cmp r2,#0
strne r3,[r2,#NDlist_prev]
streq r2,[r0,#NDlist_prev]
100:
pop {r2,r3,lr} @ restaur registers
bx lr @ return
/******************************************************************/
/* Create new node */
/******************************************************************/
/* r0 contains the value */
/* r0 return node address or -1 if allocation error*/
createNode:
push {r1-r7,lr} @ save registers
mov r4,r0 @ save value
@ allocation place on the heap
mov r0,#0 @ allocation place heap
mov r7,#0x2D @ call system 'brk'
svc #0
mov r5,r0 @ save address heap for output string
add r0,#NDlist_fin @ reservation place one element
mov r7,#0x2D @ call system 'brk'
svc #0
cmp r0,#-1 @ allocation error
beq 100f
mov r0,r5
str r4,[r0,#NDlist_value] @ store value
mov r2,#0
str r2,[r0,#NDlist_next] @ store zero to pointer next
str r2,[r0,#NDlist_prev] @ store zero to pointer previous
100:
pop {r1-r7,lr} @ restaur registers
bx lr @ return
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
.include "../affichage.inc"
</lang>
=={{header|C}}==
Takes integers as input, prints out usage on incorrect invocation
|