Question

Programming lang C++

Given a file of 100,000 unsorted integers, write a program that reads those integers into an array and sorts the integers in the array. The program should then prompt the user for an index, and then display the integer at that index.

For example, if the array contains ten integers and the contents are

79 4 42 51 12 22 33 17 91 10

after sorting, the integer at index 6 is 42

You are encouraged to use this data to test your program.

Answer 1

Following is the solution to above problem

In this i have used merge sort and fstream

Code-

--------------------------------------------------------------------------------------------------------

#include<stdlib.h>
#include<stdio.h>
#include <fstream>
#include<iostream>

using namespace std;

//merging two sub arrays
void merge(int s[], int l, int m, int r)
{
   int i, j, k;
   int n1 = m - l + 1;
   int n2 = r - m;

   int L[n1], R[n2];

   for (i = 0; i < n1; i++)
       L[i] = s[l + i];
   for (j = 0; j < n2; j++)
       R[j] = s[m + 1+ j];

   i = 0;
   j = 0;
   k = l;
   while (i < n1 && j < n2)
   {
       if (L[i] <= R[j])
       {
           s[k] = L[i];
           i++;
       }
       else
       {
           s[k] = R[j];
           j++;
       }
       k++;
   }

   //remaining elements of first temp array
   while (i < n1)
   {
       s[k] = L[i];
       i++;
       k++;
   }

   //remaining elements of second temp array
   while (j < n2)
   {
       s[k] = R[j];
       j++;
       k++;
   }
}

void mergeSort(int s[], int a, int b)
{
   if (a < b)
   {

       int m = (a+b)/2;

       mergeSort(s, a, m); //first half
       mergeSort(s, m+1, b); //second half

       merge(s, a, m, b); // send to combine array
   }
}

int main()
{
   int sum = 0,i=0,size;
   cout<<"Enter no of intergers that file contains :";
   cin>>size;
int m,ui[size];
int index;
ifstream file;

file.open("a.txt");
//check if file is opened correctly
if (!file) {
cout << "Unable to open file";
exit(1);
}

while (file >> m) {
ui[i]=m;
i++;
}

file.close();

mergeSort(ui, 0, size - 1);

cout<<"\nSorted Array is : "<<"\n";

for(i=0;i<10;i++)
cout<<ui[i]<<" ";

cout<<"\nEnter index to display sorted integer - ";
cin>>index;
cout<<"\nSorted integer is :"<<ui[index];

return 0;
}
-------------------------------------------------------------------