473,326 Members | 2,128 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

Algorithm for sorting array of integers w/ respect to another array (c code would be

2
I'm looking for a fast algorithm for sorting an array of integers with respect to a master list.

For example:

Master List: 7 3 9 1 32 6 5 4 99 100 201 13
Array that needs to be sorted array1: 1 5 4 3 6

The "sorted" array would be: 3 1 6 5 4

The order of the array that needs to sorted is originally random. Neither the master list nor the array that needs to be sorted will have repeating elements.

The fastest algorithm I have right now is:
Sort array1 with quicksort (n lg n)
foreach element in master list{
search for it in array1 //(lg n)
if found add to array2
}

array2 has the "sorted" list I am looking for

Unfortunately this gives worst case time n*lg(n) + m*lg(n) where n=number of elements in array 1 and m = number of elements in master list

and m is really big :(
Apr 7 '10 #1
6 3315
Banfa
9,065 Expert Mod 8TB
Either use a single array of structures rather than 2 arrays of int and pass it to qsort or write your own sort algorithm, everytime you perform a swap in array1 do the same swap in array2 and array2 will maintain the correct sorting relative to array1.
Apr 7 '10 #2
newb16
687 512MB
I could not understand this : >The "sorted" array would be: 3 1 6 5 4
What is sort predicate like to get this order for 'sorted' array? If you need to get all numbers from masterlist that are also in A1, in the same order they are in masterlist, just make a hashtable of A1 and check each element of masterlist against it.
Apr 7 '10 #3
donbock
2,426 Expert 2GB
What should happen if the "array to be sorted" contains a value that is not in the master list? I'll assume that this is not allowed ...

Construct an associative array M indexed by the values in the master list where each value in M is the corresponding index into the master list. Unfortunately, C doesn't support associative arrays so you will have to be creative (perhaps a sparse array or a hash).

Create a compare function for quicksort that compares two values in "the array to be sorted" by using those values to index into the associative array M and comparing the values found there.

Constructing the associative array has to be close to O(m), and accessing elements in the associative array has to be close to O(1), for this to be a helpful suggestion. If you can manage that then you can achieve overall efficiency O(m + nlogn).
Apr 7 '10 #4
jkmyoung
2,057 Expert 2GB
Constructing the associative array is O(mlogm) at best, unless you are using bucket sort and m is close to the maximum value for your integers.

You can do no better than your original algorithm since m is not sorted, and does not have an associative array.
If you were to construct an associative array, you would get
m log m + n log m vs
m log n + n log n

which is worse by more than a factor of log m/log n (since the constant for sorting is bigger than searching)

It may be worthwhile to create a sorted associative array if you intend on doing this task with different arrays, as you would only have to pay the O(m log m) cost once.
Apr 7 '10 #5
tc18a
2
I figured out n lg(n) algorithm;

I created a new array called location[].
While I am creating my master list, I store the location of each data value into location. For example, if in the master list 5 is in location 10, I do location[5] = 10. Now I have a way of looking up the location of any data value in constant time.

I then did a qsort(array1, length of array1, sizeof(int), compare);

Where compare is:
{
return location[a] - location[b]
}

qsort here gives n log n (array1 is pretty random and has unique values) and no dependency on M anymore. :)

Thanks for all the responses!
Apr 7 '10 #6
jkmyoung
2,057 Expert 2GB
I assume there was another restriction we were not told of, such as the master list contains all the numbers from 1 to n. Then the associative array is made in O(m) time.
Apr 8 '10 #7

Sign in to post your reply or Sign up for a free account.

Similar topics

1
by: Tek9_AK | last post by:
I need to find a way to transfer all the values of an array inside a function out of the fuction into another array. IE function splice($filename){ if(file_exists($filename)){...
47
by: VK | last post by:
Or why I just did myArray = "Computers" but myArray.length is showing 0. What a hey? There is a new trend to treat arrays and hashes as they were some variations of the same thing. But they...
35
by: VK | last post by:
Whatever you wanted to know about it but always were affraid to ask. <http://www.geocities.com/schools_ring/ArrayAndHash.html>
4
by: joestevens232 | last post by:
I am wring a program where you accept a sequence of integers as input and then print every integer exactly once...you can assume there are no more than 20 integers in the input bt there may be less....
8
by: per9000 | last post by:
Hi all, I have a two-dimensional array of data, f.x int's. We can imagine that the array is "really large". Now I want the data in it and store this in a one-dimensional array. The obvious...
1
by: gr8gatzb | last post by:
I have 2 arrays that are related. The first array is an array of distances from a certain spot. The second array is an array of city names. They are related in that the order of the distances array...
2
by: David | last post by:
Hey can anyone help me convert a javascript array into a ruby array. Ive been struggling with this since friday to no avail. This is the function with the ajax.request call that is supposed to...
13
by: tekinalp67 | last post by:
hi, i am trying to implement a B+ tree. There is no specification in the implementation so i am using arrays to implement the B+ tree. However, there is a problem that i encountered which is I...
9
by: manojrana | last post by:
Can we store an array within another array in javascript var locat = new Array(); var element = new Array(); locat = element; or Can we use like this locat = "manoj";
0
emaghero
by: emaghero | last post by:
I am trying to use the attached header file, which provides me with a generic way of declarating arrays and matrices of arbitrary size. I would like to be able to use the classes Array and Matrix...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.