Question

You have an array of elements of type double. It must be sorted, but recently, because of a system glitch, the sorting-in-place mechanism might allow ONE outlier, i.e., your (supposed to be) sorted array might contain one element in a wrong place. The elements in the array are not necessarily distinct. Write a function that takes the pointer to an array and the array’s size (number of elements in the array) as arguments, finds the place the index of the outlier, fixes the array in place (that is puts the outlier to a place it is supposed to be), and returns the old index where the outlier was found. In case there was no outlier, the function should return -1. This is the function’s signature: long long int fix_sorted_array(double* arr, unsigned long n);

Answer 1

Answer:

#include <stdio.h>

int fix_sorted_array(double * arr,unsigned long n){

int i;

int index=-1;

int item;

for(i=1;i<n;i++){

if(arr[i]<arr[i-1]){

index = i;

item = arr[i];

break;

}

}

for(i=index;i>0;i--){

if(arr[i-1]>item){

arr[i] = arr[i-1];

}else{

arr[i] = item;

break;

}

}

return index;

}

void print(double *arr,long s){

int i;

for(i=0;i<s;i++){

printf("%.2f ",arr[i]);

}

printf("\n");

}

int main(void){

double array[7] = {-23.75,20,25.10,-15,37.10,200.12,1000};

printf("array before : ");

print(array,7);

int index = fix_sorted_array(array,7);

printf("\nReturn index : %d\n",index);

printf("array after : ");

print(array,7);

return 0;

}

Explanation:

#include <stdio.h>

int fix_sorted_array(double * arr,unsigned long n){

int i;

int index=-1;

int item;

for(i=1;i<n;i++){

if(arr[i]<arr[i-1]){

index = i;

item = arr[i];

break;

}

}

for(i=index;i>0;i--){

if(arr[i-1]>item){

arr[i] = arr[i-1];

}else{

arr[i] = item;

break;

}

}

return index;

}

void print(double *arr,long s){

int i;

for(i=0;i<s;i++){

printf("%.2f ",arr[i]);

}

printf("\n");

}

int main(void){

double array[7] = {-23.75,20,25.10,-15,37.10,200.12,1000};

printf("array before : ");

print(array,7);

int index = fix_sorted_array(array,7);

printf("\nReturn index : %d\n",index);

printf("array after : ");

print(array,7);

return 0;

}