Solved

Getting original indices of strings after sorting a  char*name

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

Optimize your web performance

What's in the eBook?
- Full list of reasons for poor performance
- Ultimate measures to speed things up
- Primary web monitoring types
- KPIs you should be monitoring in order to increase your ROI

Question has a verified solution.

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

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…
Since upgrading to Office 2013 or higher installing the Smart Indenter addin will fail. This article will explain how to install it so it will work regardless of the Office version installed.
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 …
Six Sigma Control Plans

636 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