Partition an array for use with 'ksmall' algorithm. For this task you have to write the C function, partition_array(), that partitions the data around a pivot value. You will be implementing Step 1 of a famous algorithm 'ksmall' for this task. The algorithm has two basic steps. Step 1: Partition the data around a pivot value such that all the elements to the left of pivot index are smaller than the pivot value and the ones to the right are greater than the pivot value. Step 2: Recursively call the function 'kSmall()', on the partition that contains the kth smallest element. Details are given in the attached document. (you don't have to worry about this step) For this task you will develop the function partition_array(). The partition algorithm chooses some element p (called the pivot), then rearranges the array such that: • All elements less than or equal to p are before p. • All elements greater than p are after p. • p is in the position it would occupy if the array were sorted. • The algorithm then returns the index of p. • For this implementation your algorithm will always choose the last element of the input array as pivot. It has the following prototype: int partition_array(float * ptr_array, int size);

Answer:

The required method is as follows:

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;


/*
 * This method partitions the given array using a partition key.
 * The last element of the array is chosen as the partition key.
 * All elements less than or equal to the partitiion key is moved
 * to the left of the partition key, and all numbers greater than 
 * the partition key is moved to its right.
 * 
 * @param ptr_array: the array to be partitioned.
 * @param size: size of the array.
 * @return: the index of the partition key in the new array.
 */
int partition_array(float* ptr_array, int size) {
    // two temporary arrays to store the left and right values of the partition key.
    float temp_array_left[size], temp_array_right[size];
    
    // index variables to keep track of the next number to be filled in each partition.
    // for example, if index_left is 1, the next element to the left of partition key will
    // be stored at index 1 in the above temporary array.
    // We initialize both the indexes to 0.
    int index_left = 0, index_right = 0;
    
    // Chosing the partition key as the last element of the array.
    float partition_key = *(ptr_array+size-1);
    
    // We iterate over the array and partition elements into the temporary array.
    // The partition key will be the last element in the left array.
    for(int i=0; i<size; i++) {
        if(*(ptr_array+i) <= partition_key) {
            temp_array_left[index_left] = *(ptr_array+i);
            index_left++;
        } else {
            temp_array_right[index_right] = *(ptr_array+i);
            index_right++;
        }
    }
    
    // Copy over the left partition to the original array.
    int index = 0;
    for(int i=0; i<index_left; i++, index++) {
        *(ptr_array+index) = temp_array_left[i];
    }
    
    // Copy over the right partition to the original array.
    for(int i=0; i<index_right; i++, index++) {
        *(ptr_array+index) = temp_array_right[i];
    }
    
    
    // Return the index of the partition key in the array.
    return index_left-1;
}

The main method to test the partition method:

int main() {
    float arr[7] = {-6.4, 10.1, 6.7, -1.4, 8.3, -9.6, 3.3};
    
    // Printing the original array.
    printf("Printiing the original array: \n");
    for(int i=0; i<7; i++) {
        printf("%0.1f ", arr[i]);
    }
    printf("\n");
    
    // Partitioning the array, 3.3 should be used as the partition key.
    int index = partition_array(arr, 7);
    
    // Printing the index and partitioned array
    // The index should be 3, and all the elements less than 3.3 should be to the left.
    printf("Partition index: %d\n", index);
    printf("Printiing the partitioned array: \n");
    for(int i=0; i<7; i++) {
        printf("%0.1f ", arr[i]);
    }
    
    printf("\n");
    return 0;
}

Step-by-step explanation

Added explanation in the comments. Please found the output attached for the test run.

PFA