/*
 * C Program sorts the numbers in ascending order using quicksort (quick_sort.c)
 */
/*
#include <stdio.h>
#define MAXSIZE 1000

void array_print(char *s, int heap[], int no) {
    int i;
    printf("%s ", s);
    for (i = 0; i < no; i++)
        printf("%d ", heap[i]);
    printf("\n");
}

void swap (int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void quick_sort(int list[], int low, int high) {
    int pivot, low_index, high_index;
    if (low < high) {
        pivot      = list[low];
        low_index  = low;
        high_index = high;

        while (low_index < high_index) {
            while (list[low_index] <= pivot && low_index <= high) {
                low_index++;                               // from low,  find an element >  pivot
            }
            while (list[high_index] > pivot && high_index >= low) {
                high_index--;                              // from high, find an element <= pivot
            }
            if (low_index < high_index) {                  // two elements is in wrong order 
                swap(&list[low_index], &list[high_index]); // swap two elements
            }
        }                                                  // all elements are checked
        swap(&list[low], &list[high_index]);               // put pivot in final position

        quick_sort(list, low, high_index-1);               // sort low  part
        quick_sort(list, high_index+1, high);              // sort high part
    }
}

int main() {
    int array[MAXSIZE];
    int i, num;

    printf("enter the number of elements n = ");
    scanf("%d", &num);
    printf("enter %d elements one by one\n", num);
    for (i = 0; i < num; i++) {
        scanf("%d", &array[i]);
    }
    array_print("\nthe original array is", array, num);
    quick_sort(array, 0, num - 1);
    array_print("the  sorted  array is", array, num);
    return 0;
}
 */
.text
array_print:
    addi  sp,sp,-48
    sw    ra,44(sp)
    sw    s0,40(sp)
    addi  s0,sp,48
    sw    a0,-36(s0)
    sw    a1,-40(s0)
    sw    a2,-44(s0)
    lw    a1,-36(s0)
    lui   a5,%hi(.LC0)
    addi  a0,a5,%lo(.LC0)
    call  printf
    sw    zero,-20(s0)
    j    .L2
.L3:
    lw    a5,-20(s0)
    slli  a5,a5,2
    lw    a4,-40(s0)
    add   a5,a4,a5
    lw    a5,0(a5)
    mv    a1,a5
    lui   a5,%hi(.LC1)
    addi  a0,a5,%lo(.LC1)
    call  printf
    lw    a5,-20(s0)
    addi  a5,a5,1
    sw    a5,-20(s0)
.L2:
    lw    a4,-20(s0)
    lw    a5,-44(s0)
    blt   a4,a5,.L3
    li    a0,10
    call  putchar
    nop
    lw    ra,44(sp)
    lw    s0,40(sp)
    addi  sp,sp,48
    jr    ra
swap:
    addi  sp,sp,-48
    sw    s0,44(sp)
    addi  s0,sp,48
    sw    a0,-36(s0)
    sw    a1,-40(s0)
    lw    a5,-36(s0)
    lw    a5,0(a5)
    sw    a5,-20(s0)
    lw    a5,-40(s0)
    lw    a4,0(a5)
    lw    a5,-36(s0)
    sw    a4,0(a5)
    lw    a5,-40(s0)
    lw    a4,-20(s0)
    sw    a4,0(a5)
    nop
    lw    s0,44(sp)
    addi  sp,sp,48
    jr    ra
quick_sort:
    addi  sp,sp,-48
    sw    ra,44(sp)
    sw    s0,40(sp)
    addi  s0,sp,48
    sw    a0,-36(s0)
    sw    a1,-40(s0)
    sw    a2,-44(s0)
    lw    a4,-40(s0)
    lw    a5,-44(s0)
    bge   a4,a5,.L15
    lw    a5,-40(s0)
    slli  a5,a5,2
    lw    a4,-36(s0)
    add   a5,a4,a5
    lw    a5,0(a5)
    sw    a5,-28(s0)
    lw    a5,-40(s0)
    sw    a5,-20(s0)
    lw    a5,-44(s0)
    sw    a5,-24(s0)
    j    .L7
.L10:
    lw    a5,-20(s0)
    addi  a5,a5,1
    sw    a5,-20(s0)
.L8:
    lw    a5,-20(s0)
    slli  a5,a5,2
    lw    a4,-36(s0)
    add   a5,a4,a5
    lw    a5,0(a5)
    lw    a4,-28(s0)
    blt   a4,a5,.L11
    lw    a4,-20(s0)
    lw    a5,-44(s0)
    ble   a4,a5,.L10
    j    .L11
