Solved

Getting original indices of strings after sorting a  char*name

Posted on 2003-11-26
3
288 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
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 125 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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

This article will show, step by step, how to integrate R code into a R Sweave document
Entering a date in Microsoft Access can be tricky. A typo can cause month and day to be shuffled, entering the day only causes an error, as does entering, say, day 31 in June. This article shows how an inputmask supported by code can help the user a…
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
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 …

920 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

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now