LiamCormacGould

So I have been banging my head off this problem and could do with some help please folks.

I need to sort a list in a specific way for a buffer shuffler type thing I am building. The list is the order the slices are played and it gradually sorts itself each play through. I have already implemented one sorting method involving randomness but was looking to try and achieve the sorting method below (mainly because I think it will sound good):

For argument's sake 'list A' is '0 4 1 3 5 7 6 2':

1. Hold the items that are in their correct index (0, 3 and 6 in the initial example).

2. Decrease/increase the first incorrect number in steps of one (if higher than index decrease, if lower increase, for example 5 would be decreased).

3. Repeat 2. to avoid duplicates in the list.

4. Stop when not a duplicate and do the same for the next incorrect number.

5. play buffer slices in that order (I have got this part down)

This method seemed to involve looping and wrecked my head a bit with stack overflows and the like so:

1. Store the incorrect indexes in 'list B' (in this example '4 1 5 7 2')

2. Replace the first incorrect index of 'list A' with the nearest number in list 'B'. If the number was higher than its index choose the nearest lower number, if lower the nearest higher number. For example, 4 in 'list A' would change to 2.

3. Remove the replacement number from the 'list B'

4. Repeat for each remaining incorrect index

My attempt at doing this seems almost as horribly convoluted as this explanation and I think I need a fresh approach. Any thoughts on how to achieve either of these methods would be veryverymucho appreciated.

1. Hold the items that are in their correct index (0, 3 and 6 in the initial example).
2. Decrease/increase the first incorrect number in steps of one (if higher than index decrease, if lower increase, for example 5 would be decreased).
3. Repeat 2. to avoid duplicates in the list.
4. Stop when not a duplicate and do the same for the next incorrect number.
5. play buffer slices in that order (I have got this part down)
6. repeat for new list

Alternatively, I tried to:
1. Store the incorrect indexes in 'list B' (in this example '4 1 5 7 2')
2. Replace the first incorrect index of 'list A' with the nearest number in list 'B'. If the number was higher than its index choose the nearest lower number, if lower the nearest higher number. For example, 4 in 'list A' would change to 2.
3. Remove the replacement number from the 'list B'
4. Repeat for each remaining incorrect index
5. play buffer slices in that order
6. repeat for new list

My attempt at doing this seems almost as horribly convoluted as this explanation and I think I need a fresh approach. Any thoughts on how to achieve either of these methods would be veryverymucho appreciated.
Cormac


conundrumed-and-listless-list-sorting-finding-closest-match-above-or-below

You say to increment in steps of +1 or -1 for each value that doesn't match the index.. and to avoid duplicates. How is that possible processing each element serially? Either you are going to correct each element eventually resulting in a duplicate list value before moving onto the next element or you are going to avoid duplicating an existing list value and move on to the next element before it is corrected.

If you increment in parallel, then then entire list becomes 0 1 2 3 4 5 6 7 after five iterations.

What precisely do you want 0 4 1 3 5 7 6 2 to become after it's processed?

No example if an ideal input and output? 

You say to increment in steps of +1 or -1 for each value that doesn't match the index.. and to avoid duplicates.  How is that possible processing each element serially?  Either you are going to correct each element eventually resulting in a duplicate list value before moving onto the next element or you are going to avoid duplicating an existing list value and move on to the next element before it is corrected.    

If you increment in parallel, then then entire list becomes  0 1 2 3 4 5 6 7 after five iterations.

What precisely do you want 0 4 1 3 5 7 6 2 to become after it's processed?


Thank you for the reply it is helping me think through the problem.

The input is always a list of length x that contains all the numbers from 0 - x-1 in some order (x is limited to 2 - 2048). The output should preferably be a slightly more sorted version with correct indexes held in place and incorrect ones inc/dec closer to their index. However, I can see the problem with the adding and subtracting one and the duplicates this will create and might settle for duplicates with this method...

When you say increment in parallel what does this mean?

The efficiency, how many iterations before there is a 'sorted' list, is not really an issue. I want to listen to the process and each iteration.

The second method above where the incorrect indexes are separated and reinserted should provide an output of something like:

0 4 1 3 5 7 6 2 incorrect index values: 4 1 5 7 2

0 2 4 3 1 5 6 7 incorrect index values: 2 4 1

0 1 2 3 4 5 6 7 incorrect index values: None

When you say increment in parallel what does this mean?
The efficiency, how many iterations before there is a 'sorted' list, is not really an issue. I want to listen to the process and each iteration. 

0 4 1 3 5 7 6 2 incorrect index values: 4 1 5 7 2
0 2 4 3 1 5 6 7 incorrect index values: 2 4 1
0 1 2 3 4 5 6 7 incorrect index values: None

I wouldn't really know how to implement that kind of iteration in Max (or anywhere else really) but perhaps looking at "real" sorting algorithms and how they work, might give you a place to start.

I would also suspect that the 'sound' of the sorting algorithm would be quite prominent.

http://en.wikipedia.org/wiki/Sorting_algorithm

