Quick sort with index array

Question

1.00/5 (1 vote)

See more:

Hi,

I need a quicksort algorithm implementation which gives the original indices of the elements, before sorting, also.

ie,

Before sorting

index : 0 1 2 3 4 5
values: 70 60 40 20 30 50

After sorting

index : 3 4 2 5 1 0
values: 20 30 40 50 60 70

Posted 2-May-13 0:35am

Vineeth.B

Updated 2-May-13 0:43am

pasztorpisti

v2

Add a Solution

Comments

OriginalGriff 2-May-13 6:41am

And?
What have you tried?
Where are you stuck?

2 solutions

Solution 1

Hi
I would suggest to use a structure with value and its initial location and its array for the operation.
Then using algoritm swap the structure in the array.

Posted 2-May-13 0:45am

Vipin Kumar Mallaya G

Comments

Kenneth Haugland 2-May-13 6:49am

Why are you reposting this? 3 times?!?

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CPallini · Accepted Answer · 2013-05-02T00:49:00

Solution 4

You don't need a fresh quicksort implementation, you can use qsort as it stands:

store every array item in a struct containing its value and its original index (ending up with an array of such structs)
define your comparison function for taking two of such structs as parameters
use standard qsort for ordering the array of structs.

Posted 2-May-13 0:49am

CPallini

Comments

nv3 2-May-13 8:39am

Definitely the way to do it. Except this is homework and the teacher wants to see the implementation of the quick sort :-) My 5.

CPallini 2-May-13 8:44am

Thank you.