Sorting very large arrays using techniques such as bubble sort or insertion sort

Question

Sorting very large arrays using techniques such as bubble sort or insertion sort is prohibitively time consuming. One approach often used to sort large arrays is to divide the array into a number of smaller segments which are then sorted. The sorted array segments are subsequently merged in the proper overall order. In this QUIZ, you are required to develop and test a C++ program, as follows: a. Implement a sorting function void my_sort(int* Array, int first, int last). The function sorts the elements of Array in ascending order using either bubble sort or insertion sort. The parameters first and last are, respectively, the indices of the first and last elements of the array segment to be sorted. In the event that the whole array is sorted, we set first = o and last = N - 1, where N is the size of Array. b. Given an array Array of size N, divide the array into two segments of equal or nearly equal lengths N_1 and N_2, N_3 + N_2 = N. Using my_sort, sort each of the two array segments in ascending order separately. c. Merge the two sorted array segments into a single array in the proper overall order. d. Test your program using the input data shown. The output of the program is the input data sorted in ascending order. N = 100 Show your complete code and output on the back page. Demonstration of the program developed to your instructor before leaving is required. Specifically, show the input data, the sorted array segments, and the sorted full data. Best Wishes!! Hesham A Auda

Explanation / Answer

// create space for 100 ints and initialize the first 100

#include <iostream.h>
#include<conio.h>

using namespace std;

#define MAX_LENGTH=100;

int main()
{

int array[MAX_LENGTH],sortedArray[MAX_LENGTH],one[n], two[n];
int n = MAX_LENGTH/2;

//taking input for the main array

int a;
clrscr();
cout<<"Enter data in Array: ";
for(a=0;a<MAX_LENGTH;a++)
{
cin>>array[a];
}

//divide the array into two sub-arrays named one & two

// copy memory of the first 50 ints of array to one
memcpy(one, array, MAX_LENGTH/2 * sizeof(int));
// copy 50 ints worth of memory from the 51st item in array onwards
memcpy(two, &array[50], MAX_LENGTH/2 * sizeof(int));

// Bubble Sort two sub-arrays separately
  
bubble_sort (one, n);
cout << "Sorted Array : " << endl;
for (int i = 0; i < n; ++i)
cout << one[i] << " ";
  

bubble_sort (two, n);
cout << "Sorted Array : " << endl;
for (int j = 0; j < n; ++j)
cout << two[j] << " ";
  

//Merging two sorted array into sortedArray

for(i=0; i<n; i++)
   {
       sortedArray[i]=one[i];
   }
  
   for(i=0, k=n; k<MAX_LENGTH && i<n; i++, k++)
   {
       sortedArray[k]=two[i];
   }
   cout<<"Now the new array after merging is : ";
   for(i=0; i<size; i++)
   {
       cout<<sortedArray[i]<<" ";
   }
   getch();

}

//Bubble Sort function

void bubble_sort (int arr[], int s)
{
for (int i = 0; i < s; ++i)
for (int j = 0; j < s - i - 1; ++j)
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}      

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.