Quicksort algorithm trace Quicksort algorithm on the two lists (i.e. arrays), wh
ID: 3679426 • Letter: Q
Question
Quicksort algorithm
trace Quicksort algorithm on the two lists (i.e. arrays), which have already had their median of three pivot’s swapped into the first array element.
[62, 71, 66, 69, 56] and [85, 92, 79, 97, 82, 99]
Don’t forget to list the array’s element order after each exchange of elements and indent the body of the while loops and if-statement.
For convenience, here’s the first few lines in the traces, please complete the rest:
Sublist 1 Trace:
1. (Q3) (S1) QuickSort([62, 71, 66, 69, 56], 0, 4)
2. (S2) pivot = 62
3. (S3) left = 0
4. (S4) right = 4
Sublist 2 Trace:
1. (Q3) (S1) QuickSort([85, 92, 79, 97, 82, 99], 0, 5)
2. (S2) pivot = 79
3. (S3) left = 0
4. (S4) right = 5
Explanation / Answer
62 71 66 69 56 85 92 79 97 82 99 Pivot 62 Left 0 Right 10
56 62 66 69 71 85 92 79 97 82 99 Pivot 56 Left 0 Right 0
56 62 66 69 71 85 92 79 97 82 99 Pivot 66 Left 2 Right 10
56 62 66 69 71 85 92 79 97 82 99 Pivot 66 Left 2 Right 1
56 62 66 69 71 85 92 79 97 82 99 Pivot 69 Left 3 Right 10
56 62 66 69 71 85 92 79 97 82 99 Pivot 69 Left 3 Right 2
56 62 66 69 71 85 92 79 97 82 99 Pivot 71 Left 4 Right 10
56 62 66 69 71 85 92 79 97 82 99 Pivot 71 Left 4 Right 3
56 62 66 69 71 85 92 79 97 82 99 Pivot 85 Left 5 Right 10
56 62 66 69 71 79 82 85 97 92 99 Pivot 79 Left 5 Right 6
56 62 66 69 71 79 82 85 97 92 99 Pivot 79 Left 5 Right 4
56 62 66 69 71 79 82 85 97 92 99 Pivot 82 Left 6 Right 6
56 62 66 69 71 79 82 85 97 92 99 Pivot 97 Left 8 Right 10
56 62 66 69 71 79 82 85 92 97 99 Pivot 92 Left 8 Right 8
56 62 66 69 71 79 82 85 92 97 99 Pivot 99 Left 10 Right 10
//-------------Find the Below program traces any list of number-------------------
//you just need to change the list.
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author abhinay009
*/
public class QuickSort {
public static void quickSort(int array[])
{
quickSort(array, 0, array.length - 1);
}
public static void quickSort(int array[], int start, int end)
{
int i = start;
int k = end;
for(int ind=0;ind<array.length;ind++)
{
System.out.print(" "+array[ind]);
}
System.out.print(" Pivot "+array[start]+" Left "+start+" Right "+end);
System.out.println();
if (end - start >= 1)
{
int pivot = array[start];
while (k > i)
{
while (array[i] <= pivot && i <= end && k > i)
i++;
while (array[k] > pivot && k >= start && k >= i)
k--;
if (k > i)
swap(array, i, k);
}
swap(array, start, k);
quickSort(array, start, k - 1);
quickSort(array, k + 1, end);
}
else
{
return;
}
}
public static void swap(int array[], int index1, int index2)
{
int temp = array[index1]; // store the first value in a temp
array[index1] = array[index2]; // copy the value of the second into the first
array[index2] = temp; // copy the value of the temp into the second
}
public static void main(String args[])
{
int[] list={62, 71, 66, 69, 56,85, 92, 79, 97, 82, 99};
quickSort(list);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.