Click here to Skip to main content
14,102,245 members
Rate this:
 
Please Sign up or sign in to vote.
See more:
Hi, I 'm working on this practice problem. In which I am testing my code using bash command with a text file. The file contains numbers the 1st number is the total of rest of the numbers.

For example 1st number as a 4 means there are total 4 numbers in line.

Example array length 8

3

5

6

7

0

4

1

2

Then I have to use merge sort and after that
the output is

First element is at subscript 4

0 3 5

1 5 2

2 6 3

3 7 -1

4 0 6

5 4 1

6 1 7

7 2 0

It works fine for indices column, input column, but not the links. I did my search on links I find out they can be extracted from sort function. Now my question is the mergesort functions I'm using are these proper for this purpose. What is missing?

What I have tried:

#include <stdio.h>
#include <stdlib.h>
#define MAX 50


//Prototypes
int binary(int a[],int n,int m,int l,int u);
void partition(int **arr,int low,int high);
void mergeSort(int arr[],int low,int mid,int high);


int main()
{
    
    //Variable initialization
    int n, j, temp, i=0, low = 0, indx = 0;
    int *index, *input, *link, *sorted;
    
    scanf("%d ",&n);
    
    //Memory allocation
    input = (int*) malloc((n)* sizeof(int));
    index = (int*) malloc((n)* sizeof(int));
    link = (int*) malloc((n)* sizeof(int));
    sorted = (int*) malloc((n)* sizeof(int));
    
    
    //Error handeling
    if(input == NULL)
    {
        printf("Error! memory not allocated.");
        exit(0);
    }
    
    //Input
    for(i= 0; i < n; i++)
    {
        scanf("%d",&input[i]);
        index[i]=i;
        sorted[i]=input[i];
        link[i]=-1;
        
    }
    
    partition(&sorted,0,n-1);
    
    // Finding minimum value
    low=sorted[0];
    for(i=0;i<n;i++){
        if(input[i]==low)
        {
            indx=i;
        }
    }
    
    //Binary search
    for(i=0;i<n;i++){
        temp= input[i];
        for(j=0;j<n;j++){
            if(sorted[j]==temp){
                link[i]=j+1;
                printf("print link j+i %d\n", link[j]);
                if(link[i]==input[i]){
                    
                    
                }
            }
        }
    }
    
    
    // Printing output
    printf("First element is at the subscript %d \n", indx);
    for(i=0;i<n;i++){
        printf(" %d  %d %d \n",index[i],input[i],link[i]);
        
    }
    /*
     for(i=0;i<n;i++)
     {
     printf("%d ",sorted[i]);
     }*/
    //Memory deallocation
    free(index);
    free(input);
    free(link);
    
    
    return 0;
    
}

void partition(int **arr,int low,int high){
    
    int mid;
    
    if(low<high){
        mid=(low+high)/2;
        partition(arr,low,mid);
        partition(arr,mid+1,high);
        mergeSort(*arr,low,mid,high);
    }
}

void mergeSort(int arr[],int low,int mid,int high){
    
    int i,m,k,l,temp[MAX];
    
    l=low;
    i=low;
    m=mid+1;
    
    while((l<=mid)&&(m<=high)){
        
        if(arr[l]<=arr[m]){
            temp[i]=arr[l];
            l++;
        }
        else{
            temp[i]=arr[m];
            m++;
        }
        i++;
    }
    
    if(l>mid){
        for(k=m;k<=high;k++){
            temp[i]=arr[k];
            i++;
        }
    }
    else{
        for(k=l;k<=mid;k++){
            temp[i]=arr[k];
            i++;
        }
    }
    
    for(k=low;k<=high;k++){
        arr[k]=temp[k];
    }
}
Posted
Updated 24-Jun-17 6:48am
v2

1 solution

Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 1

There is a tool that allow you to see what your code is doing, its name is debugger. It is also a great learning tool because it show you reality and you can see which expectation match reality.
When you don't understand what your code is doing or why it does what it does, the answer is debugger.
Use the debugger to see what your code is doing. Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug.
   
Comments
Member 13277005 24-Jun-17 12:53pm
   
I believe I'm still not clear on the concept of links once I know how it's working. I will be fine. If you can help me with the logic how it's breaking down and merging back in such sequence.
Patrice T 24-Jun-17 12:59pm
   
What is supposed to be a link for you.
Member 13277005 24-Jun-17 13:03pm
   
a pointer.
Patrice T 24-Jun-17 13:09pm
   
Are you sure the size of a pointer is same as an integer ?
Member 13277005 24-Jun-17 13:13pm
   
If an int pointer is pointing at the same int variable then size should be same.
Patrice T 24-Jun-17 13:19pm
   
link is a pointer to an array of ints, not to an array of pointers.
Member 13277005 24-Jun-17 13:28pm
   
My link pointer is populated with input array values then set to -1.
What I'm understanding form your explanation. It should point to input array, I thought my method was doing the same thing.
Member 13277005 24-Jun-17 13:34pm
   
How these numbers are being generated for links.
Patrice T 24-Jun-17 13:56pm
   
I see link is not a pointer, it contain only the original position of the number in input.
Member 13277005 24-Jun-17 14:17pm
   
so the link I have changed to a pointer
int *link: *input=NULL;
link=&input[i];
rest is same my output is still same.
Patrice T 24-Jun-17 14:28pm
   
Give try to debugger
Member 13277005 24-Jun-17 14:36pm
   
I'm debugging it in Xcode.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy | Cookies | Terms of Service
Web05 | 2.8.190518.1 | Last Updated 24 Jun 2017
Copyright © CodeProject, 1999-2019
All Rights Reserved.
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100