All geek questions in one place

Why is this program exponentially longer with sizes over 50?

So, I am writing a quicksort method to build an ARM for a class. I have an understanding for the most part, besides complexity it makes no sense.

We compare it with another bubble sorting method that we have made, and it is better suited for examples with 1 argument and 10 arguments. However, I cannot even compare the test with 100 arguments, because it takes too long ... I cannot get it to do 75, but 50 is done in a few seconds.

This is what I have

qsort:  @ Takes three parameters:
    @   a:     Pointer to base of array a to be sorted (arrives in r0)
    @   n:  number of elements in the array (arrives in r1)

    stmfd   sp!, {r4, r6, lr}     @ Save r4 and r6 for caller
    mov     r6, r1                @ r6 <- right
    mov r2, #0                    @ r2 <- left
qsort_tailcall_entry:
    sub     r7, r6, r2            @ If right - left <= 1 (already sorted),
    cmp     r7, #1
    ldmlefd sp!, {r4, r6, pc}     @ Return, restoring r4 and r6
    ldr     r7, [r0, r2, asl #2]  @ r7 <- a[left], gets pivot element
    add     r1, r2, #1            @ l <- left + 1
    mov     r4, r6                @ r <- right
partition_loop:
    ldr     r3, [r0, r1, asl #2]  @ r3 <- a[l]
    cmp     r3, r7                @ If a[l] <= pivot_element,
    addle   r1, r1, #1            @ ... increment l, and
    ble     partition_test        @ ... continue to next iteration.
    sub     r4, r4, #1            @ Otherwise, decrement r,
    ldr     r8, [r0, r4, asl #2]  @ ... and swap a[l] and a[r].
    str     r8, [r0, r1, asl #2]
    str     r3, [r0, r4, asl #2]
partition_test:
    cmp     r1, r4                @ If l < r,
    blt     partition_loop        @ ... continue iterating.
partition_finish:
    sub     r1, r1, #1            @ Decrement l
    ldr     r3, [r0, r1, asl #2]  @ Swap a[l] and pivot
    str     r3, [r0, r2, asl #2]
    str     r7, [r0, r1, asl #2]
    bl      qsort                 @ Call self recursively on left part,
                                  @  with args a (r0), left (r2), r (r2),
                                  @  also preserves r4 and r6
    mov     r2, r4
    b       qsort_tailcall_entry  @ Tail-call self on right part,
                                  @  with args a (r0), l (r2), right (r6)

Can someone help me understand why in the world it takes IT a long time and grows exponentially? What can I do to fix this?

+4
source share
2 answers

, script , . .

/* qsort1.s */

@ ---- Added ----
.data

tstdat:
    .word 9, 9, 9, 9, 9

array:
    .word 3, 7, 8, 5, 2, 1, 9, 5, 4
len:
    .word ((len - array) /4)

.balign 4
format:
    .asciz " %2d  %2d  %2d  %2d  %2d  %2d  %2d  %2d  %2d  |  %2d  %2d  %2d\n"


.text

.global main

Print:
    push  {r0-v7, lr}
    mrs   v7,  cpsr
    push  {v7, v8}
    push  {r2, r6, r7}
    ldr   r7,  =array
    ldm   r7,  {r1-r9}
    push  {r4-r9}
    ldr   r0,  =format
    bl    printf
    add   sp,  #36
    pop   {v7, v8}
    msr   cpsr_f, v7
    pop   {r0-v7, pc}

main:

    ldr     r0,  =array
    ldr     r1,  =len
    ldr     r1,  [r1]

    push    {r3-r11, lr}
    bl      Print
    bl      qsort
    bl      Print
    pop     {r3-r11, pc}

@ ---------------------------

qsort:  @ Takes three parameters:
    @   a:     Pointer to base of array a to be sorted (arrives in r0)
    @   n:  number of elements in the array (arrives in r1)

    stmfd   sp!, {r4, r6, lr}     @ Save r4 and r6 for caller
    mov     r6, r1                @ r6 <- right
    mov     r2, #0                @ r2 <- left
qsort_tailcall_entry:
    sub     r7, r6, r2            @ If right - left <= 1 (already sorted),
@   bl      Print                @ <---- Added
    cmp     r7, #1
    ldmlefd sp!, {r4, r6, pc}     @ Return, restoring r4 and r6
    ldr     r7, [r0, r2, asl #2]  @ r7 <- a[left], gets pivot element
    add     r1, r2, #1            @ l <- left + 1
    mov     r4, r6                @ r <- right
partition_loop:
    ldr     r3, [r0, r1, asl #2]  @ r3 <- a[l]
    cmp     r3, r7                @ If a[l] <= pivot_element,
    addle   r1, r1, #1            @ ... increment l, and
    ble     partition_test        @ ... continue to next iteration.
    sub     r4, r4, #1            @ Otherwise, decrement r,
    ldr     r8, [r0, r4, asl #2]  @ ... and swap a[l] and a[r].
    str     r8, [r0, r1, asl #2]
    str     r3, [r0, r4, asl #2]
    bl      Print                @ <---- Added
partition_test:
    cmp     r1, r4                @ If l < r,
    blt     partition_loop        @ ... continue iterating.
partition_finish:
    sub     r1, r1, #1            @ Decrement l
    ldr     r3, [r0, r1, asl #2]  @ Swap a[l] and pivot
    str     r3, [r0, r2, asl #2]
    str     r7, [r0, r1, asl #2]
    bl      qsort                 @ Call self recursively on left part,
                                  @  with args a (r0), left (r2), r (r2),
                                  @  also preserves r4 and r6
    mov     r2, r4
    b       qsort_tailcall_entry  @ Tail-call self on right part,
                                  @  with args a (r0), l (r2), right (r6)

. - , - r2, r6 r7. https://en.wikipedia.org/wiki/Quicksort (https://upload.wikimedia.org/wikipedia/commons/a/af/Quicksort-diagram.svg).

pi@RPi:~/pgm $ mym qsort1
as -o qsort1.o qsort1.s
gcc -o qsort1 qsort1.o

./qsort1; echo $?
  3   7   8   5   2   1   9   5   4  |  2126935836  66296   0 (before pgm)
  3   4   8   5   2   1   9   5   7  |   0   9   3
  3   5   8   5   2   1   9   4   7  |   0   9   3
  3   9   8   5   2   1   5   4   7  |   0   9   3
  3   1   8   5   2   9   5   4   7  |   0   9   3
  3   1   2   5   8   9   5   4   7  |   0   9   3    
 ...
 (  array to be sorted             )    r2   r4  r7
0

quicksort , "Linux qsort" .

@ http://www.tutorialspoint.com/c_standard_library/c_function_qsort.htm
@
@ http://man7.org/linux/man-pages/man3/qsort.3.html
@
@ void qsort(void *base, size_t nmemb, size_t size,
@            int (*compar)(const void *, const void *));
@
@      qsort(r0 =array, r1 =numelements, r2 = 4 bytes,
@            r0=(r3 =cmpfunc){ r0=[r0] - r1=[r1] })

cmpfunc:
    ldr   r0,  [r0]
    ldr   r1,  [r1]
    sub   r0,  r0, r1
    mov   pc,  lr

qsort_setup:
    ldr   r0,  =array
    ldr   r1,  =numbytes
    lsr   r1,  #2
    mov   r2,  #4
    ldr   r3,  =cmpfunc

    bl    qsort

-, .

/* qsort14.s */

.data

@ See /usr/include/arm-linux-gnueabihf/asm/unistd.h
@ See /usr/include/arm-linux-gnueabihf/bits/fcntl-linux.h

    .equ create,     8
         .equ Mode, 0644       @ -rw-r--r--
    .equ open,       5
         .equ Rd,   00
         .equ Wr,   01
         .equ RdWr, 02
         .equ Apnd, 02000
    .equ read,       3
    .equ write,      4
    .equ close,      6
    .equ sync,       36
    .equ exit,       1
    .equ sfile,      187

    .equ numbytes,  (64 * 4)     @ Has to be multiples
@   .equ numbytes,  (128 * 4)    @  of 8 times 4.
@   .equ numbytes,  (512 * 4) 

.balign 4
array: .skip numbytes

.balign 4
dir_file:
    .asciz "/dev/urandom"

.balign 4
Open:
    .word dir_file, RdWr | Apnd, open

.balign 4
Read:
    .word array, numbytes, read

.balign 4
hex3ff:
    .word 0x3ff

.balign 4
format:
    .asciz " %4u  %4u  %4u  %4u  %4u  %4u  %4u  %4u\n"

.balign 4
fmt:
    .asciz "\n"

@ ---------------------------

.text

.global main

Prt_arr:
    push  {r0-r12, lr}
    mrs   r12,  cpsr
    push  {r11, r12}
    mov   r0,  #0xa
    bl    putchar
    ldr   r12, =numbytes
    lsr   r12, #5
    mov   r11, #0
endprt:
    ldr   r0,  =array
    add   r0,  r11
    ldm   r0,  {r1-r8}
    push  {r4-r12}
    ldr   r0,  =format
    bl    printf
    pop   {r4-r12}
    add   r11, #32
    subs  r12, #1
    bne   endprt
    pop   {r11, r12}
    msr   cpsr_f, r12
    pop   {r0-r12, lr}
    mov   pc, lr

@ ---- Program starts here ----
@ ---- Read random numbers ----

main:
    push  {r4-r12, lr}

    ldr   r3, =Open            @ load address
    ldm   r3, {r0, r1, r7}     @ load registers
    svc   #0                   @ OS opens urandom file
    mov   r4, r0               @ save fd in r4

    ldr   r3, =Read            @ load address
    ldm   r3, {r1, r2, r7}     @ load registers
    svc   #0                   @ OS reads urandom file

    mov   r0, r4               @ move fd in r0
    mov   r7, #close           @ num for close
    svc   #0                   @ OS closes urandom file

@ ---- Fix array so numbers are 999 or less ----

    ldr   r10, =array
    ldr   r1,  =numbytes
    sub   r1,  #4
    ldr   r2,  =hex3ff
    ldr   r2,  [r2]
fix:
    ldr   r0,  [r10, r1]
    and   r0,  r2
    cmp   r0,  #1000
    subge r0,  #1000
    lslge r0,  r0, #5
    str   r0,  [r10, r1]
    subs  r1,  #4
    bpl   fix

@ ---- Print unsorted array ----

    bl    Prt_arr
    b     qsort_setup

@ http://www.tutorialspoint.com/c_standard_library/c_function_qsort.htm
@
@ http://man7.org/linux/man-pages/man3/qsort.3.html
@
@ void qsort(void *base, size_t nmemb, size_t size,
@            int (*compar)(const void *, const void *));
@
@      qsort(r0 =array, r1 =numelements, r2 = 4 bytes,
@            r0=(r3 =cmpfunc){ r0=[r0] - r1=[r1] })

cmpfunc:
    ldr   r0,  [r0]
    ldr   r1,  [r1]
    sub   r0,  r0, r1
    mov   pc,  lr

qsort_setup:
    ldr   r0,  =array
    ldr   r1,  =numbytes
    lsr   r1,  #2
    mov   r2,  #4
    ldr   r3,  =cmpfunc

    bl    qsort

End:
    bl    Prt_arr
    mov   r0,  #0xa
    bl    putchar

    pop    {r4-r12, lr}
    bx     lr

.end
0

Source: https://habr.com/ru/post/1616298/

More articles:


All Articles