ACM 2002(?) Silly Sort...

All things techie, be they discussions on troubleshooting, video encoding, programming, or algorithm design.

Moderator: Nuxius

ACM 2002(?) Silly Sort...

Postby Gigafrost » Sat Apr 12, 2003 4:26 am

Basically, in Computer Science, when you're sorting something you want to do it as fast as possible, however this is assuming that "swapping" to items doesn't matter. Now, the challenge of this assignment is\was to make a sorting algorithm with the smallest cost possible. In this case, the cost is simple to find. Just add the values of the two items swapped together and voila! So, when you sort, you've got to add the costs up, and your goal is to sort it with the lowest cost possible.

EXAMPLE:
8 1 2 4 (cost for swapping goes here)
1 8 2 4 (9)
1 2 8 4 (10)
1 2 4 8 (12)
Total cost: 31

Now, how would you go about sorting something in the least cost possible? In the given case, let's set it as established that the minimum is 17, alright? How would you do that? Well...

8 1 2 4
8 2 1 4 (3)
8 2 4 1 (5)
1 2 4 8 (9)
Total cost: 17

Okay, so you can see that it was done, but what does it mean? Well, notice that the method was actually pretty simple...find the smallest, find what should be in the place it is, and swap them! This is the core idea behind my solution, although it isn't complete. Let me show:

1 8 9 7 6

Well, now what do we do? The smallest is already in place, right? Well, maybe if we switch the smallest one with the smallest one that's out of place (in this case, the 6) and proceed as normal...

1 8 9 7 6
6 8 9 7 1 (7)
6 8 1 7 9 (10)
6 8 7 1 9 (8)
6 1 7 8 9 (9)
1 6 7 8 9 (7)
Total cost: 31

In this case, 31 is the smallest, so this looks like the solution to our problem, right? But wait! What if I had the same ordering that the previous one did, but I used smaller numbers?

1 4 5 3 2
2 4 5 3 1 (3)
2 4 1 3 5 (6)
2 4 3 1 5 (4)
2 1 3 4 5 (5)
1 2 3 4 5 (3)
Total cost: 21

But, what if I told you that this is not the minimum...that the minimum is actually 18? Well then, there's obviously another case to consider. In fact, the minimum for that one is actually done by using the smallest element that's out of place. What does this mean? Well, if you think about it, how are using the two different? Obviously, all the other elements don't matter since they'll be swapped anyways, so maybe there's a way to mathematically determine which one would be more efficient to use? Well, i found there is a way to roughly determine, however it's possible it could fail...hehehe.

Notice how if you use the 2 (the smallest out of place in the above example) then what will happen is the 2 will be swapped with 3 elements. Well, there are 4 elements out of place, so the expected cost for using the 2 would be...

2 * (4 - 1) = 6

or rather...

(smallest piece out of order) * (unsorted elements - 1) = cost #1

something similar would happen if we switched the 1 with the 2, though. First, we observer that the 1 would be swapped with those same 3 elements, but it will be swapped with the smallest out-of-order one twice! So, the cost for doing that would actually be the sum of those two...

(1 + 2) * 2 + 1 * (4 - 1) = 6 + 3 = 9

or rather...
(smallest + smallest out of order) * 2 + (smallest) * (unsorted elements - 1) = cost #2

Well, now it's a simple matter of choosing the smaller of the two!

So, pretty much this narrows down most cases. There might still exist cases that slip by this method, though. There's one that can slip by if programmed oddly. Take this example:

2 5 3 3 4

Well, notice that there are two 3s. Also notice that one of them is already in place. It'd be very easy to accidently move around that one that's already in place, but that'd be silly to do! It'll result in unneccessary moves! Basically, the way I got around that is that I calculate in advanced where everything is supposed to go and I make sure that the specific 3 is identified as "in place." Then, instead of looking for the smallest out-of-order item by the value in the spot, i can search based upon the previously calculated index! It works. ;)

Alrighty, now I'm done. I hope this psyche poke wasn't too painful. :p :evil:
User avatar
Gigafrost
Frost Weapon
Frost Weapon
 
Posts: 4900
Joined: Wed Dec 04, 2002 5:09 pm
Location: Here

Postby Gigafrost » Mon Apr 14, 2003 10:38 am

Well, the project was due 5 to 6 hours ago, so now I guess I'll post the code! :)

It's in JAVA, so there's not going to be any help from me to run it. Also, the algorithm I'm posting is quadratic...which is your slower sort...and I've thought about it some and I think I can improve it and make it O(N log N) ... maybe I'll do that just for fun sometime...hehehe...there's just the big problem of finding the smallest element...hmmm...
Attachments
SillySort.zip
(3.03 KiB) Downloaded 601 times
User avatar
Gigafrost
Frost Weapon
Frost Weapon
 
