r. Software Design: Recursive and Non-Recursive Modules In this question, we are
ID: 3803755 • Letter: R
Question
r. Software Design: Recursive and Non-Recursive Modules In this question, we are going to compare the recursive and non-recursive versions of the QuickSort algorithm (in non-descending order). (i) The following functions design a recursive and a non-recursive solution, respectively. (a Fill out the mumbered blanks in the functions and highlight your answer with the corresponding numbers. b What is the time complexity ofthe two solutions? public int partition (int I data, int left, int right) int temp data, lleft. inti left, j right while (i j) while (j i if (j i) data Olij data tj11 it while (j i it if (i j) data data lija data li return public static void QuickSortRecursion (int array int left, int right)Explanation / Answer
1. While (J>i && data[j]>data[lleft] if(j>i)
2. while(j>i && data[i]<data[right]
3. QuickSortRecursion(data, left, j - 1);
4. QuickSortRecursion(data, j + 1, right);
comparision
1. FUNCTION CALLS My implementation avoids function calls. Calling (and returning from) a function is time-consuming, and not because the content of the function takes time to execute — just getting into the function, and back out of it, uses processor time.
2. STACK My implementation does not use the stack to store data. Recursive functions look neat and simple in part because they don’t have to have big arrays like my beg[] and end[]. But all they’re really doing is using the stack as their own private array. This is much slower than using a real array, and could cause stack overflow on some systems, crashing the app that called the quicksort. My implementation simply returns NO if this kind of failure occurs.
3. SWAP VARIABLE In any one pivot round, the Wikipedia version can pass items through a swap variable many times. My code passes only one item (the pivot) through a swap variable, and only once per round.
4. MULTIPLE MOVES In any one pivot round, the Wikipedia version can move the same item more than once in the list. My code never moves an item to a new position in the list more than once per round.
5. UNNECESSARY MOVES
and i have one more pdf who give you a better comparision b/w recurive n non recusive funtion
if you want then please tell me
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.