Amdocs Interview Question Testing / Quality Assurances
0of 0 votesGiven an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].
e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2,1,3,3,6,8,8]
For input array: {1, 3, 6, 8, -5, -2, 3, 8 }
Your code return:
{1, 1, 1, 1, 1, 1, 3, 8}
I have tested this algorithm with different inputs. It works without any issue. Can you check it out what is wrong on this algorithm?
Your rotateArray doesn't "rotate" a range with just two elements. In that case endInd = startEnd + 1. So, endInd - startInd is 1, and rotateArray does nothing. Change the test to
if ((endInd - startInd) >= 1)
The other mistake you have is that mergeSortedRangeArray skips the very last element.
Change the while condition to
while (i < j && j < arr.length)
Try you current implementation on {1, 4, 2, 3}.
Unfortunately your solution is O(n^2). It is just an insert sort. It is possible to do the merge in O(n) time.
// java code
public class MergeShort {
/**
* @param args
*/
/**
* @param args
*/
public static void main(String[] args) {
int[] a={4,7,9,20,1,3,10,15};
int i=0, length=8, j, k, temp;
// for(i=0;i<length;i++){
// System.out.println(i+":"+a[i]);
// }
for(j=length/2; j<length; j++){
for(; i<j; i++){
if(a[i] >= a[j]){
temp=a[j];
for(k=j; k>i; k--){
a[k]=a[k-1];
}
a[i]=temp;
i++;
break;
}
}
}
System.out.println("#######################");
for(i=0;i<length;i++){
System.out.println(i+":"+a[i]);
}
}
}
I am downvoting this answer, because there are lots of ways to in-place sort a list, but this brief answer doesn't explain why heapsort would be superior to, say, quicksort, given the partial ordering.
Of the most common divide-and-conquer sorts, mergesort is the one that breaks down the problem by recursively creating two sorted lists, so it would seem like the most appropriate sort to adopt for this problem. Unfortunately, it's really hard to do a mergesort efficiently on array-based lists when you don't have contiguous storage at your disposal for the merged result. If the original list were a linked list instead of an array, then you could do it pretty trivial with no extra storage, but the problem explicitly says this an array.
#include<stdio.h>
void mergetwoSortedRangeArray(int *, int );
void swap(int *, int *);
int main(void){
int a[8]={1,3,6,8,-5,-2,3,8};
int len = sizeof(a)/sizeof(int);
mergetwoSortedRangeArray(a,len);
for(int i=0; i<len; i++){
printf("%d ",a[i]);
}
return 0;
}
void mergetwoSortedRangeArray(int a[], int len){
int i=0, j=len/2;
while(i<j && j<=len){
if(a[j]<a[i]){
for(int k=i; k<j; k++){
swap(&a[k], &a[j]);
}
i++;
j++;
}
else{
i++ ;
}
}
printf("\n");
}
void swap(int *x, int *y){
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
#include<stdio.h>
#include<conio.h>
int _tmain(int argc, _TCHAR* argv[])
{
int a[8],len,*p,temp=0,i,j;
a[8]=(1,3,6,8,-5,-2,3,8);
p=a;
len=sizeof(a)/sizeof(a[0]);
printf("length of the array is : %d",len);
printf("\n");
for( i=0;i<len/2;i++)
{
for( j=len/2;j<len;j++)
{
if(*(p+i) > *(p+j) || *(p+i)==*(p+j))
{
int k=0;
k=k+i;
temp=*(p+j);
printf("%d ",*(p+j));
while(k<=j)
{
*(p+k+1)=*(p+k);
k++;
}
*(p+i)=temp;
}
}
}
for(i=0;i<len;i++)
{
printf("%d ",*(p+i));
}
getch();
return 0;
}
--------------------------------------------------------------------------------------------------
check and plz let me knw tat what is the problem in this code?
C# code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Sort2HalfSortedArrays
{
class Program
{
static void Main(string[] args)
{
int[] array = { 1, 3, 6, 8, -5, -2, 3, 8 };
int[] sortedArray = Sort(array); ;
Console.WriteLine("Sorted Array");
for (int i = 0; i < sortedArray.Length; i++)
{
Console.Write("{0} ", sortedArray[i]);
}
Console.Read();
}
public static int[] Sort(int[] array)
{
int i = 0;
while (array[i] < array[i + 1])
{
if (i + 1 == array.Length - 1)
{
return array;
}
else
{
i++;
}
}
int j = array.Length - 1;
while ((i >= 0) && i < j)
{
if (array[i] >= array[j])
{
int k = i;
while (k < j)
{
int temp = array[k];
array[k] = array[k + 1];
array[k + 1] = temp;
k++;
}
i--;
j -= 2;
}
else
{
j--;
}
}
return array;
}
}
}
output:
Sorted Array
-5,-2,1,3,3,6,8,8
Comment if any issues in this.
Basically what we are doing is comparing the first element of both sorted portion
Scenario 1) in case second portion elemnt is smaller , we are bringing it to front and shifting the elements to right making room for it
Scenario 2) in case first portion elemnt is smaller, just goto second element in first portion, remain at first element in second portion
1,3,6,8,-5,-2,3,8
-5,1,3,6,8,-2,3,8
-5,-2,1,3,6,8,3,8
-5,-2,1,3,6,8,3,8
-5,-2,1,3,3,6,8,8
detail explanation
array length = 8
i = 0 ;
j = length/2; => 4
indices 0 1 2 3 4 5 6 7
values 1 3 6 8 -5 -2 3 8
compare if (a[i] > a[j]) i.e a[0] and a[4] ( 1 > -5 in our example)
place a[j] in a[i] and shift every indices by one
i.e. each a[i+1]= a[i] till a[j];
i++, j++
indices 0 1 2 3 4 5 6 7
values -5 1 3 6 8 -2 3 8
now compare a[1] with a[5] ( 1 > -2) , replace a[1] with a[5] ans shift
indices 0 1 2 3 4 5 6 7
values -5 -2 1 3 6 8 3 8
i++, j++;
compare a[2] with a[6] this time a[i] < a[j], no swap and shifting is required, but dont increase j only i
indices 0 1 2 3 4 5 6 7
values -5 -2 1 3 6 8 3 8
i++; j is not increased
now a[3] with a[6] still a[3] is less than a[6] so increase i only
indices 0 1 2 3 4 5 6 7
values -5 -2 1 3 6 8 3 8
now a[4] with a[6], swap and shift, we get
indices 0 1 2 3 4 5 6 7
values -5 -2 1 3 3 6 8 8
i++, j++
now a[5] with a[7], no change required, increase only i;
similalry done
#include<iostream>
using namespace std;
int main()
{
int i,j,temp,n=8;
int a[8]={1,3,6,8,-5,-2,3,8};
i=0,j=4;
while(i<j && j<n)
{
if(a[j] <= a[i])
{
temp=a[j];
for(int k=j-1;k>=i;k--)
{
a[k+1]=a[k];
}
a[i]=temp;
i++;
j++;
}
else if(a[i]<a[j])i++;
}
for(i=0;i<n;i++)cout<<a[i]<<" ";
cout<<endl;
}
I have solved this problem in c#. Compare the first and mid element on the array, like that we compare the all the array elements. When we find smaller number in the second set of array, need to swap the array elements.
- N on April 07, 2011 Edit | Flag Replyvoid mergetwoSortedRangeArray(int[] arr)
{
int i=0;
int j=(int)arr.Length/2;
while(i<j && j< arr.Length -1)
{
if (arr[i] > arr[j])
{
rotateArray(arr, i, j);
j++;
}
i++;
}
}
void rotateArray(int[] arr, int startInd, int endInd)
{
int newInd = startInd, temp = 0;
int? prevValue = null;
if ((endInd - startInd) > 1)
{
for (int i = startInd; i <= endInd; i++)
{
if (newInd == endInd)
newInd = startInd;
else
newInd++;
temp = arr[newInd];
if (prevValue == null)
arr[newInd] = arr[i];
else
arr[newInd] = (int)prevValue;
prevValue = temp;
}
}
}
Let me know if anyone find better solution