Question

Trace the partition function provided for the array A = {27, 38, 12, 39, 27, 16}. After each iter...

Trace the partition function provided for the array A = {27, 38, 12, 39, 27, 16}. After each iteration of the loop check that the invariant is true.

int partition(int A[], int first, int last) {

// Take A[first] as the item to be placed in correct

// sorted order. Set pivotIndex to that item and return it.

  

int p= A[first]; // Initialisation to satisfy the invariant.

int LastS1= first;

int FirstUnknown= first + 1;

int temp;

while (FirstUnknown <= last) {

// INVARIANT: The items in myArray[first+1..LastS1]

// are all strictly less than p,

// and the items in myArray[LastS1+1.. FirstUnknown-1] are at least p.

if (A[FirstUnknown] < p) { // Case: need to add to S1

LastS1++; // Increment LastS1

temp= A[FirstUnknown];

A[FirstUnknown]= A[LastS1];

A[LastS1]= temp;

FirstUnknown++;

}

else {

FirstUnknown++;

} // Case: Need to add to S2

}

temp= A[first];

A[first]= A[LastS1];

A[LastS1]= temp;

FirstUnknown++;

return LastS1;

}

0 0
Add a comment Improve this question Transcribed image text
Answer #1

first in this code

array a[]={27,38,12,39,27,16}

variables are

initially

FirstUnknown =1

p=0

LastS1=0

FirstUnknown P LastS1 a[FirstUnknown] a[LastS1] array
1 27 0 38 27 27,38,12,39,27,16
2 27 0 12 27 27,38,12,39,27,16
3 27 1 39 12 27,12,38,39,27,16
4 27 1 27 12 27,12,38,39,27,16
5 27 1 16 12 27,12,38,39,27,16
6 27 2 - 16 27,12,16,39,27,38

now its change

first and LastS1

so that a[first]=a[LastS1]

so that a[first]=16

and a[LastS1]=27

the sequence is 16,12,27,39,27,38.

SUMMERY:

code is goto first to last element of array

then check a[Firstunknown] < (p=a[first])

if condition satisfy then do LastS1++; and change value of LastS1 and FirstUnknown while end of the array

at last changed value of LastS1 and First element.

please like,

comment if you have any query.

Add a comment
Know the answer?
Add Answer to:
Trace the partition function provided for the array A = {27, 38, 12, 39, 27, 16}. After each iter...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • Trace the partition function provided for the array A = {27, 38, 12, 39, 27, 16}....

    Trace the partition function provided for the array A = {27, 38, 12, 39, 27, 16}. After each iteration of the loop check that the invariant is true. int partition(int A[], int first, int last) { // Take A[first] as the item to be placed in correct // sorted order. Set pivotIndex to that item and return it.    int p= A[first]; // Initialisation to satisfy the invariant. int LastS1= first; int FirstUnknown= first + 1; int temp; while (FirstUnknown...

  • JAVA- Trace the recursive quick sort and partition methods in Lab6.java for this list of numbers:...

    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...

    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: ";...

  • A test harness program for testing sorting methods is provided with the rest of the textbook...

    A test harness program for testing sorting methods is provided with the rest of the textbook program files. It is the file Sorts.java in the ch11 package. The program includes a swap method that is used by all the sorting methods to swap array elements. Describe an approach to modifying the program so that after calling a sorting method the program prints out the number of swaps needed by the sorting method. Implement your approach. Test your new program by...

  • C++ Time the sequential search and the binary search methods several times each for randomly generated...

    C++ Time the sequential search and the binary search methods several times each for randomly generated values, then record the results in a table. Do not time individual searches, but groups of them. For example, time 100 searches together or 1,000 searches together. Compare the running times of these two search methods that are obtained during the experiment. Regarding the efficiency of both search methods, what conclusion can be reached from this experiment? Both the table and your conclusions should...

  • Java Programming Write a program to find the number of comparison using binarySearch and the sequentialSearch...

    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....

    //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...

  • Need help with the trickle down This is the maxheap.h #ifndef MAXHEAP_H_INCLUDED #define MAXHEAP_H_INCLUDED #include <vector>...

    Need help with the trickle down This is the maxheap.h #ifndef MAXHEAP_H_INCLUDED #define MAXHEAP_H_INCLUDED #include <vector> #include <sstream> #include <string> #include <queue> #include <cmath> // pow() using namespace std; #define PARENT(i) ((i-1) / 2) #define LINE_WIDTH 60.0 template<class T> class MaxHeap{ // private: vector<T> heap; void bubbleUp(int id);    void Heapify() { int length = heap.size(); for(int i=length / 2 -1; i>=0; --i) trickleDown(i); }; public: MaxHeap( vector<T> &vector ) : heap(vector) { Heapify(); } ; MaxHeap() {}; void trickleDown(int...

  • Objective: GUI Layout manager Download one of the sample GUI layout program. Use any GUI layout...

    Objective: GUI Layout manager Download one of the sample GUI layout program. Use any GUI layout to add buttons to start each sort and display the System.nanoTime in common TextArea panel. The question is a bit confusing so i will try to simplify it. Using the GUI ( I made a unclick able one so you have to make it clickable), allow a user to sort the text file based on what they click on. example: if i click merge...

  • Practical 5: Write a program that implements several sorting algorithms, and use it to demonstrate the comparative perfo...

    Practical 5: Write a program that implements several sorting algorithms, and use it to demonstrate the comparative performance of the algorithms for a variety of data sets. Need Help With this Sorting Algorithm task for C++ Base Code for sorting.cpp is given. The header file is not included in this. Help would be much appreciated as I have not started on this due to personal reasons #include <cstdlib> #include <iostream> #include <getopt.h> using namespace std; long compares; // for counting...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT