Ad:

C++ Discussion Thread
Unsolved
Views: 387

Dec 2nd, 2008

Finding Positon of characters

Expand Post »

I want to write a program which take input and save the poistions of the array elements in another array.
let if i enter an array
A[0]= 4
A[1]=1
A[2]=2
A[3]=3
now the output array will hold
1
2
3
0
i-e the posistions of the array elements starting from the smallest number.
As 1 is the smallest number and it is on 1 posistion the output array will hold values like this
B[0]=1 //Posistion of the smallest number
B[1]=2 //Posistion of second smallest number
B[2]=3 //and so on
B[3]=0 //as 4 is on 0 posistion so it will be on this location of out //array.
This is the problem any one to solve it.

Awais Ahmad

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

5 posts
since Nov 2007

Permalink

Dec 2nd, 2008

Re: Finding Positon of characters

It seems as if the simplest way to affect a solution for your scenario would be to implement any of the available sorts, focusing on array index rather than array content.

Ψmon

Reputation Points: 12

Solved Threads: 0

Light Poster

Offline

30 posts
since Mar 2007

Permalink

Dec 2nd, 2008

Re: Finding Positon of characters

That's a better description of the project, but you could have posted it in your original thread.

As I see it the trick is to keep track of the original element indexes after you have sorted the array. I can think of two ways to do that.

First, copy the original array, sort the copied array, then loop through the original array to find the index of the element with the same value as the current element in the sorted array and place it in a third array containing the indexes in the original . Sort of a mapping of values in the sorted array to indexes in the original array.

Second option, create a struct holding the value and the index of each element in the original array, make an array of struct and sort it based on value, then display it using the indexes stored in each struct object.

Lerner

Reputation Points: 718

Solved Threads: 373

Nearly a Posting Maven

Offline

2,253 posts
since Jul 2005

Permalink

Dec 2nd, 2008

Re: Finding Positon of characters

Here's a sample code..The rest is yours..

C++ Syntax (Toggle Plain Text)
void swap(int items[], int i1, int i2)
(
   int t = 0;
   t=items[i1];
   items[i1]=items[i2];
   items[i2]=t;
)
int main()
{
   int n=0,m=0;
   const int s=4;
   int num[s]={4,1,2,3};
   for(;n<s;n++)
      std::cout<<num[n]<<std::endl;
   for(n=s-1;n>0;n--)
      for(m=0;m<n;m++)
         if(num[m]>num[m+1])
            swap(num,m,m+1);
   num[s-1]=0;
   std::cout<<std::endl;
   for(n=0;n<s;n++)
      std::cout<<num[n]<<std::endl;
   return 0;
}
void swap(int items[], int i1, int i2)
(
   int t = 0;
   t=items[i1];
   items[i1]=items[i2];
   items[i2]=t;
)
int main()
{
   int n=0,m=0;
   const int s=4;
   int num[s]={4,1,2,3};
   for(;n<s;n++)
      std::cout<<num[n]<<std::endl;
   for(n=s-1;n>0;n--)
      for(m=0;m<n;m++)
         if(num[m]>num[m+1])
            swap(num,m,m+1);
   num[s-1]=0;
   std::cout<<std::endl;
   for(n=0;n<s;n++)
      std::cout<<num[n]<<std::endl;
   return 0;
}

cikara21

Reputation Points: 47

Solved Threads: 69

Posting Whiz

Offline

340 posts
since Jul 2008

Permalink

Dec 2nd, 2008

Re: Finding Positon of characters

Here's a sample code..The rest is yours..

C++ Syntax (Toggle Plain Text)
void swap(int items[], int i1, int i2)
(
   int t = 0;
   t=items[i1];
   items[i1]=items[i2];
   items[i2]=t;
)
int main()
{
   int n=0,m=0;
   const int s=4;
   int num[s]={4,1,2,3};
   int old[s]={4,1,2,3};
 
   for(;n<s;n++)
      std::cout<<num[n]<<std::endl;
   for(n=s-1;n>0;n--)
      for(m=0;m<n;m++)
         if(num[m]>num[m+1])
            swap(num,m,m+1);
 
   std::cout<<std::endl;
   for(n=0;n<s;n++)
      std::cout<<num[n]<<std::endl;
 
   //...A few aid
   for x=0 to s-1
      for y=0 to s-1
         if num[x] = old[y] then
             the old pos=y
 
   return 0;
 //done
}
void swap(int items[], int i1, int i2)
(
   int t = 0;
   t=items[i1];
   items[i1]=items[i2];
   items[i2]=t;
)
int main()
{
   int n=0,m=0;
   const int s=4;
   int num[s]={4,1,2,3};
   int old[s]={4,1,2,3};

   for(;n<s;n++)
      std::cout<<num[n]<<std::endl;
   for(n=s-1;n>0;n--)
      for(m=0;m<n;m++)
         if(num[m]>num[m+1])
            swap(num,m,m+1);
   
   std::cout<<std::endl;
   for(n=0;n<s;n++)
      std::cout<<num[n]<<std::endl;

   //...A few aid
   for x=0 to s-1
      for y=0 to s-1
         if num[x] = old[y] then
             the old pos=y

   return 0;
 //done
}

Last edited by cikara21; Dec 2nd, 2008 at 3:24 pm. Reason: :)

cikara21

Reputation Points: 47

Solved Threads: 69

Posting Whiz

Offline

340 posts
since Jul 2008

Permalink

Dec 2nd, 2008

Re: Finding Positon of characters

By Just Skimming through your Problem statement one can judge its a sorting problem, what you need to do is to analyze which sort will meets your need, if you've small array and planty of space then the following trivial algorithm will meet your requirements. But this trivial algorithm only requires unique element.

Algorithm.
i) Find the MAX of Input Array in O(n) Time.
ii) Allocate the Large Enough Array and Initialize it with -1.
iii) Loop Through the Input Array and increment the counter of output array positions which equates to input_array value.
iv) Print the Ouput Array (where value is not negative).

again this is a tentative solution, you can think of another, I'll prefer if you check the Thomas H Corman Sorting Techniques, which suites your requirement, if you really want to learn the sorting techniques & mathematically inclined you should check "The Art of Computer Programming" By Knuth.

Laiq Ahmed

Reputation Points: 113

Solved Threads: 20

Junior Poster

Offline

147 posts
since Jun 2006

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: Easy C++ Contest!

Next Thread in C++ Forum Timeline: Using string as char array

DaniWeb Message

Cancel Changes

User Name
Password