CODEWITHSUNDEEP
c++arrayspointersmerge
Muhammad Abdullah BSCS 2022 FA
Muhammad Abdullah BSCS 2022 FA

Reputation: 37

Problem in merging two sorted arrays using pointers

I am trying to merge two sorted arrays using pointers. The third loop is working food upto first arr[5] but then show garbage values afterwards. is the sorting techniqure wrong or am I using pointers incorrectly?

#include<iostream>
using namespace std;


int main() {
    int arr1[] = { 1,3,4,6 };
    int arr2[] = { 2,3,4,5 };
    int n1 = 4;
    int n2 = 4;
    int arr3[10];
    int* endptr = &arr1[0];
    int* endptr2 = &arr2[0];
    int* endptr3 = arr3;
    int k = 0;

   
    while (endptr < &arr1[n1-1] &&endptr2  < &arr2[n2-1]) {
        if (endptr[0] < endptr2[0]) {
            endptr3[k++] = endptr[0];
            endptr++;
        }
            
        else {
            endptr3[k++] = endptr2[0];
            endptr2++;
        }
    }
    while (endptr < &arr1[n1 - 1]) {
        endptr3[k++] = endptr[0];
        endptr++;
    }

    while (endptr2 < &arr2[n2 - 1]) {
        endptr3[k++] = endptr[0];
        endptr2++;
    }
    cout << arr3[5];
}

I got the results up to first 6 elements and then get garbage values.

Upvotes: 2

Views: 139

Answers (1)

D&#250;thomhas
D&#250;thomhas

Reputation: 10028

The way you are using the pointers is negatively affecting your thought process.

Let’s abstract it to a function to help make it cleaner:

void merge(
  int * first1, int * last1,  // elements of array1
  int * first2, int * last2,  // elements of array2
  int * dest )                // where to put sorted data

This is the “iterator” idiom used by C++ algorithms. first points to the first element. last points to one-past the last element. (And we assume that dest points to enough space to contain the results.) So:

int array1[] = { 1,3,4,6 };
int array2[] = { 2,3,4,5,7 };
int array3[9];  // enough room for array1+array2

merge( 
  array1, array1+4,  // first array has 4 elements
  array2, array2+5,  // second array has 5 elements
  array3 );          // destination array has 4+5=9 elements

C++ actually gives us a couple of functions to get the first and last pointers to whatever underlying sequence container you’ve got:

merge(
  std::begin(array1), std::end(array1),
  std::begin(array2), std::end(array2),
  std::begin(array3) );

Now we can reconsider our merge algorithm.

void merge(...)
{
  // while both array1 and array2 have elements:
  while ((first1 != last1) and (first2 != last2))
  {
    if (*first2 < *first1)
      *dest++ = *first2++;
    else
      *dest++ = *first1++;
  }

  // if array1 has any leftover elements:
  while (first1 != last1)
    *dest++ = *first1++;

  // if array2 has any leftover elements:
  while (first2 != last2)
    *dest++ = *first2++;
}

In particular, notice:

  • We can easily check whether an array has elements by comparing the first and last pointers directly. When first == last, there are no elements, since last is one-past the end of the source array.
  • Comparison is simple enough. We could have written that as if (first2[0] < first1[0]) but that is less idiomatic than just using the * operator.
  • Copying a value is as simple as a dereference and increment on both sides of the assignment.
  • The three loops of the merge all work on a simple “are there elements left?” check.

Note also how we kept the test condition to a strict less-than comparison. That has ramifications for generic programming (for example, merge sorting in non-increasing order), but I’ll leave it at that for today...

Upvotes: 4

Related Questions