.L13:
    lw    a5,-24(s0)
    addi  a5,a5,-1
    sw    a5,-24(s0)
.L11:
    lw    a5,-24(s0)
    slli  a5,a5,2
    lw    a4,-36(s0)
    add   a5,a4,a5
    lw    a5,0(a5)
    lw    a4,-28(s0)
    bge   a4,a5,.L12
    lw    a4,-24(s0)
    lw    a5,-40(s0)
    bge   a4,a5,.L13
.L12:
    lw    a4,-20(s0)
    lw    a5,-24(s0)
    bge   a4,a5,.L7
    lw    a5,-20(s0)
    slli  a5,a5,2
    lw    a4,-36(s0)
    add   a3,a4,a5
    lw    a5,-24(s0)
    slli  a5,a5,2
    lw    a4,-36(s0)
    add   a5,a4,a5
    mv    a1,a5
    mv    a0,a3
    call  swap
.L7:
    lw    a4,-20(s0)
    lw    a5,-24(s0)
    blt   a4,a5,.L8
    lw    a5,-40(s0)
    slli  a5,a5,2
    lw    a4,-36(s0)
    add   a3,a4,a5
    lw    a5,-24(s0)
    slli  a5,a5,2
    lw    a4,-36(s0)
    add   a5,a4,a5
    mv    a1,a5
    mv    a0,a3
    call  swap
    lw    a5,-24(s0)
    addi  a5,a5,-1
    mv    a2,a5
    lw    a1,-40(s0)
    lw    a0,-36(s0)
    call  quick_sort
    lw    a5,-24(s0)
    addi  a5,a5,1
    lw    a2,-44(s0)
    mv    a1,a5
    lw    a0,-36(s0)
    call  quick_sort
.L15:
    nop
    lw    ra,44(sp)
    lw    s0,40(sp)
    addi  sp,sp,48
    jr    ra
main:
    addi  sp,sp,-2032
    sw    ra,2028(sp)
    sw    s0,2024(sp)
    addi  s0,sp,2032
    addi  sp,sp,-2000
    lui   a5,%hi(.LC2)
    addi  a0,a5,%lo(.LC2)
    call  printf
    li    a5,-4096
    addi  a5,a5,88
    addi  a4,s0,-16
    add   a5,a4,a5
    mv    a1,a5
    lui   a5,%hi(.LC3)
    addi  a0,a5,%lo(.LC3)
    call  scanf
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a5,88(a5)
    mv    a1,a5
    lui   a5,%hi(.LC4)
    addi  a0,a5,%lo(.LC4)
    call  printf
    sw    zero,-20(s0)
    j    .L17
.L18:
    li    a5,-4096
    addi  a5,a5,92
    addi  a4,s0,-16
    add   a4,a4,a5
    lw    a5,-20(s0)
    slli  a5,a5,2
    add   a5,a4,a5
    mv    a1,a5
    lui   a5,%hi(.LC3)
    addi  a0,a5,%lo(.LC3)
    call  scanf
    lw    a5,-20(s0)
    addi  a5,a5,1
    sw    a5,-20(s0)
.L17:
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a5,88(a5)
    lw    a4,-20(s0)
    blt   a4,a5,.L18
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a4,88(a5)
    li    a5,-4096
    addi  a5,a5,92
    addi  a3,s0,-16
    add   a5,a3,a5
    mv    a2,a4
    mv    a1,a5
    lui   a5,%hi(.LC5)
    addi  a0,a5,%lo(.LC5)
    call  array_print
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a5,88(a5)
    addi  a4,a5,-1
    li    a5,-4096
    addi  a5,a5,92
    addi  a3,s0,-16
    add   a5,a3,a5
    mv    a2,a4
    li    a1,0
    mv    a0,a5
    call  quick_sort
    li    a5,-4096
    addi  a4,s0,-16
    add   a5,a4,a5
    lw    a4,88(a5)
    li    a5,-4096
    addi  a5,a5,92
    addi  a3,s0,-16
    add   a5,a3,a5
    mv    a2,a4
    mv    a1,a5
    lui   a5,%hi(.LC6)
    addi  a0,a5,%lo(.LC6)
    call  array_print
    li    a5,0
    mv    a0,a5
    addi  sp,sp,2000
    lw    ra,2028(sp)
    lw    s0,2024(sp)
    addi  sp,sp,2032
    jr    ra
.data
.LC0: .string "%s "
.LC1: .string "%d "
.LC2: .string "enter the number of elements n = "
.LC3: .string "%d"
.LC4: .string "enter %d elements one by one\n"
.LC5: .string "\nthe original array is"
.LC6: .string "the  sorted  array is"
.end