Question

Please solve this problem, in c++ (algoritms) write code and explaination how to solve it!

1) N numbers are given. The first K of them are sorted in ascending order, the remaining NK are also sorted in ascending order. Sort numbers in ascending order in O (N).

Input data format N - number of numbers, K - number of numbers in the first half (sorted).

Example input

10 6

1 2 5 6 8 9 3 4 7 12

Sample Output

1 2 3 4 5 6 7 8 9 12

Answer 1

C++program execution starts with main() function. So define a main() function and declare required variables.

1. Read n and k from user.
2. Create an array, arr of size n to store input data
3. Create another array, sorted of size n to store sorted items.
4. Read n inputs to array arr.
5. Initialize a=0 (a corresponds to index in first sorted half) and b= k (b corresponds to index in last sorted half.)
6. For i varies from 0 to n-1,
7. if b>=n or  (a<k and arr[a]<arr[b]), then sorted[i] = arr[a] and increment a.
8. otherwise sorted[i] = arr[b] and increment b.
9. At the end of execution array sorted will be having all sorted elements.
10. Print elemets in sorted array.

Loop body has fixed number of statements and hence loop body has constant time complexity, and we are using only one for-loop for sorting, and i varies from 0 to n-1. Hence the complexity of sorting = O(N)

Program:

#include <iostream>
using namespace std;
int main()
{
    int n, k;                           /* declare variables */
    cin>>n>>k;                          /* read n and k */
    int arr[n];                         /* declare array arr to store input data */
    int sorted[n];                      /* declare array sorted to store sorted elements */
    for(int i=0;i<n;i++){               /* read n inputs */
        cin>>arr[i];
    }
    int a=0, b=k;                       /* initialize a=0 and b=k */
    
    for(int i=0;i<n;i++){               /*for i varies from 1 to n-1 */
        if(b>=n||a<k&&arr[a]<arr[b]){   /* if b>n or (a<k and arr[a]<arr[b]) */
            sorted[i] = arr[a];         /* add element from first half to sorted */
            a++;                        /* increment a */
        }
        else{                           /* otherwise add element from last half to sorted */
            sorted[i] = arr[b];
            b++;                        /* increment b */
        }
    }
    
    for(int i=0;i<n;i++){               /* print sorted array */
        cout<<sorted[i]<<" ";
    }
    return 0;
}

Screenshot:

Output:

Please don't forget to give a Thumbs Up.