Snipplr - rtperson

(Java) Quicksort in Java, with Enforced Suckitude

Tue, 08 May 2012 00:02:25 GMT

It's no fun implementing QuickSort unless you can force it out of its blister-fast, O(n log n) speed and humiliate it with its worst-case, O(n^2) runtime. So that's what I set out to do. My naive partition simply pivots around the low item, but my randomized partition defeats the sucky inputs by choosing a random pivot. (If you're interested in checking out a QuickSort which naively partitions until it hits an attempt to get it to run in quadratic time, check out IntroSort -- which simply fails over to Merge Sort when it exceeds its optimal recursion depth.)

(Haskell) Haskell 99 Problems, numbers 1 through 9

Thu, 08 Sep 2011 00:23:54 GMT

I had originally started these problems from #10 (Run-length encoding). I went back and did 1-8 for completeness.

(Haskell) Haskell 99 Problems - Number 20, Arrowed!

Thu, 25 Aug 2011 01:54:30 GMT

problem 20, (*) Remove the K'th element from a list *Main> removeAt 1 "abcd" "acd" Trivial using a pure function. A bit more challenging if you use this problem to work up your Arrow-fu.

(Haskell) Haskell 99 Problems - Number 18 and 19

Sun, 21 Aug 2011 01:58:02 GMT

Problem 18: Extract a slice from a list. Given two indices, i and k, the slice is the list containing the elements between the i'th and k'th element of the original list (both limits included). Start counting the elements with 1. Example: *Main> slice ['a','b','c','d','e','f','g','h','i','k'] 3 7 "cdefg 9 Problem 19 - Rotate a list N places to the left. *Main> rotate ['a','b','c','d','e','f','g','h'] 3 "defghabc" *Main> rotate ['a','b','c','d','e','f','g','h'] (-2) "ghabcdef" (This one is so easy it feels like cheating...)

(Haskell) Haskell 99 Problems - Solutions to 11 and 12

Fri, 29 Jul 2011 08:03:55 GMT

problem 11, modified run-length encoding ======================================== If an element has no duplicates, mark it as such. Example: encodeModified "aaaabccaadeeee" [Multiple 4 'a',Single 'b',Multiple 2 'c', Multiple 2 'a',Single 'd',Multiple 4 'e'] problem 12, Decode a run-length encoded list. ============================================= Given a run-length code list generated as specified in problem 11. Construct its uncompressed version. Example: decodeModified [Multiple 4 'a',Single 'b',Multiple 2 'c', Multiple 2 'a',Single 'd',Multiple 4 'e'] "aaaabccaadeeee"

(Haskell) Run-Length Encoding in Haskell

Fri, 29 Jul 2011 06:08:49 GMT

Problem 10 of the famous 99 Problems. I got 99 problems, but a Lisp ain't one.

(Haskell) Euler Problem 4 in Haskell

Wed, 01 Jun 2011 00:11:10 GMT

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 * 99. Find the largest palindrome made from the product of two 3-digit numbers. There are shorter ways to do this, and I cheat a bit by counting down to 900 rather than 100, but this one short-circuits when it finds the answer, and so is very efficient.