
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 (or list) of strings in order of descending length, and in ascending lexicographic order for strings of equal length.

Use a sorting facility provided by the language/library, combined with your own callback comparison function.


Note:   Lexicographic order is case-insensitive.




 
/* ARM assembly AARCH64 Raspberry PI 3B */
/*  program customSort64.s   */
 
 /* use merge sort iteratif and pointer table  */
 /* but use a extra table on stack for the merge */
/*******************************************/
/* Constantes file                         */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
 
/*******************************************/
/* Structures                               */
/********************************************/
/* city structure      */
    .struct  0
city_name:                             //
    .struct  city_name + 8             // string pointer
city_country:                          // 
    .struct  city_country + 8          // string pointer
city_end:
 
/*********************************/
/* Initialized data              */
/*********************************/
.data
sMessResult:           .asciz "Name : @  country : @ \n"
szMessSortName:        .asciz "Ascending sort table for name of city :\n"
szMessSortCitiesDesc:  .asciz "Descending sort table for name of city : \n"
szCarriageReturn:      .asciz "\n"
 
// cities name
szLondon:           .asciz "London"
szNewyork:          .asciz "New York"
szBirmin:           .asciz "Birmingham"
szParis:            .asciz "Paris"
// country name
szUK:               .asciz "UK"
szUS:               .asciz "US"
szFR:               .asciz "FR"
.align 4
TableCities:               
e1:              .quad szLondon         // address name string
                 .quad szUK             // address country string
e2:              .quad szParis
                 .quad szFR
e3:              .quad szNewyork
                 .quad szUS
e4:              .quad szBirmin
                 .quad szUK
e5:              .quad szParis
                 .quad szUS
e6:              .quad szBirmin
                 .quad szUS
/* pointers table */
ptrTableCities:   .quad e1
                  .quad e2
                  .quad e3
                  .quad e4
                  .quad e5
                  .quad e6
.equ NBELEMENTS,  (. - ptrTableCities) / 8
 
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:              .skip 24
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                             // entry of program 
    ldr x0,qAdrptrTableCities     // address pointers table
    bl displayTable
 
    ldr x0,qAdrszMessSortName
    bl affichageMess
 
    ldr x0,qAdrptrTableCities     // address pointers table
    mov x1,0                      // first element
    mov x2,NBELEMENTS             // number of élements 
    adr x3,comparAreaAlphaCrois   // address custom comparator ascending
    bl mergeSortIter
    ldr x0,qAdrptrTableCities     // address table
    bl displayTable
 
    ldr x0,qAdrszMessSortCitiesDesc
    bl affichageMess
 
    ldr x0,qAdrptrTableCities     // address table
    mov x1,0                      // first element
    mov x2,NBELEMENTS             // number of élements 
    adr x3,comparAreaAlphaDecrois // address custom comparator descending 
    bl mergeSortIter
    ldr x0,qAdrptrTableCities     // address table
    bl displayTable
 
100:                              // standard end of the program 
    mov x0,0                      // return code
    mov x8,EXIT                   // request to exit program
    svc 0                         // perform the system call
 
qAdrsZoneConv:            .quad sZoneConv
qAdrszCarriageReturn:     .quad szCarriageReturn
qAdrsMessResult:          .quad sMessResult
qAdrTableCities:          .quad TableCities
qAdrszMessSortName:        .quad szMessSortName
qAdrszMessSortCitiesDesc:  .quad szMessSortCitiesDesc
qAdrptrTableCities:        .quad ptrTableCities
 
/******************************************************************/
/*      merge sort  iteratif                                      */ 
/* use an extra table on stack                                    */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the index of first element */
/* x2 contains the number of element */
/* x3 contains the address of custom comparator */
mergeSortIter:
    stp fp,lr,[sp,-16]!     // save  registers
    stp x1,x2,[sp,-16]!     // save  registers
    stp x4,x5,[sp,-16]!     // save  registers
    stp x6,x7,[sp,-16]!     // save  registers
    stp x8,x9,[sp,-16]!     // save  registers
    stp x10,x11,[sp,-16]!   // save  registers
    stp x12,x13,[sp,-16]!   // save  registers
    stp x14,x15,[sp,-16]!   // save  registers
    mov x15,x0              // save address
    mov x4,x1               // save N0 first element
    sub x5,x2,1             // save N° last  element
    tst x2,1                // number of  element odd ?
    add x13,x2,1            // yes then add 1
    csel x13,x13,x2,ne      // to have a multiple to 16 bytes
    lsl x13,x13,3           // for reserve the extra table to the stack
    sub sp,sp,x13
    mov fp,sp               // frame register = address extra table on stack
 
    mov x10,1               // subset size 
