Tag Archives: Java

Array Sort

Earlier in the week I was working on something completely unrelated to programming (sorting some school work actually) and I had an idea about sorting integers using array indices. I finally got around to implementing and benchmarking it in Java this morning.

The process is fairly simple, though it might be kinda hard to explain. To start with I’m going to describe a simplified version that uses a bit more array space than my optimized version.

Imagine you have an array of integers, something like    int myArray[] = {5,9,3,8,4,10,2,8,6,4};   for example. The first thing the code does is loop through the whole array once to determine the maximum value in the array. In this case that would be max:10. Using this value, we create a second empty array, as follows:    int sorted[] = new int[max+1];   

Here’s where the trick comes in. Rather than using the array itself to sort the data, we use the array’s indices. This means that we now loop through the original myArray and for each value we encounter, we do   sorted[value]++;   

Once we’re done looping through myArray, we’re left with: 

sorted[0]=0    sorted[1]=0    sorted[2]=1    sorted[3]=1    sorted[4]=2

sorted[5]=1    sorted[6]=1    sorted[7]=0    sorted[8]=2    sorted[9]=1    

sorted[10]=1

Since array indices are sorted, all we need to do now is loop through the array one more time and printed out the indices that have non-zero values. If the value is >1, we print out the number that many times. This gives us 2,3,4,4,5,6,8,8,9,10. And look, it’s sorted!

With a small-scale array like this, QuickSort is much faster. However with datasets at around 50,000 or more the “ArraySort” method starts to start looking very nice. I recorded and graphed some running times at intervals of 100,000, between 100,000 and 3,000,000. Each array contains n elements generated by a for loop, with each element being set to:  (int) (Math.random() * 1000000);

 Here’s the resulting graph:

I couldn’t believe the results. I changed the ArraySort program to print out the sorted array at the end of the run, just to make sure it was actually sorting, and it was. I guess the difference here is that 1) ArraySort only uses a constant 3 loops and 2)QuickSort is recursive, so with more things to sort more method calls have to be made.

 I plan on trying this again using C++ instead of Java later today to see how the performance compares.

T


JMorse Part 1 – A Crack at the Rules

As mentioned in my previous post, I decided to actually try going down the route of mixing Morse Code and programming. The first step in doing this was coming up with a few rules to write programs in Morse code. The easiest way to get started was to use standard Morse letter sequences, and then fill in any characters that were missing, e.g. ( ) [ ] { } ; ” “. This gave me:

Morse Code

To make parsing easier/possible, I came up with a few spacing rules as well. A single space, ” “, is used between characters in the same “word”. A double space, ”  “, is used to represent the access operator, in Java’s case this would be the period. Finally, a triple space, ”   “, is used to indicate the gap between two words. If any of that is confusing it’ll make sense in a minute with the code snippet.

To start with, I wrote a very simple and cliche “Hello World” in Java, and then encoded it into Morse. The original program looked like this:

Java Hello World

And encoded in Morse I ended up with this abomination:

Java Morse Code

Two things became clear pretty quickly while writing the above program. The first was that as more non-alphanumeric symbols are needed, the more complex the morse equivalents are going to become. I still need =,+,-,/,*,%, the logical and bitwise operators…To fit them all into the Morse code set I’d probably have to extend out to a length of 6 dot/dashes for some cases. This would become very yucky very fast.

The second problem is Morse doesn’t allow for capital and lower case letters. You more or less have to pick one and stick with it. This is a pretty big problem as I’m a strict follower of camelCase-style naming conventions and Java’s standard libraries are loaded with mixes of upper and lower case. The only solution to this that doesn’t require an additional 26 Morse codes adding a “shift” character that has to be prefixed to any character that needs to be in upper case. That would be a bitch.

So where does this leave us? I can’t help but feel that there’s got to be a better way to go about doing this. I know the original intent was to use strict Morse Code compliant characters to write programs, but retrofitting the necessary characters into the existing codeset is brutal. As I see, there are two options left:

1. Use morse of the letters only, and retain existing “punctuation” using Java’s traditional symbols ()[]{}””,;. etc.

or

2. Start from scratch and design a new variant of Morse Code that’s optimized for programming. Rather than having “e” as “.”, maybe “.” could be the period symbol that it appears to be. And curly braces could be “-.” and “.-“, and so on.

I’ll have to think about this some more, but I think number 1 is looking a bit more appealing. The problem with number 2 is that it feels like I’m just rewriting ASCII, albeit a more reduced version of ASCII. Number 1 retains the Morse Code feel and will require far fewer additions to the original codeset.

That’s all for now though.

T


Sudoku Solver

Earlier this week, I decided to try my hand at writing a solver for classic Sudoku puzzles. It was sort of a spur-of-the-moment sort of project, inspired by a friend that had to write something similar for an assignment. One of the Project Euler questions involves solving a set of 50 some Sudoku puzzles, so I figured I’d use the final code for my Euler solutions.

Initially, I wrote a very basic system designed to perform the classic process of elimination approach used by most human solvers. Of course, for the Euler question a good number of the puzzles were beyond such a solver and required a more powerful solution. My second iteration of the Sudoku solver used a basic brute-force approach by recursing through the vacant square and testing numbers. It was fairly efficient; it could solve easier puzzles in a few milliseconds, taking 20 or so for hard questions. I unfortunately have not gotten around to writing a logic-based “smart” solver yet, however this is definitely a topic I’d like to explore again in the future.

Just for anyone that’s curious, I plotted a few graphs that charted the active cell vs. the call number for the recursion function. The first graph shows a very basic puzzle, which only took around 280 recursive calls to reach a solution. The second shows a more tricky puzzle, which took a little less than 4,500 calls. The worst case puzzle, pulled from a Wikipedia article, took some 300,000 calls and had such a large dataset that Excel decided it didn’t want to function properly (read: it crashed).

Easy Sudoku graph:
Easy Sudoku

Hard Sudoku graph:
Hard Sudoku

That’s all for now!

T


%d bloggers like this: