I am writing a program about sorting an int array. What I have to do is to just modify the pointer array so that the original content of the array will not be changed. Noted that it is not allowed to creat an new array. So what should I do with the array in the sorting function and in the main function?
I have totally no idea of those complex operators....

Please help. Thank you!
-newbie in C

Recommended Answers

All 7 Replies

are you using a linked list for that int array?

no, just some simple integers, say,int arr={4,2,5,6,1}

just modify the pointer array so that the original content of the array will not be changed.

by this statement I was thinking of dynamically creating the array and linked them together so you can traverse and sort the array by modifying each nodes connection so there won't be a need to change the original values of each node

I had in mind something like this for array creation (note: just an example so it won't compile without errors):

typedef struct _array
{           
    int value;
}array;

/*  to create a linked list */
typedef struct _linked_list
{
    array sample;
    struct _linked_list *next;  
}*linked_list;

linked_list head = NULL;

int main(void){
    linked_list ptr = NULL;
    linked_list temp = NULL;
    int i;
    for (i = 0 ; i<5 ; i++){
    temp = NULL
        if(head == NULL){
            temp = malloc(sizeof(struct _linked_list));
            temp->sample.value = someValue; //get the value
            temp->next = NULL;
            ptr = head;
        }else{
            temp = malloc(sizeof(struct _linked_list));
            temp->sample.value = someValue; //get the value
            temp->next = NULL;
            ptr->next = temp; //link this node toprevious node
            ptr = ptr->next; //move to current node
        }
    }

    /*then implement a sorting algorithm where you manipulate the nodes' connection by changing where a nodes next pointer will connect*/

    return 0;
}

thank you very much, it works using linked list. but one thing, is it really necessary to use linked list in this case? would those pass by value or by reference(i dont actually know) doing the same thing? it will help clearifying my poor concept....

I may be complicating things here but as I understand your original requirements require that the original contents of each index should not be modified. Still the indeces' value will change if we were to use pass by reference or value such as swapping the values of the indeces.

The problem with linked list is it could be overkill to implement as a solution for your problem (e.g. keeping track of the head node), if this is homework you might want to clarify a few things before jumping to coding.

okay, thank you anyway. i will try to reinforce my base.

You have an int array, and you have an array of int pointers? They are the same size, right?

Then it's straight forward:

Before you sort anything, you assign the address of the pointers to each array[index] number, in turn.

In your sorter, you will make all your comparisons using the array of pointers, to reference the ints. Whenever a swap is needed, you don't swap ints, you only swap the pointers addresses.

To print out the original int array, you simply print out the int array - nothing has been moved. To print out the sorted array of int values, you print out the values that are now pointed to be the array of pointers.

This is a similar bit of code, that uses an int array instead of an array of int pointers, but the logic is almost identical:

#include <stdio.h>

void printIt(int *a, int *map, int size, int type);

int main(void) {
   int i, j, temp;
   int a[]={3,8,0,4,1,2,6,9,5,7};
   int map[10];

   //initialize map
   for(i=0;i<10;i++)
      map[i]=i;

   //sort via Substitution sort
   for(i=0;i<10-1;i++) {
      for(j=i+1;j<10;j++) {
         if(a[map[i]] > a[map[j]]) {
            temp = map[i];
            map[i] = map[j];
            map[j] = temp;
         }
      }
   }
   printIt(a, map, 10, 0); //original order
   printIt(a, map, 10, 1); //sorted order
   return 0;
}

void printIt(int *a, int *map, int size, int type) {
   int i;

   if(!type) {
      printf("Original and current actual order in array a[]:\n");
      for(i=0;i<size;i++)
         printf("%2d ", a[i]);
   }
   else {
      printf("array a[] as enumerated with the map array as the index:\n");
      for(i=0;i<size;i++)
         printf("%2d ", a[map[i]]);
   }
   printf("\n\n");
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.