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
Medium Priority
325 Views
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
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

LVL 45

Expert Comment

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

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

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

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 …
Suggested Courses
Course of the Month7 days, 21 hours left to enroll