1:
    mov x6,x4               // first element
2:
    lsl x8,x10,1            // compute end subset
    add x8,x8,x6
    sub x8,x8,1
    add x7,x6,x8            // compute median
    lsr x7,x7,1
    cmp x8,x5               // maxi ?
    ble 21f                 // no
    mov x8,x5               // yes -> end subset = maxi
    cmp x6,0                // subset final ?
    beq 21f                 // no
    cmp x7,x8               // compare median end subset
    blt 21f
    mov x7,x8               // maxi -> median 
 
21:
    add x9,x7,1
    mov x0,x15
3:                          // copy first subset on extra table
    sub x1,x9,1
    ldr x2,[x0,x1,lsl 3]
    str x2,[fp,x1,lsl 3]
    sub x9,x9,1
    cmp x9,x6
    bgt 3b
    mov x9,x7
    cmp x7,x8
    beq 41f
4:                          // and copy inverse second subset on extra table
    add x1,x9,1
    add x12,x7,x8
    sub x12,x12,x9
    ldr x2,[x0,x1,lsl 3]
    str x2,[fp,x12,lsl 3]
    add x9,x9,1
    cmp x9,x8
    blt 4b
41:
    mov x11,x6  //k
    mov x1,x6  // i
    mov x2,x8  // j
5:                          // and now merge the two subset on final table
    mov x0,fp
    blr x3
    cmp x0,0
    bgt 7f
    blt 6f
    // si egalité et si i < pivot 
    cmp x1,x7
    ble 6f
    b 7f
6:
    ldr x12,[fp,x1, lsl 3]
    str x12,[x15,x11, lsl 3]
    add x1,x1,1
    b 8f
7:
    ldr x12,[fp,x2, lsl 3]
    str x12,[x15,x11, lsl 3]
    sub x2,x2,1
8:
    add x11,x11,1
    cmp x11,x8
    ble 5b
 
9:
    mov x0,x15
    lsl x2,x10,1
    add x6,x6,x2         // compute new subset 
    cmp x6,x5            // end ?
    ble 2b
    lsl x10,x10,1        // size of subset * 2
    cmp x10,x5           // end ?
    ble 1b
 
100:
    add sp,sp,x13           // stack alignement
    ldp x14,x15,[sp],16     // restaur  2 registers
    ldp x12,x13,[sp],16     // restaur  2 registers
    ldp x10,x11,[sp],16     // restaur  2 registers
    ldp x8,x9,[sp],16       // restaur  2 registers
    ldp x6,x7,[sp],16       // restaur  2 registers
    ldp x4,x5,[sp],16       // restaur  2 registers
    ldp x1,x2,[sp],16       // restaur  2 registers
    ldp fp,lr,[sp],16       // restaur  2 registers
    ret                     // return to address lr x30
 
/******************************************************************/
/*      ascending comparison sort area                                */ 
/******************************************************************/
/* x0 contains the address of table */
/* x1 indice area sort 1 */
/* x2 indice area sort 2 */
comparAreaAlphaCrois:
    stp x1,lr,[sp,-16]!          // save  registers
    stp x2,x3,[sp,-16]!          // save  registers
    stp x4,x5,[sp,-16]!          // save  registers
    stp x6,x7,[sp,-16]!          // save  registers
    stp x8,x9,[sp,-16]!          // save  registers
 
    ldr x1,[x0,x1,lsl 3]         // load pointer element 1
    ldr x6,[x1,city_name]        // load area sort element 1
    ldr x2,[x0,x2,lsl 3]         // load pointer element 2
    ldr x7,[x2,city_name]        // load area sort element 2
 
    mov x8,#0                    // compar alpha string