I wouldn't really know how to implement that kind of iteration in Max (or anywhere else really) but perhaps looking at "real" sorting algorithms and how they work, might give you a place to start. 

http://en.wikipedia.org/wiki/Comb_sort
http://en.wikipedia.org/wiki/Quicksort

http://en.wikipedia.org/wiki/Sorting_algorithm


Sounds rather like a single iteration of the bubble sort algorithm.

Hey Cormac.. just want you to know that I have been messing around with this. It took a bit longer than I thought so I put it down for the evening but it's very doable. I think when you start messing with list elements, indexing and removing processed values from your original list, it's best handled in a collection... so once you process your initial list into a sublist of 'incorrect' values, use coll to store them and then query each element, process it and send it to a final output coll. That will give you more freedom in manipulating individual elements and allow you to easily remove processed elements. It's still a bit complicated, but workable. I will post what I have in the next day or so. I need to work on other stuff right now... that is if I don't get side tracked exploring jit.bsort.. hehe

Hey Cormac.. just want you to know that I have been messing around with this.  It took a bit longer than I thought so I put it down for the evening but it's very doable.  I think when you start messing with list elements, indexing and removing processed values from your original list, it's best handled in a collection...  so once you process your initial list into a sublist of 'incorrect' values, use coll to store them and then query each element, process it and send it to a final output coll.  That will give you more freedom in manipulating individual elements and allow you to easily remove processed elements.  It's still a bit complicated, but workable.   I will post what I have in the next day or so.  I need to work on other stuff right now...  that is if I don't get side tracked exploring jit.bsort.. hehe


@Rodrigo I will be looking into the different sorting algorithms so as to possibly implement some of them in the patch later.

@Peter I am quite intrigued by the jit.bsort option so will have to look into jitter a little bit too. For some reason it didn't occur to me that there would be some jitter options....

In the meantime I have managed to sort this but I am sure my 'algorithm' could be improved or bettered (in terms of the implementation I mean as I am happy with the results it gives).

@Metamax I am still interested in your approach if you get round to completing it.

Here is my implementation (feel free to tell if it bugs out, max list is 2048):

In the meantime I have managed to sort this but I am sure my 'algorithm' could be improved or bettered (in terms of the implementation I mean as I am happy with the results it gives). 

@Metamax I am still interested in your approach if you get round to completing it. 

Here is my implementation (feel free to tell if it bugs out, max list is 2048):


just realised it doesnt work so scratch that ;)

Cormac.. I was very close to a solution to your problem before experiencing an untimely crash.. after which I just didn't have the gumption to mess with it any more. But I did make a patch that performs the more conventional sort that Peter mentioned. You may find it useful.

I also made one that is a kind of hybrid of an insertion sort and bubble sort. I can post that as well if anyone is interested.

Cormac.. I was very close to a solution to your problem before experiencing an untimely crash.. after which I just didn't have the gumption to mess with it any more.  But I did make a patch that performs the more conventional sort that Peter mentioned.  You may find it useful. 

I also made one that is a kind of hybrid of an insertion sort and bubble sort.  I can post that as well if anyone is interested.  

Here's the inc/dec approach and the sort approach. It converges surprisingly quick!

Here's the inc/dec approach and the sort approach.  It converges surprisingly quick!


I actually managed to get the non working method above to work with some exceptions written in although it was a true ball-ache.

@Metamax your solution is bubble sort right? I implemented this with the jit.bsort suggested which is nice and elegant (not sure about efficiency). Good to see a Max version.

@Peter McCulloch thanks for the simple inc/dec approach. I think, since this will take an awfully long time to sort long lists, I might try and implement a way to make the inc/dec a factor of list length. The other method is interesting, not quite what I was trying to do but the more methods to listen to the better! It will go in to my master patch.

Hey Thanks for the interest guys!
I actually managed to get the non working method above to work with some exceptions written in although it was a true ball-ache. 

@Peter McCulloch thanks for the simple inc/dec approach. I think, since this will take an awfully long time to sort long lists, I might try and implement a way to make the inc/dec a factor of list length. The other method is interesting, not quite what I was trying to do but the more methods to listen to the better! It will go in to my master patch.


Peter, I like that inc/dec approach.. sort or not..

Cormac, yes! It's a bubble sort.. at least in effect. Unlike a true bubble sort, my patch doesn't actually stop comparing values at the largest sorted element on the right, so it's not as efficient. It compares them all and just passes over the pairs that are in the right order. But the output is identical to a bubble sort in terms of iteration.

I'm sure jit.bsort is far more efficient.. though it doesn't output increments - just the completed sort.

Cormac, yes!  It's a bubble sort.. at least in effect. Unlike a true bubble sort, my patch doesn't actually stop comparing values at the largest sorted element on the right, so it's not as efficient.  It compares them all and just passes over the pairs that are in the right order.  But the output is identical to a bubble sort in terms of iteration.

Conundrumed and listless - List sorting/ finding closest match above or below