
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 integers (of any convenient size) into ascending order using Circlesort.

In short, compare the first element to the last element, then the second element to the second last element, etc.

Then split the array in two and recurse until there is only one single element in the array, like this:

Before:
6 7 8 9 2 5 3 4 1
After:
1 4 3 5 2 9 8 7 6

Repeat this procedure until quiescence (i.e. until there are no swaps).

Show both the initial, unsorted list and the final sorted list. (Intermediate steps during sorting are optional.)

Optimizations (like doing 0.5 log2(n) iterations and then continue with an Insertion sort) are optional. 


Pseudo code:

 function circlesort (index lo, index hi, swaps)
 {
   if lo == hi return (swaps)
   high := hi
   low := lo
   mid := int((hi-lo)/2)
   while lo < hi {
     if  (value at lo) > (value at hi) {
        swap.values (lo,hi)
        swaps++
     }
     lo++
     hi--
   }
   if lo == hi
     if (value at lo) > (value at hi+1) {
         swap.values (lo,hi+1)
         swaps++
     }
   swaps := circlesort(low,low+mid,swaps)
   swaps := circlesort(low+mid+1,high,swaps)
   return(swaps)
 }
 while circlesort (0, sizeof(array)-1, 0)



See also

 For more information on Circle sorting, see Sourceforge.


 
/* ARM assembly Raspberry PI  */
/*  program circleSort.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"
 
/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessSortOk:       .asciz "Table sorted.\n"
szMessSortNok:      .asciz "Table not sorted !!!!!.\n"
szMessSortBefore:   .asciz "Display table before sort.\n"
sMessResult:        .asciz "Value  : @ \n"
szCarriageReturn:   .asciz "\n"
 
.align 4
#TableNumber:      .int   1,3,6,2,5,9,10,8,4,7
#TableNumber:       .int   1,2,3,4,5,6,7,8,9,10
TableNumber:       .int   9,5,12,8,2,12,6
#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,iAdrszMessSortBefore
    bl affichageMess
    ldr r0,iAdrTableNumber          @ address number table
    bl displayTable
1:
    ldr r0,iAdrTableNumber          @ address number table
    mov r1,#0
    mov r2,#NBELEMENTS -1           @ number of élements 
    mov r3,#0
    bl circleSort
    cmp r0,#0
    bne 1b
    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
iAdrszMessSortBefore:     .int szMessSortBefore
/******************************************************************/
/*     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 
/******************************************************************/
/*         circle sort                                              */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the first index */
/* r2 contains the last index */
/* r3 contains number of swaps */
circleSort:
    push {r1-r10,lr}           @ save registers
    cmp r1,r2
    beq 99f
    mov r7,r0                  @ save address
    mov r8,r1                  @ low
    mov r9,r2                  @ high
    sub r4,r2,r1
    lsr r4,#1
    mov r10,r4                 @ mid
1:                             @ start loop
    cmp r1,r2
    bge 3f
    ldr r5,[r0,r1,lsl #2]
    ldr r6,[r0,r2,lsl #2]
    cmp r5,r6
    ble 2f
    str r6,[r0,r1,lsl #2]      @ swap values
    str r5,[r0,r2,lsl #2] 
    add r3,r3,#1
2:
    add r1,r1,#1               @ increment lo
    sub r2,r2,#1               @ decrement hi
    b 1b                       @ and loop
3:
    cmp r1,r2                  @ compare lo hi
    bne 4f                     @ not egal
    ldr r5,[r0,r1,lsl #2]
    add r2,r2,#1
    ldr r6,[r0,r2,lsl #2]
    cmp r5,r6 
    ble 4f
    str r6,[r0,r1,lsl #2]      @  swap
    str r5,[r0,r2,lsl #2] 
    add r3,r3,#1
4:
    mov r1,r8                  @ low
    mov r2,r10                 @ mid
    add r2,r2,r1
    bl circleSort
    mov r3,r0                 @ swaps
    mov r0,r7                 @ table address
    mov r1,r8                 @ low
    mov r2,r10                @ mid
    add r1,r2,r1
    add r1,r1,#1
    mov r2,r9                 @ high
    bl circleSort
    mov r3,r0                 @ swaps
99:
    mov r0,r3                 @ return number swaps
100:
    pop {r1-r10,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 conversion10                   @ 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
100:
    pop {r0-r3,lr}
    bx lr
iAdrsZoneConv:           .int sZoneConv
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
.include "../affichage.inc"
 
 