Question

find the k-th smallest value

given array[ 5, 2, 1, 15, 6, 9, 3, 4, 11] , k=2, the algorithm return the first two value: 1, 2

please show steps of how to output the first 2 values by using merge sort

and please analyze the running time.

your time is greatly appreciated.

Answer 1

It is request to please don't leave without thumbs up I really need it so that I can provide quality answer to you hoping for good thank you! And please don't dislike ask query in comment section

As from the given question it is ask for kth smallest element but in the output you want the k smallest element in the array so as per output of the program i provide the souce code of k smallest number

but as your question is not full or specific as it ask for merge sort if you have any doubts so please ask in comment section

so time complexity of the program is very simple as i have sort the program using sort function which uses merge sort to sorting the element is O(nlogn) and there is another loop which run for k times so time Complexity of that loop is O(k) so total time Complexity of the program is t(n)= O(nlogn) +O(k)

I am attaching the output scnshot of the program which is exactly you want in the question

// C++ code for k largest elements in an array
#include <bits/stdc++.h>

using namespace std;


void kSmallest(int arr[], int n, int k)
{

    // Sort the given array arr


    sort(arr, arr + n);


    // this will print  first k smallest elements

    for (int i = 0; i < k; i++)

        cout << arr[i] << " ";
}

// driver program

int main()
{

    int n,k;
    cout<<"enter the size of array\n ";
    cin>>n;
    cout<<endl;
    cout<<"enter the k value  ";
    cin>>k;
    cout<<endl;
    int arr[1000];
    cout<<"enter the element of the array \n";
    for(int i = 0; i<n; i++)
    cin>>arr[i];

    cout<<"k smallest element are: "<<kSmallest(arr, n, k);
}

Output:

And please upvote it is request THANKYOU!