I need help finish my Partition method #include <algorithm> // Provides swap #in

Question

I need help finish my Partition method

#include <algorithm> // Provides swap

#include <cstdlib> // Provides EXIT_SUCCESS, size_t

#include <iostream> // Provides cout and cin

using namespace std;

// PROTOTYPES of the functions used in this test program:

void quicksort(int data[ ], size_t n);

// Precondition: data is an array with at least n components.

// Postcondition: The elements of data have been rearranged so

// that data[0] <= data[1] <= ... <= data[n-1].

void partition(int data[ ], size_t n, size_t& pivot_index);

// Precondition: n > 1, and data is an array (or subarray)

// with at least n elements.

// Postcondition: The function has selected some "pivot value"

// that occurs in data[0]..data[n-1]. The elements of data

// have then been rearranged, and the pivot index set so that:

// -- data[pivot_index] is equal to the pivot;

// -- Each item before data[pivot_index] is <= the pivot;

// -- Each item after data[pivot_index] is >= the pivot.

int main( )

{

const char BLANK = ' ';

const size_t ARRAY_SIZE = 10; // Number of elements in the array to be sorted

int data[ARRAY_SIZE]; // Array of integers to be sorted

int user_input; // Number typed by the user

size_t number_of_elements; // How much of the array is used

size_t i; // Array index

// Provide some instructions

cout << "Please type up to " << ARRAY_SIZE << " positive integers.";

cout << "Indicate the list's end with a zero." << endl;

// Read the input numbers

number_of_elements = 0;

cin >> user_input;

while ((user_input != 0) && (number_of_elements < ARRAY_SIZE))

{

data[number_of_elements] = user_input;

number_of_elements++;

cin >> user_input;

}

// Sort the numbers and print the result with two blanks after each number

quicksort(data, number_of_elements);

cout << "In sorted order, your numbers are: " << endl;

for (i = 0; i < number_of_elements; i++)

cout << data[i] << BLANK << BLANK;

cout << endl;

return EXIT_SUCCESS;

}

void quicksort(int data[ ], size_t n)

// Library facilities used: cstdlib

{

size_t pivot_index; // Array index for the pivot element

size_t n1; // Number of elements before the pivot element

size_t n2; // Number of elements after the pivot element

if (n > 1)

{

// Partition the array, and set the pivot index.

partition(data, n, pivot_index);

// Compute the sizes of the subarrays.

n1 = pivot_index;

n2 = n - n1 - 1;

// Recursive calls will now sort the subarrays.

quicksort(data, n1);

quicksort((data + pivot_index + 1), n2);

}

}

void partition(int data[ ], size_t n, size_t& pivot_index){

}

Explanation / Answer

Here is the partition code for you:

void partition(int data[ ], size_t n, size_t& pivot_index){
  
int pivot = 0;
int rb = n - 1;
int low = 0, high = n - 1;
while(low <=high)
{
while(data[pivot] >= data[low] && low <=rb)
low++;
while(data[pivot] < data[high])
high--;
if(pivot != high)
{
data[pivot] = data[pivot] + data[high];
data[high ] = data[pivot] - data[high];
data[pivot] = data[pivot] - data[high];
}
}
pivot_index = high;
  
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.