1:
    ldrb w9,[x6,x8]              // byte string 1
    ldrb w5,[x7,x8]              // byte string 2
    cmp w9,w5
    bgt 11f                      // croissant
    blt 10f
 
    cmp w9,#0                    //  end string 1
    beq 12f                      // end comparaison
    add x8,x8,#1                 // else add 1 in counter
    b 1b                         // and loop
 
10:                              // lower
    mov x0,-1
    b 100f
11:                              // highter
    mov x0,1
    b 100f
12:                              // equal
    mov x0,0
100:
    ldp x8,x9,[sp],16            // restaur  2 registers
    ldp x6,x7,[sp],16            // restaur  2 registers
    ldp x4,x5,[sp],16            // restaur  2 registers
    ldp x2,x3,[sp],16            // restaur  2 registers
    ldp x1,lr,[sp],16            // restaur  2 registers
    ret                          // return to address lr x30
/******************************************************************/
/*      descending comparison sort area                                */ 
/******************************************************************/
/* x0 contains the address of table */
/* x1 indice area sort 1 */
/* x2 indice area sort 2 */
comparAreaAlphaDecrois:
    stp x1,lr,[sp,-16]!          // save  registers
    stp x2,x3,[sp,-16]!          // save  registers
    stp x4,x5,[sp,-16]!          // save  registers
    stp x6,x7,[sp,-16]!          // save  registers
    stp x8,x9,[sp,-16]!          // save  registers
 
    ldr x1,[x0,x1,lsl 3]         // load pointer element 1
    ldr x6,[x1,city_name]        // load area sort element 1
    ldr x2,[x0,x2,lsl 3]         // load pointer element 2
    ldr x7,[x2,city_name]        // load area sort element 2
 
    mov x8,#0                    // compar alpha string
1:
    ldrb w9,[x6,x8]              // byte string 1
    ldrb w5,[x7,x8]              // byte string 2
    cmp w9,w5
    blt 11f                      // descending
    bgt 10f
 
    cmp w9,#0                    //  end string 1
    beq 12f                      // end comparaison
    add x8,x8,#1                 // else add 1 in counter
    b 1b                         // and loop
 
10:                              // lower
    mov x0,-1
    b 100f
11:                              // highter
    mov x0,1
    b 100f
12:                              // equal
    mov x0,0
100:
    ldp x8,x9,[sp],16            // restaur  2 registers
    ldp x6,x7,[sp],16            // restaur  2 registers
    ldp x4,x5,[sp],16            // restaur  2 registers
    ldp x2,x3,[sp],16            // restaur  2 registers
    ldp x1,lr,[sp],16            // restaur  2 registers
    ret                          // return to address lr x30
/******************************************************************/
/*      Display table elements                                */ 
/******************************************************************/
/* x0 contains the address of table */
displayTable:
    stp x1,lr,[sp,-16]!          // save  registers
    stp x2,x3,[sp,-16]!          // save  registers
    stp x4,x5,[sp,-16]!          // save  registers
    stp x6,x7,[sp,-16]!          // save  registers
    mov x2,x0                    // table address
    mov x3,0
1:                               // loop display table
    lsl x4,x3,#3                 // offset element
    ldr x6,[x2,x4]               // load pointer
    ldr x1,[x6,city_name]
    ldr x0,qAdrsMessResult
    bl strInsertAtCharInc        // put name in message
    ldr x1,[x6,city_country]     // and put country in the message
    bl strInsertAtCharInc        // insert result at @ character
    bl affichageMess             // display message
    add x3,x3,1
    cmp x3,#NBELEMENTS
    blt 1b
    ldr x0,qAdrszCarriageReturn
    bl affichageMess
100:
    ldp x6,x7,[sp],16            // restaur  2 registers
    ldp x4,x5,[sp],16            // restaur  2 registers
    ldp x2,x3,[sp],16            // restaur  2 registers
    ldp x1,lr,[sp],16            // restaur  2 registers
    ret                          // return to address lr x30
/********************************************************/
/*        File Include fonctions                        */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
 