Solved

Getting original indices of strings after sorting a  char*name

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

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

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
This is an explanation of a simple data model to help parse a JSON feed
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

821 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