Computer Science Canada

Sorting array into an index array?

Author:  Homer_simpson [ Wed Mar 03, 2004 7:00 pm ]
Post subject:  Sorting array into an index array?

ok let's say i got this array of decimal numbers like so:{5.0 , 2.3 , 3.2 , 1.7 }
now i want to have another array of four which contains the sorted out index of the first array like this: { 4 , 2 , 3 , 1 }

so whenever i print array1[array2[from 1 to 4]] i would get the numbers in order...
i have a coupla methods in my mind in how to do it... i was wondering if anybody knew a quick and efficient method...

Author:  wtd [ Wed Mar 03, 2004 7:15 pm ]
Post subject: 

You could use a standard quick sort or such to sort the array, then...

create an array of indexes
for each unique element in the sorted array
for each element in the original array
if the latter equals the former
push the index of the latter onto the end of indexes

code:
# quick example in Ruby

unsorted_array = [2.3, 4.2, 6.5, 1.2]
sorted_array = unsorted_array.sort
indexes = []

sorted_array.uniq.each { |sorted_element|
   unsorted_array.each_with_index { |unsorted_element, index|
      indexes.push(index) if unsorted_element == sorted_element
   }
}

puts indexes.join(", ")


wtf?
i believe that's in basic...
the reason i posted it here was that i'm speaking in general...
i already know bubble sort and linear.. looking for something more efficient...

Author:  shorthair [ Wed Mar 03, 2004 8:04 pm ]
Post subject: 

ruby ive posted in your other forum and PM you , this section is pseudo code ,no set language ,

Author:  wtd [ Wed Mar 03, 2004 8:22 pm ]
Post subject: 

shorthair wrote:
ruby ive posted in your other forum and PM you , this section is pseudo code ,no set language ,


Interesting. I haven't received a private message.

I did in fact offer psuedo-code. I didn't put it into code tags in this case for fear of the layout mangling that's occurred in other threads.

I simply offered some real, working code in addition so that the original poster could see that it works, and possibly play with the code, if he felt like it. It just happens that Ruby is the language I could code it fastest in, and one which I feel is rather expressive.

I don't feel bad for using this forum for tutorials on other languages. Being exposed to other programming languages is a good thing, and no other forum seems appropriate. I like to sharemy knowledge, and frankly, this forum doesn't seem too active otherwise.

If you don't like it, simply don't read the threads. :shrug:

Author:  Homer_simpson [ Thu Mar 04, 2004 11:23 pm ]
Post subject: 

well dude there's no array.sort command in language i'm using...

Author:  Catalyst [ Thu Mar 04, 2004 11:25 pm ]
Post subject: 

all the basic sorting algorithms w/ source

[url]
http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
[/url]

Author:  Dan [ Fri Mar 05, 2004 12:38 pm ]
Post subject: 

Homer_simpson wrote:
well dude there's no array.sort command in language i'm using...


what language are u using? there is an array sort in java (i think thats what u are using from u calling it a method)

Author:  Homer_simpson [ Fri Mar 05, 2004 6:04 pm ]
Post subject: 

THX catalyst awesome sorting methods!!!
and dan... i'm using java how do u use the array sort in java and is it fast?

Author:  Dan [ Fri Mar 05, 2004 6:56 pm ]
Post subject: 

i think so, and i think it is like this:

code:

import java.util.*;

public class temp
{
        public static void main(String args[])
        {
                int mynum[] = {1,2,3,8,7,6,4,3};

                Arrays.sort(mynum);
        }
}



and it is a speed of n*log(n)

Author:  rizzix [ Fri Mar 05, 2004 7:00 pm ]
Post subject: 

speakin of arrays. i think i should metion it here at the least. to improve performance in copying the contents of one array into the other use the optimized system command:
static void System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

Author:  Dan [ Fri Mar 05, 2004 7:09 pm ]
Post subject: 

then i think i will add:


fill(int[] a, int val)


so polep can stop puting in thous for loops to set all the array elements to 1 or w/e Razz

tried doesn't work...

Author:  Homer_simpson [ Fri Mar 05, 2004 8:46 pm ]
Post subject: 

nice nice... veryuseful..
but i still think my sort method is more efficient...

Author:  wtd [ Fri Mar 05, 2004 9:04 pm ]
Post subject: 

Just so I can be the guy to give the C++ example...

Note: The sort algorithm by default sorts in ascending order. If you want descending, just print them out in reverse order, as I hae done (first output is ascending, second is descending).

code:
#include <algorithm>
#include <iostream>

int main()
{
   using namespace std;

   const int LOA = 4;
   double array[LOA] = { 5.0 , 2.3 , 3.2 , 1.7 };
   double sorted[LOA];

   copy(array, array + LOA, sorted);
   sort(sorted, sorted + LOA);
   double * end_of_unique = unique(sorted, sorted + LOA);

   int indexes[LOA];
   int counter = 0;

   for (double * i = sorted; i != end_of_unique; i++)
      for (double * j = array; j < array + LOA; j++)
         if (*i == *j)
            indexes[counter++] = j - array;

   for (int * i = indexes; i < indexes + LOA; i++)
      cout << *i << endl;

   cout << endl;

   for (int * i = indexes + LOA - 1; i >= indexes; i--)
      cout << *i << endl;

   return 0;
}

Author:  Dan [ Fri Mar 05, 2004 10:12 pm ]
Post subject: 

Homer_simpson wrote:
nice nice... veryuseful..
but i still think my sort method is more efficient...


what type of sort u using? i whould have thougth java whould have used very fast sorting for there api thingy

Author:  Homer_simpson [ Sat Mar 06, 2004 12:01 am ]
Post subject: 

fast quick sorting... mixture of quicksorting and insertion sorting... it's pretty damn quick...

Author:  rizzix [ Sat Mar 06, 2004 12:59 am ]
Post subject: 

i think java uses the quick sort.

so far the fastest sort i've come accross is the radix sort.
heh just 2 itterations and its sorted... sweet.

Author:  Homer_simpson [ Sat Mar 06, 2004 1:02 am ]
Post subject: 

nope... my sorting method is even quicker than the raddix 8)

Author:  Homer_simpson [ Sat Mar 06, 2004 1:03 am ]
Post subject: 

Hacker Dan wrote:
then i think i will add:


fill(int[] a, int val)


so polep can stop puting in thous for loops to set all the array elements to 1 or w/e Razz

tried doesn't work...

Author:  Dan [ Sat Mar 06, 2004 3:45 pm ]
Post subject: 

did u do:

Arrays.Fill

or just

Fill


i think youi need the array part on it.


: