Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Getting original indices of strings after sorting a  char*name

Posted on 2003-11-26
3
Medium Priority
?
325 Views
Last Modified: 2011-08-18
hi all,

const char* name[max];

i have some strings in name like some names.

i use some sort technique to sort strings in name.after sorting if i need to know the original position of the strings before sorting, how can i do it.

eg:

name= abc,dba,mba,ccb;
sorted name = abc,ccb,dba,mba;

previously mba was at position 3 bur after sorting at 4. so how to get the original positions of the strings.

Thanks and regards
aravind



0
Comment
Question by:garavindbabu
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
3 Comments
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9823707
Hi garavindbabu,

> after sorting if i need to know the original position of the strings before
> sorting, how can i do it
there is no way to do it after you have sorted unless you keep a copy of the original data structure or an index of the form (previus position - string name) ... clearly keeping a copy of the original data structure is more efficient ...

alternatively, you can define a struct like

struct a
{
    char * name;
    int old_pos;
};

and use an array of this struct

struct a b[max];

while you are sorting, save the original indices

Cheers!
Sunny:o)
0
 
LVL 2

Author Comment

by:garavindbabu
ID: 9823743
hi sunny,

can u be more specific.i understand u r concept ,but i could not implement it.can u write some sample code for it.

Thanks for help.
aravind
0
 
LVL 11

Accepted Solution

by:
bcladd earned 500 total points
ID: 9824146
I think sunnycoder has a good basic concept but I think there is an easier data structure to keep track of it.

garavindbabu: I am assuming that you wrote the sort routine and have access to the swap function/commands (we're going to have to do some other work in the swap)

Before you sort, set up a vector (array) of integers, one entry for each entry in the name. Fill each position with its index:

vector<int> initialPositions;
for (int i = 0; i < numberOfNames; ++i) {
    initialPositions.push_back(i);
}

(or, for an array:
int initialPositions[MAXIMUM_NUMBER_OF_NAMES];
for (int i = 0; i < numberOfNames; ++i) {
    initialPositions[i] = i;
}

...)

Now, when you sort your names you have a spot where you swap two names, something like this:

temp = name[i];
name[i] = name[j];
name[j] = temp;

right? (or a direct call to the swap function).

Add three lines after that to swap the same elements in the initialPositions vector:

int tempI = initialPositions[i];
intiialPositions[i] = initialPositions[j];
initialPositions[j] = tempI;

After the sort initialPositions[k] contains the initial position of the name that ended up in position k.

Hope this helps, -bcl
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Q&A with Course Creator, Mark Lassoff, on the importance of HTML5 in the career of a modern-day developer.
The SignAloud Glove is capable of translating American Sign Language signs into text and audio.
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …

715 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question