In the code below I was given unsorted array had to find kth smallest Given an array arr[] and an integer K where K is smaller than size of array, the task is to find the Kth smallest element in the given array. It is given that all array elements are distinct.

#include<bits/stdc  .h>
using namespace std;

Merge function:

void merge(int arr[],int l,int m,int r){
    int marr[(r-l) 1];
    int i=l,j=m 1,k=0;
    for(k;k<=(r-l);k  ){
        if(i==(m 1)){
            marr[k]=arr[j];
            j  ;
        }
        else if(j==(r 1)){
            marr[k]=arr[i];
            i  ;
        }
        else if(arr[i]<=arr[j]){
            marr[k]=arr[i];
            i  ;
        }
        else if(arr[i]>arr[j]){
            marr[k]=arr[j];
            j  ;
        }
    }
    //Below assignment was creating wrong output but cant figure out why?
    for(k=0;k<=(r-l);k  ,l  ){
         arr[l]=marr[k];
     }
//However below code worked instead, in spite tracing same no. of values
//for(int x=l,k=0;x<=r;x  ,k  ){
        
      //  arr[x]=marr[k];
//}

Mergesort:

void mergesort(int arr[], int l,int r){
    if(r<=l)
    return;
    int mid=l (r-l)/2;
    mergesort(arr,l,mid);
    mergesort(arr,mid 1,r);
    merge(arr,l,mid,r);
} 

class Solution{
    public:
    // arr : given array
    // l : starting index of the array i.e 0
    // r : ending index of the array i.e size-1
    // k : find kth smallest element and return using this function
    int kthSmallest(int arr[], int l, int r, int k) {
    
        mergesort(arr,l,r);
   
        return arr[k-1];
        
        

    }
};

Driver Code starts

int main()
{
    int test_case;
    cin>>test_case;
    while(test_case--)
    {
        int number_of_elements;
        cin>>number_of_elements;
        int a[number_of_elements];
        
        for(int i=0;i<number_of_elements;i  )
            cin>>a[i];
            
        int k;
        cin>>k;
        Solution ob;
        cout<<ob.kthSmallest(a, 0, number_of_elements-1, k)<<endl;
    }
    return 0;
}  

Driver Code ends

CodePudding user response：

The non-standard variable length arrays and other considerations notwithstanding (seriously, get a good reference book and reputable tutorial guide), the problem is in your merge algorithm:

At the end of merge you're trying to put the sorted marr data back into arr. That is done here:

for(k=0;k<=(r-l);k  ,l  )
{
    arr[l]=marr[k];
}

The problem is the increment of l, which has the effect of shortening the merge because it causes (r-l) to collapse toward k, while k is ascending upward. This means you don't copy all your data, and you're left not-only with partial sorting, you're left with potential duplicate junk in arr (in fact, it is highly likely).

Replacing that with this:

for (i=0; i<=(r-l);   i)
{
    arr[i l] = marr[i];
}

should fix it for you. This runs i from 0..segment length inclusive, drops the results into the adjusted offset i l location.

Everything either wrong or poor in this code has been deftly mentioned in comments, so I'll leave that for you to address (and believe me, you want to address all of it).