Python - Recursive to non-recursive quick sort. What I have at the moment is a recursive quick sort, I need to make it non-recursive, any help is appreciated!
def quickSort(list):
quickSortHelper(list, 0, len(list) - 1)
def quickSortHelper(list, first, last):
if last > first:
pivotIndex =
partition(list, first, last)
quickSortHelper(list,
first, pivotIndex - 1)
quickSortHelper(list,
pivotIndex + 1, last)
# Partition list[first..last]
def partition(list, first, last):
pivot = list[first] # Choose the first element
as the pivot
low = first + 1 # Index for forward search
high = last # Index for backward search
while high > low:
# Search forward from
left
while low <= high and
list[low] <= pivot:
low += 1
# Search backward
from right
while low <= high and
list[high] > pivot:
high -= 1
# Swap two elements
in the list
if high > low:
list[high], list[low] = list[low], list[low]
while high > first and list[high] >=
pivot:
high -= 1
# Swap pivot with list[high]
if pivot > list[high]:
list[first] =
list[high]
list[high] = pivot
return high
else:
return first
# A test function
def main():
list = [2, 3, 2, 5, 6, 1, -2, 3, 14, 12]
quickSort(list)
for v in list:
print(str(v) + " ", end
= "")
main()
Python code is given below: (modified code segment is highlighted)
def quickSort(list): quickSortHelper(list, 0, len(list) - 1) def quickSortHelper(list, first, last): if last > first: pivotIndex = partition(list, first, last) quickSortHelper(list, first, pivotIndex - 1) quickSortHelper(list, pivotIndex + 1, last) # Partition list[first..last] def partition(list, first, last): pivot = list[first] # Choose the first element as the pivot low = first + 1 # Index for forward search high = last # Index for backward search while high > low: # Search forward from left while low <= high and list[low] <= pivot: low += 1 # Search backward from right while low <= high and list[high] > pivot: high -= 1 # Swap two elements in the list if high > low: temp = list[high] list[high] = list[low] list[low] = temp while high > first and list[high] > pivot: high -= 1 # Swap pivot with list[high] if pivot > list[high]: list[first] = list[high] list[high] = pivot return high else: return first def quickSortIterative(list): l = 0 # set the low and high h = len(list) - 1 size = h - l + 1 st = [0] * (size) # initializing the stack top = -1 # it represents the empty stack top = top + 1 st[top] = l # inserting low and high in stack top = top + 1 st[top] = h while top >= 0: # run while loop until the stack becomes empty h = st[top] # popping the low and high top = top - 1 l = st[top] top = top - 1 p = partition(list, l, h) # partition if p - 1 > l: # again push the range low to pivot-1 top = top + 1 st[top] = l top = top + 1 st[top] = p - 1 if p + 1 < h: # push the range pivot + 1 to high top = top + 1 st[top] = p + 1 top = top + 1 st[top] = h # A test function def main(): list = [2, 3, 2, 5, 6, 1, -2, 3, 14, 12] quickSortIterative(list) for v in list: print(str(v) + " ", end = "") main()
Sample Output:
-2 1 2 2 3 3 5 6 12 14
Screenshot of the code is given below:
If the answer helped please upvote, it means a lot and for any query please comment.
Python - Recursive to non-recursive quick sort. What I have at the moment is a recursive...
JAVA- Trace the recursive quick sort and partition methods in Lab6.java for this list of numbers: 47 71 15 35 66 61 44 26 68 56 18 19 36 84 69 55 1. Find the value of pivot 2. Show the result after partitionIt() is called first time 3. Show the value of partition 4. Show the content of the array ///////////////////////////// Lab6.java class ArrayIns { private long[] theArray; // ref to array theArray private int nElems; // number of...
C++. Difficulty with quickSort function. Code will not run quickSort function. The code I'm having trouble with is in bold. -------------------------------------------------------------------------------------------------driverProgram.cpp #include #include #include #include #include "quickSort.cpp" using namespace std; int main() { const int MIN_SIZE = 4; //Array size const int SIZE = 25; int theArray[SIZE] = {11, 22, 33, 44, 55, 66, 77, 88, 99, 12, 13, 14, 15, 16, 17, 18, 19, 18, 19, 20, 21, 22, 23, 24, 25}; cout << "List of 25 items: ";...
JAVA For the code in which I implemented most of the quick select algorithm. Quick select is a O(n) time algorithm to find the nth smallest value in an (unordered list). The following recursive algorithm finds thenth smallest element with an index bewtween left and right in list: Code: Integer QuickSelect(list, left, right, n) { if left = right // If we only have one index available return list[left] // return the element at that index endif pivotIndex ⇐ partition(list,...
Sorting algorithm: quick sort Exercise One (20 marks) Given the following program body for implementing Quick sort, complete the program by writing code where required import java.util.Random; public class QuickSort public void quickSectlinti] A) QuickSort/A, O, A.length-1); private void guickSortlin Aiat low.int high) //Complete the code for the quicksort method (5 marks] private void swaplint[] a, int indexl, int index2) //Complete the code for the swap method [3 marks] private int setPivotlint low, int high) Random rand = new Random();...
Modify the sorts (selection sort, insertion sort, bubble sort, quick sort, and merge sort) by adding code to each to tally the total number of comparisons and total execution time of each algorithm. Execute the sort algorithms against the same list, recording information for the total number of comparisons and total execution time for each algorithm. Try several different lists, including at least one that is already in sorted order. ---------------------------------------------------------------------------------------------------------------- /** * Sorting demonstrates sorting and searching on an...
c++ please read all question edit the program to test different random sizes of the array and give me the time in a file will be like random size of the array and next to it the time it took for each size Im trying to do time analysis for Quick sort but i keep getting time = 0 also i want edit the program to test different random sizes of the array and give me the time in a...
Java Programming Write a program to find the number of comparison using binarySearch and the sequentialSearch algorithms as follows: Suppose list is an array of 2500 elements. 1. Use a random number generator to fill list; 2. Use a sorting algorithm to sort list; 3. Search list for some items as follows: a) Use the binary search algorithm to search list (please work on SearchSortAlgorithms.java and modify the algorithm to count the number of comparisons) b) Use the sequential search...
//Generic interface that describes various searching and sorting //algorithms. Note that the type parameter is unbounded. However, //for these algorithms to work correctly, the data objects must //be compared using the method compareTo and equals. //In other words, the classes implementing the list objects //must implement the interface Comparable. The type parameter T //is unbounded because we would like to use these algorithms to //work on an array of objects as well as on objects of the classes //UnorderedArrayList and...
7) Here is the code for the partition function (used by Quick Sort). Explain the purpose of each line of code. int partition (int* vals, int low, int high) { int lowpos = low; low++; while (low <= high) { while (low <= high && vals[low] <= vals [lowpos]) low++; while (high >= low && vals[high) > vals[lowpos]) high--; if (low < high) swap (&vals[low], &vals[high]); swap (&vals[lowpos], &vals[high]); return high;