c++: Kth Smallest element in an array using partition

Question

Could anyone check my code? I'm not getting the right output when I'm trying to find the kth smallest.

This is the algorithm:
create a function int my_partition(int *anArray, int first, int last)
*anArray is the array being partitioned, first and last are the beginning and end of the section of the array where the pivot will be place. When it is done, my_partition will return the pivot index.
the value at anArray[first] is the pivot
two values are set: left_position is set to first + 1, right_position is set to last
while left_position < right_position
while anArray[left_position] is less than pivot
add on to left_position
while anArray[right_position] is greater than pivot
subtract on from right_position
if right_position > left_position
swap the values in anArray[left_position] and anArray[right_position]
increment left_position
decrement right_position
store values of anArray[right_position] in anArray[first]
store the pivot in anArray[right_position]
return right_position as the pivot index
test the kSmall by writing a main function where the array that is to be passed to the function must be generated as a dynamic array using new operator.\

My output: Enter array size:
8
Enter 8 elements in array:
1
5
8
3
6
2
4
7
You entered:
1 5 8 3 6 2 4 7
Enter the value of k:
5
K’th smallest element: 0%

#include <iostream>
using namespace std;


int partition(int *anArray, int first, int last)
{
    int pivot = anArray[first];
    int left_side = first +1;
    int right_side = last;
    
    while (left_side <= right_side)
    {
        while (anArray[left_side] < pivot)
        {
            left_side++;
        }
        while (anArray[right_side] > pivot)
        {
            right_side--;
        }
        if (left_side < right_side)
        {
            int temp1 = anArray[left_side];
            anArray[left_side] = anArray[right_side];
            anArray[right_side] = temp1;
        }
    }
    int temp2 = anArray[first];
    anArray[first] = anArray[right_side];
    anArray[right_side] = temp2;

    return right_side;
}


int kSmall(int k, int *anArray, int first, int last)
{
    int pivotIndex = partition(anArray, first, last);
    if (k < pivotIndex - first + 1)
    {
        return kSmall(k, anArray, first, pivotIndex-1);
    }
    else if (k = pivotIndex - first +1)
    {
        return anArray[pivotIndex];
    }
    else
    {
        return (k - (pivotIndex - first + 1), anArray, pivotIndex + 1, last);
    }
}

int main()
{
    int size;
    cout << "Enter array size: " << endl;
    cin >> size;

    int *arr = new int(size);

    cout << "Enter " << size << " elements in array: " << endl;
    for (int i=0; i<size; i++)
    {
        cin >> arr[i];
    }

    cout << "You entered: " << endl;
    for (int i=0; i<size; i++)
    {
        cout << arr[i] << " " << endl;;
    }

    int k;
    cout << "Enter the value of k: " << endl;
    cin >> k;
    int first = arr[0];
    int last = arr[size];
    cout << "K’th smallest element: " << kSmall(k,arr,first,last);
}

Answer 1

Continuing from the comments above, your two primary syntax problems would have been caught by simply compiling with warnings enabled. That would have flagged the problem with the assignment instead of comparison in else if (k = pivotIndex - first +1) and would have pointed you to the use of the comma operator in return (k - (pivotIndex - first + 1), anArray, pivotIndex + 1, last); (which should be return kSmall (...)). Both problems occur in kSmall() and can be remedied as:

int kSmall (int k, int *anArray, int first, int last)
{
    int pivotIndex = partition(anArray, first, last);
    if (k < pivotIndex - first + 1)
    {
        return kSmall (k, anArray, first, pivotIndex-1);
    }
    else if (k == pivotIndex - first +1)    /* == for comparison */
    {
        return anArray[pivotIndex];
    }
    else
    {
        /* return kSmall (...) */
        return kSmall (k - (pivotIndex - first + 1), 
                        anArray, pivotIndex + 1, last);
    }
}

Your next problem is simply a logic problem passing the value of the first and last elements instead of the first and last indexes as specified in your problem statement and as the parameters kSmall() takes. What's needed is:

    int first = 0;          /* first and last element indexes */
    int last = size - 1;
    std::cout << "K’th smallest element: " << kSmall(k,arr,first,last) << '\n';

A couple of other tips, see: Why is “using namespace std;” considered bad practice?. Additionally, when you output a string literal, e.g. "Enter array size: ", there is no need to add << std::endl -- simply include '\n' as the last character in your string-literal:

    std::cout << "Enter array size: \n";  /* std::endl not needed, \n is fine */

You cannot use any input function correctly unless you check the stream state after the input and before you attempt to use the variable holding the input. Without checking the stream state, see Member State Functions std::basic_iostream, you cannot know whether the input succeeded or failed. Blindly proceeding to use the variable after a .bad(), .fail() or .eof() state is triggered will result in Undefined Behavior. Instead, validate the input, e.g.

    if (!(std::cin >> size)) {  /* validate every input */
        std::cerr << "error: invalid integer input.\n";
        return 1;
    }

(note: that is the minimal validation. To recover and continue, you would need to clear() the error and then use std::cin.ignore (...) to remove the offending characters from the input stream)

Lastly, your allocation of int *arr = new int(size); is incorrect. It allocates storage for one int and initializes its value to 8. See new expression (example under the heading Memory Leaks). Instead int *arr = new int[size]; is the correct form.

Putting those tips altogether in main() you would have:

int main()
{
    int size;
    std::cout << "Enter array size: \n";  /* std::endl not needed, \n is fine */
    
    if (!(std::cin >> size)) {  /* validate every input */
        std::cerr << "error: invalid integer input.\n";
        return 1;
    }

    int *arr = new int[size];

    std::cout << "Enter " << size << " elements in array: \n";
    for (int i = 0; i < size; i++)
    {
        if (!(std::cin >> arr[i])) {    /* ditto */
            std::cerr << "error: invalid integer input.\n";
            return 1;
        }
    }

    std::cout << "You entered: \n";
    for (int i = 0; i < size; i++)
    {
        if (i)
            std::cout.put(' ');
        
        std::cout << arr[i];
        
        if (i == size - 1)
            std::cout.put('\n');
    }

    int k;
    std::cout << "Enter the value of k: \n";
    if (!(std::cin >> k)) { /* ditto */
        std::cerr << "error: invalid integer input.\n";
        return 1;
    }
    
    int first = 0;          /* first and last element indexes */
    int last = size - 1;
    std::cout << "K’th smallest element: " << kSmall(k,arr,first,last) << '\n';
    
    delete[] arr;           /* don't forget to free what you allocated */
}

Compiling, and running provides the correct response, e.g.

./bin/partition_kth_smallest
Enter array size:
8
Enter 8 elements in array:
1 5 8 3 6 2 4 7
You entered:
1 5 8 3 6 2 4 7
Enter the value of k:
5
K’th smallest element: 5

Look things over and let me know if you have further questions.