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_1 + 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 Array: [406 157 415 318 472 46 252 187 364 481 450 90 390 35 452 74 196 312 142 160 143 220 483 392 443 488 79 234 68 150 356 496 69 88 177 12 288 120 222 270 441 422 103 321 65 316 448 331 117 183 184 128 323 141 467 31 172 48 95 359 239 209 398 99 440 171 86 233 293 162 121 61 317 52 54 273 30 226 421 64 204 444 418 275 263 108 10 149 497 20 97 136 139 200 266 238 493 22 17 39]

Explanation / Answer

#include<iostream.h>

void my_sort(int *Array, int first, int last){
    int temp;
    int index;

    index = last;
    for (int i = first; i <= last; ++i){
        index = index -1;
        for (int j = first; j <= index; ++j){
            if (Array[j] > Array[j+1]){
               temp = Array[j];
               Array[j] = Array[j+1];
               Array[j+1] = temp;
            }
           
        }
    }
}

void main(){

   int Array[100] = { 406, 157, 415,........} //Assuming array has been initialized
   int sortedArray[100];
   int count;

   my_sort(Array, 0, 50);
   my_sort(Array, 51, 99);

   count = -1;
   while (i < 51 && j < 100){
       if (Array[i] < Array[j){
          count++;
          sortedArray[count] = Array[i];
          i++;
       }
       if (Array[i] > Array[j){
          count++;
          sortedArray[count] = Array[j];
          j++;
       }
       if (Array[i] == Array[j){
          count++;
          sortedArray[count] = Array[i];
          i++
          count++;
          sortedArray[count] = Array[j];
          j++;
       }
   }
   if (i == 51){
      while (j < 100) {
           count++;
           sortedArray[count] = Array[j];
           j++;
      }
   }
   if (j == 100){
      while (i < 51) {
           count++;
           sortedArray[count] = Array[i];
           i++;
      }
   }    
   
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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