
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




 This page uses content from Wikipedia. The original article was at Counting sort. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)



Task

Implement the Counting sort.   This is a way of sorting integers when the minimum and maximum value are known.



Pseudocode

function countingSort(array, min, max):
    count: array of (max - min + 1) elements
    initialize count with 0
    for each number in array do
        count[number - min] := count[number - min] + 1
    done
    z := 0
    for i from min to max do
        while ( count[i - min] > 0 ) do
            array[z] := i
            z := z+1
            count[i - min] := count[i - min] - 1
        done
    done

The min and max can be computed apart, or be known a priori.


Note:   we know that, given an array of integers,   its maximum and minimum values can be always found;   but if we imagine the worst case for an array that can hold up to 32 bit integers,   we see that in order to hold the counts,   an array of up to 232 elements may be needed.   I.E.:   we need to hold a count value up to 232-1,   which is a little over 4.2 Gbytes.   So the counting sort is more practical when the range is (very) limited,   and minimum and maximum values are known   a priori.     (However, as a counterexample,   the use of   sparse arrays   minimizes the impact of the memory usage,   as well as removing the need of having to know the minimum and maximum values   a priori.)




 
/* ARM assembly Raspberry PI  */
/*  program countSort.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"
/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessSortOk:       .asciz "Table sorted.\n"
szMessSortNok:      .asciz "Table not sorted !!!!!.\n"
sMessResult:        .asciz "Value  : @ \n"
szCarriageReturn:   .asciz "\n"
 
.align 4
#Caution : number stritcly positive and not too big
#TableNumber:      .int   1,3,6,2,5,9,10,8,5,7       @ for test 2 sames values
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,#NBELEMENTS                             @ number of élements 
    bl searchMinMax                                @ r1=min r2=max
    mov r3,#NBELEMENTS                             @ number of élements 
    bl countSort
    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 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 éléments number  */
/* r0 return address r1 return min  r2 return max */
searchMinMax:
    push {r3-r5,lr}                @ save registers
    mov r3,r1                      @ save size
    mov r1,#1<<30                  @ min
    mov r2,#0                      @ max
    mov r4,#0                      @ index
1:
    ldr r5,[r0,r4, lsl #2]         @ load value
    cmp r5,r1                      @ if < min
    movlt r1,r5
    cmp r5,r2                      @ if > max
    movgt r2,r5
    add r4,r4,#1                   @ increment index
    cmp r4,r3                      @ end ?
    blt 1b                         @ no -> loop
100:
    pop {r3-r5,lr}
    bx lr                                              @ return 
/******************************************************************/
/*     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 
/******************************************************************/
/*         count Sort                                          */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the minimum    */
/* r2 contains the maximun */
/* r3 contains elements number */
/* caution : the count area is in the stack. if max is very large, risk of error */ 
countSort:
    push {r1-r9,lr}           @ save registers
    sub r3,r3,#1              @ compute end index
    sub r5,r2,r1              @ compute max - min
    add r5,r5,#1              @ + 1
    lsl r9,r5,#2              @ 4 bytes by number
    sub sp,sp,r9              @ reserve area on stack 
    mov fp,sp                 @ frame pointer = stack address
    mov r6,#0
    mov r4,#0
1:                            @ loop init stack area 
    str r6,[fp,r4, lsl #2]
    add r4,r4,#1
    cmp r4,r5
    blt 1b
    mov r4,#0                 @ indice
2:                            @ start loop 2
    ldr r5,[r0,r4,lsl #2]     @ load value A[j]
    sub r5,r5,r1              @ - min
    ldr r6,[fp,r5,lsl #2]     @ load count of value
    add r6,r6,#1              @ increment counter
    str r6,[fp,r5,lsl #2]     @ and store 
    add r4,#1                 @ increment indice
    cmp r4,r3                 @ end ?
    ble 2b                    @ no -> loop 2
 
    mov r7,#0                 @ z
    mov r4,r1                 @ indice = min
    //bl displayTable
3:                            @ loop 3
    sub r6,r4,r1              @ compute index - min
    ldr r5,[fp,r6,lsl #2]     @ load count
4:                            @ loop 4
    cmp r5,#0                 @ cont <> zero
    beq 5f
    str r4,[r0,r7,lsl #2]     @ store value
    add r7,r7,#1              @ increment z
    sub r5,r5,#1              @ decrement count
    b 4b
5:
    add r4,r4,#1              @ decrement indice
    cmp r4,r2                 @ max ?
    ble 3b                    @ no -> loop 3
 
    add sp,sp,r9              @ 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
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
.include "../affichage.inc"
 