With gcc$,$ at&t syntax, we have a debian, $64-$bit server with the current problem to solve this in assembly language:

Program $6$: Quicksort $-$Assembler$$

Quicksort$$

In this program, you will implement the quicksort routine in assembler to sort $5000$ numbers again using AT&T syntax on the Debian $64$ bit system. You will generate$$ the numbers by calling the random number generator using $$call rand$.$ You will need to scale the numbers using the mod function$$ to provide numbers between $10,000-60,000.$ Remember that the mod function in assembler is really using the$$divq$$ instruction and using the remainder. Dividing by $60,000$ will produce remainders between $0-59,999.$ How do you get the numbers to be between $10,000-60,000?$

Requirements:$$

$-$ In assembler, store the numbers in a contiguous space in memory that will enable you to use an $$array$$ implementation of quicksort.$$

$-$ While testing$/$writing your program, initially implement Quicksort by generating between $200-400$ random numbers.$$

$-$ Write a function to print out the numbers $(10-15$ numbers on a line in neat columns$).-$ Only print the numbers if you are sorting the smaller set of $400$ numbers $($and not the $5000$ number set$).-$ Write a check routine and print out an $$Unsorted$$ or $$Sorted$$ message.$$

$-$ Implement the Quicksort. The quicksort is recursive so you must use the system stack. You will need$$ to push values such as High and Low and possibly the pivot on the stack. You will need to manage the$$ base pointer register $(\%$rbp$)$ and the stack pointer register $(\%$rsp$).$

$-$ Note that the partition function is not recursive so it is not required that you utilize the system stack for$$ that function, although you certainly may use it in a similar way as the quicksort function, managing$\%$rsp and $\%$rbp$.$

$-$ You should be able to run the program for $400$ numbers and for the full set of $5000$ numbers.$-$ Only print the numbers out if you are sorting the smaller set of $400$ numbers.$$

$-$

$-$ Hand in your final program. Be sure to run the program for $400$ numbers and for the full $5000$ set of$$ numbers.$$

$-$ Also call your check routine after sorting the numbers.$$

Summary Notes$$

$1.$ You should request the number of random numbers to generate from the user. That will be helpful in$$ testing since you should test your program using a small number of numbers $($e$.$g$.100-400).2.$ You should show that your program works for a small number $(400)$ of values by printing out the$$ UNSORTED AND the SORTED numbers and handing in the output when you hand in your program.$$ Be sure to print $10-20$ numbers on a line to minimize the number of lines of output that you generate. $3.$ DO NOT print the numbers when you run the program for more than $400$ numbers. Instead, you should$$ verify that you have sorted the array correctly by executing a 'check' routine to verify that the array is$$ sorted. Note that you should not need to re$-$assemble your program to handle $400$ and fewer numbers$$ and more than $400$ numbers. Your program logic should handle whether or not you print the numbers.

$4.$ Use either the C srand or rand functions.$$

$5.$ It is very important that you spend considerable time and effort performing quicksort by hand on a small$$ example so that you are able to identify the steps that you will follow as you implement the routines.$$ Use your quicksort program from CS$141$ and the C$++$ program as templates for writing the program.$$

$6.$ As a guideline, in implementing the sort you should partition the memory $"$in$-$place", i$.$e$.,$ you should not$$ use additional space than that needed to store your numbers while you are executing your sort. For$$ example, if you are sorting $100$ integers, you should only use $100$ words of memory $($plus possibly some$$ small amount of "utility" memory space$).$

$7.$ After you have read the numbers, your call to quicksort should partition the numbers using a partition$$ algorithm. The key to performing the quicksort recursively in assembler will be making the correct use$$ of the stack and registers. We will discuss the use of the stack in more depth in class.$$

Optional Extra Credit Opportunities: The following extra credit opportunities are available for this program.$$ You will receive extra credit points for each extra credit item that you choose to implement if you implement it correctly and successfully in the program.$$

$1.$ Utilize macros correctly and appropriately in your program for sets of instructions that are performed$$ numerous times. Because the purpose of macros is different than for functions, macros would not replace your calls to functions. For examples of macros, see the macro$\_$ex$.$s and macro$\_$library.s files.$$