help with : sorting elements of array while preserving its index numbers

[AnjaliAnuradha]

I am having problem with sorting and need help with it.
I have to sort the integers in an array and finally after sorting the index number of all the elements before sorting are to be preserved.

I have used merge sort. The sorting is done but the index numbers are not preserved. This is the code I have used for merge sort:

#include <stdlib.h>
#include <stdio.h>

#define NUM_ITEMS 9

void mergeSort(int numbers[], int temp[], int array_size);
void m_sort(int numbers[], int temp[], int left, int right);
void merge(int numbers[], int temp[], int left, int mid, int right);

int numbers[]={1,3, 5, 7, 9, 2, 4, 8, 10};
int temp[9];


int main()
{
  int i;
  

  //seed random number generator
  //srand(getpid());

  //fill array with random integers
 //for (i = 0; i < NUM_ITEMS; i++)
   // numbers[i] = rand();

  //perform merge sort on array
  mergeSort(numbers, temp, NUM_ITEMS);

  printf("Done with sort.\n");

  for (i = 0; i < NUM_ITEMS; i++)
    printf("%i\n", numbers[i]);
}


void mergeSort(int numbers[], int temp[], int array_size)
{
  m_sort(numbers, temp, 0, array_size - 1);
}



void m_sort(int numbers[], int temp[], int left, int right)
{
  int mid;

  if (right > left)
  {
    mid = (right + left) / 2;
    m_sort(numbers, temp, left, mid);
    m_sort(numbers, temp, mid+1, right);

    merge(numbers, temp, left, mid+1, right);
  }
}


void merge(int numbers[], int temp[], int left, int mid, int right)
{
  int i, left_end, num_elements, tmp_pos;

  left_end = mid - 1;
  tmp_pos = left;
  num_elements = right - left + 1;

  while ((left <= left_end) && (mid <= right))
  {
    if (numbers <= numbers[mid])
    {
      temp[tmp_pos] = numbers;
      tmp_pos = tmp_pos + 1;
      left = left +1;
    }
    else
    {
      temp[tmp_pos] = numbers[mid];
      tmp_pos = tmp_pos + 1;
      mid = mid + 1;
    }
  }

  while (left <= left_end)
  {
    temp[tmp_pos] = numbers;
    left = left + 1;
    tmp_pos = tmp_pos + 1;
  }
  while (mid <= right)
  {
    temp[tmp_pos] = numbers[mid];
    mid = mid + 1;
    tmp_pos = tmp_pos + 1;
  }

  for (i=0; i <= num_elements; i++)
  {
    numbers = temp;
    right = right - 1;
  }
}

Please help me to modify this code or write another code so that I could also preserve the index numbers of the unsorted array, even after sorting.

[Prabakar]

I am preety lazy to use merge sort. The trick is to have an array of index which originally has numbers from 1 to n. and sort it along with the array. Here is a simple code.

#include<iostream>
using namespace std ;
int main ( )
{
    int a[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 } ;
    int index[11] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
    int i, j; 

    for ( i=0; i<10 ;i++ )
        for ( j = i+1 ; j < 11 ;j++ )
            if( a[i] > a[j] ) 
            {
                a[i] = a[i]+a[j] ; index[i] = index[i]+index[j] ;
                a[j] = a[i]-a[j] ; index[j] = index[i]-index[j] ;
                a[i] = a[i]-a[j] ; index[i] = index[i]-index[j] ;
            } 
     for ( i = 0 ; i < 11 ; i++ )
         cout << i+1 << "." << a[i] << " " << index[i] << endl ;
     getchar ( ) ;
}

[AnjaliAnuradha]

Thanks a lot,
But what changes should be made to that code to sort the numbers in descending order.....

[Alex Edwards]

I am preety lazy to use merge sort. The trick is to have an array of index which originally has numbers from 1 to n. and sort it along with the array. Here is a simple code.

#include<iostream>
using namespace std ;
int main ( )
{
    int a[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 } ;
    int index[11] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
    int i, j; 

    for ( i=0; i<10 ;i++ )
        for ( j = i+1 ; j < 11 ;j++ )
            if( a[i] > a[j] ) 
            {
                a[i] = a[i]+a[j] ; index[i] = index[i]+index[j] ;
                a[j] = a[i]-a[j] ; index[j] = index[i]-index[j] ;
                a[i] = a[i]-a[j] ; index[i] = index[i]-index[j] ;
            } 
     for ( i = 0 ; i < 11 ; i++ )
         cout << i+1 << "." << a[i] << " " << index[i] << endl ;
     getchar ( ) ;
}

end quote.

That seems like the hard way of doing it...

Why not simply make an array of nodes and sort the nodes by their value while incrementing their index at creation time?

Then when sorted, their natural index will always be retained.

[AnjaliAnuradha]

Thankyou for your suggesion. But The previous code also worked well. I just want to know how the code should be modified to get decreasing order. Please help me.

[Prabakar]

Now, Did you really code that merge sort program? And is it really working?

Alex suggestion was correct, I just wanted to show the calculation part. The code I wrote would have worked well, but its not practical, as he said you should increment the index at creation time.

I think to sort the other way is very very very difficult. Its too complex that I just cant help you:(

[mitrmkar]

I just want to know how the code should be modified to get decreasing order. Please help me.

You need to study the impact of if( a[i] > a[j] ) statement.

With regard to the merge sort code you posted, if you can compile it without errors, then get yourself another compiler. Otherwise, you can get a fresh compilable copy of it from ...
http://linux.wku.edu/~lamonml/algor/sort/merge.html