[ProgSoc] Multi-index sorting algorithms

sanguinev at progsoc.org sanguinev at progsoc.org
Tue Dec 21 15:51:50 EST 2010


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 21/12/2010 12:38 PM, James Ducker wrote:
> Putting aside some silly errors in the code I linked, this is an
> interesting problem, though I think I'm onto a solution, which I may
> post later on. Input still encouraged though :)
> 
> - James
> 
> 
> On 21 December 2010 11:57, James Ducker <jducker at it.uts.edu.au> wrote:
>>
>> Hey all,
>> I'm trying to write a sorting algorithm that can sort a set of data
>> (the usual, lowest to highest, A-Z, etc), but when it encounters a tie
>> condition between two values, will defer sorting to another set of
>> data, which I call the "tiebreaker" set. I'm having a diddly of a
>> pickle getting it to sort reliably (recursive quicksorting wasn't
>> working, bubblesorting is working /sort-of/, in that values tend
>> toward the correct position, but are usually off by one or two slots).
>>
>> Anyway, does anyone know of some good multi-index sorting algorithms?
>>
>> - James
>>
>> PS: Here's a link to the current iteration of my code. It's
>> JavaScript, /fairly/ legible though.
>>
>> http://progsoc.pastebin.com/DeZ3Hbnh
>>
>> Also, original, less-concise, quicksort-based attempt:
>> http://progsoc.pastebin.com/GurMaRYb
>>
>> --
>> James Ducker

Depends a little on the language (and I am no expert on javascript), but
in some languages (OCaml, python) you can do very simple comparisons, so
the following pseudocode would work:

for(i = 0;i < array1.length();i++)
  for(j = i+1; j < array1.length();j++)
    if ((array1[i],array2[i]) > (array1[j],array2[j]))
      array1.swap(i,j)
      array2.swap(i,j)

Basically combine the two values into a pair and use the normal
comparison on the pair.

- - SanguineV
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (MingW32)

iQIcBAEBAgAGBQJNEDJlAAoJEI+NvFGSwhPn4VoP/jEd1hSULG8bcLNlNA8ye/zt
LhNj0bGpTShph0eDDh0Fmw9P6srNBeJRVom2ENV5XC2MfV5ubrOixA7CNSQBulkt
wY2uxY5vLujMsJ9qyQb5BVv3gEdorBDWp5dKG7ps0375vhrjtM4mqQm3hAmwKiEc
hfoj4HEx4QBAIgw214ZT7nZbCNw42qE2qx6ei42M74jl0CK46Es4Y21OEehmXxGO
d4hZR5MUkbwXy9L3kvZSjYDBV8Cf9BgbLY+Uh5MoB1DjkDgiYqVe3jOUezhV9ri4
jxm8bJp3XVnLTzGum7E+gu6xbQ9ovQRLxMGhvsrU0usdEpCbuXRJ+iQQCh8D3Iqc
nrlp/kZrSoQxxdXDDN6ziYkLgoIhXZbvlwhf3F1qP65pKIxeiMyMYvCQ4QhR4GIt
kTEiNGfe1iDqo/2w4+mviF/AjwGFS9QthiPpqaDNgXGmja8mTVHwZHcPGxsTdui0
B9gawz2bbeqvpVbGiNBbc4i4r8eGFZZem8QMdyC9pDjoGfLZvudMqxvKWZkMyuno
UiiWJEoHKypMpz9eN/zO/eyNt8pYg8oHB57c7bgsLvIKyeaE/ljdmMMMZ43G2v71
cDxSYbhTD13S0jFHUFvS+45eOD2QsYjsQFxAM3QAuvGATmk7/OndQEr9ghwXK6Jc
0Ta4ZRZ3ppFZkiuPq0Cb
=lySY
-----END PGP SIGNATURE-----



More information about the Progsoc mailing list