[04:03] Join: Metcalf joined #corewars [09:05] MSG: Ping timeout: 245 seconds [09:05] Join: Metcalf joined #corewars [11:09] Join: yoR joined #corewars [11:10] JM: Have you done a Shell sort? (next to the Dobwjbjwble one?) [12:26] Join: fiveop joined #corewars [16:16] MSG: [17:03] MSG: Ping timeout: 245 seconds [17:04] Join: Metcalf joined #corewars [17:11] MSG: Ping timeout: 245 seconds [17:24] Join: yoR joined #corewars [17:43] MSG: Quit: humhum [19:39] Join: Metcalf joined #corewars [19:40] JM! [19:41] evenings etc [19:42] Hi Roy, Mizcu [19:42] Roy, haven't implemented shell sort yet [19:43] I think Dobosiewicz will be more efficient in redcode [19:45] Might be [19:45] I just made my second sorting algorithm, seems to be a LOT better [19:46] Its better then most algorithms actually, except the O(n log n) ones.. [19:46] But its in-place, doesn't use much memory... but still quicksort will always beat it [19:46] Oh, sounds interesting? [19:46] Can I have a hint? [19:47] It works like this: [19:47] I have a few ideas I'll try soon [19:47] Merge sort breaks everything down and rebuilds it, the best algorithm, so I thought 'lets pretend the whole array is already sorted into sublists' [19:48] So basicly my algorithm merges all the little sublists in the list, worst case would be high-low-high-low (shortest lists possible) [19:49] The merging algorithm goes like this: is A>B add one to the 'rotate' variable, A So you look for runs to begin with? [19:50] I made Java applets out of my own sorting algorithms, just the this: http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html [19:51] I'll upload those very soon! [19:52] :-) [19:52] I just made redcode [19:54] Hehe, its a bit code-heavy, even in higher languages [19:55] There's a Shell sort by Brian Haskin in r.g.cw [19:55] For some reason, it's not on Planar's site [19:57] Measuring my sort with a 200000 object random array: Insertion Sort 80sec, My sort: 24sec, Quick+Merge >1sec [19:57] http://www.ociw.edu/~birk/COREWAR/ODD/HILL/seasidesort.red [19:58] Nice improvement [20:02] Hmmm... this is a funny looking Shell sort! [20:08] Does it work (well)? [20:10] Haven't tested it [20:10] I don't know how to construct the worst case for Shell sort [20:10] I'm just about to eat, I'll test it after [20:12] My dobosort = 55000 cycles to sort 500 random [20:20] http://www.redcode.nl/sorting/algorithms.html [20:20] The algorithms... hehe [20:27] Brian's shell sort takes about the same time as my dobosort for the random data [20:28] Nice... now you'll have to calculate the worst case hehe [20:30] That's tricky [20:30] But I think it should be possible to construct the worst case by reversing the sort and scrambling a sorted array! [20:32] "Applet nl.redcode.sorting.SortItem notinited" [20:43] Weird.. works here :( [20:46] I've only tried it in ff [20:47] Works in my ff too hehe [20:52] Join: OoS joined #corewars [20:52] I didn't mean to press that key! [20:54] MSG: Ping timeout: 245 seconds [21:21] MSG: Ping timeout: 245 seconds [21:35] Join: OoS joined #corewars [21:51] MSG: [22:05] MSG: Ping timeout: 245 seconds [22:05] Join: OoS joined #corewars [23:08] argh! the return of add #1, somewhere :-( [23:25] MSG: Ping timeout: 245 seconds [23:29] Join: OoS joined #corewars [23:33] MSG: Ping timeout: 245 seconds