
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


Sort an array of numbers (of any convenient size) into ascending order using   Patience sorting.



Related task

   Longest increasing subsequence


 
/* 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  */
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"
 