Posts: 4900
Joined: Wed Dec 04, 2002 5:09 pm
Location: Here

Postby Nyufrost » Mon Apr 14, 2003 12:02 pm

Well, as you know, I was replying to this the other night when I clicked on some link on AIM and my browser crashed so I never got a chance to .... uh .... this sounds like a "the dog ate my homework" excuse ... :oops:

Anyways, I was really impressed with SillySort and --though it's most obvious appeal to me was the cutesy name-- thought it was really neat that it could figure out such things ... and that you could write such stuff. ^_^

Though you explained to me what it does and how it works ... where would someone use something like this? Yes, that's a dumb question but I don't understand ... it's not a stand-alone program but a script add-on thingy, right?

So, what would JoeBob Retailer *do* with it to make it work for him?

Gigafrost19: feel free to take a look at the source...if you dare! bwahahahahaha!

Heh ... :p I don't know that much about codes but it *looks* really impressive. :oops:
<BR><center> "Snowflakes are one of nature's most fragile things, but just look <br> what they can do when they stick together.." ... Vesta M. Kelly</center>
User avatar
Nyufrost
Frost Advisor
Frost Advisor
 
Posts: 5534
Joined: Wed Dec 04, 2002 7:03 am
Location: Out There

Postby Gigafrost » Mon Apr 14, 2003 2:21 pm

Nyufrost wrote:Well, as you know, I was replying to this the other night when I clicked on some link on AIM and my browser crashed so I never got a chance to .... uh .... this sounds like a "the dog ate my homework" excuse ... :oops:

Ah hah! A confession?
Forget about it... :MIB :)

Anyways, I was really impressed with SillySort and --though it's most obvious appeal to me was the cutesy name-- thought it was really neat that it could figure out such things ... and that you could write such stuff. ^_^

Mostly, it's not that the program itself is terribly smart. Actually, I finally came up with an example which my program doesn't do correctly...it's not quite "smart enough" to handle that...but I know how to fix it to do that...and that's pretty much what programming things like this is about! ^.^;;

Though you explained to me what it does and how it works ... where would someone use something like this? Yes, that's a dumb question but I don't understand ... it's not a stand-alone program but a script add-on thingy, right?

Pretty much, anything written in JAVA isn't a stand-alone program, but, yeah, it's supposed to be an add-on. A more ideal use of this program would be to "record" how it got the results, since that would be more useful information, but that's a minor change that can be done by any semi-skilled programmer. :)

So, what would JoeBob Retailer *do* with it to make it work for him?

Well, he'd need software that uses it, and it'd be best to get a program that does it for him or get somebody to make a program that does it for him. Then, when he'd feed the information into the computer and read the results, using the results to form a "plan" for making things work.

Gigafrost19: feel free to take a look at the source...if you dare! bwahahahahaha!

Heh ... :p I don't know that much about codes but it *looks* really impressive. :oops:

Yeah, it would...any complex code ends up looking impressive...given it's nice and tidy...


Anywho, I was thinking about it alot this morning and I'm 100% sure I can fix the algorithm to work for every case and to work in N log N time...maybe I'll just put the changes here...

1) Instead of using the findSmallest() method I can use the findSpot() method, looking for the item with index "a"...this would be equivalent to finding the smallest element... (this is first because it's very easy to do)

2) Fix the algorithm by "tracing" what swaps will happen where. Another array will be needed to store this information, though. This will allow me to find the exact number of swaps that will get the "current" into position, fixing the case where it doesn't work. The information will be stored so that the calculations will only need to be done once.

3) Modify the order() method to use heapSort instead of insertionSort as its ordering type...heapSort is a guaranteed O(N log N) sort, and this is the first step into turning the algorithm into an O(N log N) sort.

4) Modify the order() method to return a binary search tree instead of an array. If done properly, the lookup speed of findSpot() can be increased to O(log N) and this will be the most important part of achieving N log N efficiency.

5) Modify the findSpot() method to properly read the binary search tree.

6) Create a new method to fix the binary search tree after a swap occurs.

Note to self: It might be the case where I still will need an array to hold the indices...I'll have to think about that some more...
User avatar
Gigafrost
Frost Weapon
Frost Weapon
 
Posts: 4900
Joined: Wed Dec 04, 2002 5:09 pm
Location: Here

Re: ACM 2002(?) Silly Sort...

Postby Gigafrost » Tue Apr 05, 2011 12:40 am

Old topic is old.

Recently re-implemented this algorithm.

http://www.kraftfam.org/~erk/cs/SillySort.zip
User avatar
Gigafrost
Frost Weapon
Frost Weapon
 
Posts: 4900
Joined: Wed Dec 04, 2002 5:09 pm
Location: Here


Return to Communications Center

Who is online

Users browsing this forum: No registered users and 2 guests

cron