#include <iostream> #include <algorithm> // Provides swap #include <cstdlib> //

Question

#include <iostream>

#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(int argc, const char * argv[] )

{

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)

// Library facilities used: itemtool.h, stdlib.h

//

// NOTES FROM THE IMPLEMENTOR:

// How the partition works on small arrays:

//

// Notice that n=0 is not permitted by the precondition.

//

// If n=1, then too_big_index is initialized as 1, and too_small_index is

// initialized as 0. Therefore, the body of the loop is never executed,

// and after the loop pivot_index is set to zero.

//

// If n=2, then both too_big_index and too_small_index are initialized as 1.

// The loop is entered, and there are two cases to consider:

// -- if data[1] <= pivot, then too_big_index increases to 2, and

// too_small_index stays at 1. The if-statement at the bottom of the loop

// is then skipped, and after the loop we copy data[1] down to data[0],

// and copy the pivot into data[0]. Thus, the smaller element is in

// data[0], and the larger element (the pivot) is in data[1].

// -- if data[1] > pivot, then too_big_index stays at 1, and too_small_index

// decreases to 0. The if-statement at the bottom of the loop is then

// skipped, and after the loop we end up copying the pivot onto data[0]

// (leaving data[1] alone). Thus, the smaller element (the pivot) remains

// at data[0], leaving the larger element at data[1].

{  

//-- Implementation is left to the student

}

1. First Implement the authors Partition Function (psudo code is given)

2. Second Rewrite the parition function by selecting the median of three random values from the array.

3. Third Write another version using 5 values instead of 3

Explanation / Answer

1. void partition(int a[],int start,int end)

2. function quicksort(array)

3. #!/usr/bin/env python

for x in range(1,101):

s = ""

if x % 3 == 0:

s += "Fizz"

if x % 5 == 0:

s += "Buzz"

if s == "":

s = x print s

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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