Problem of the Day: Pyramid Sort

Sorting is always tricky and heavily studied for speed and efficiency. My first through was using the idea of keeping the odd numbers on the left and the even on the right which works if the array is only sequential numbers; that assumption certainly makes an assumption out of you and me.

Scratch that idea right quick. Next plan, find the highest number in the array and put it in the middle (index n/2 of odd-numbered arrays or index n/2 + 1 of even numbers to keep the higher number on the right). Works, but then it has to work through both halves at that point. Easy with recursion but not as straight forward.

Last idea, and probably the one I’ll go with, is to focus on the lowest number instead of the high number. Don’t find the highest and put it where it might go instead find the lower number and put it where it will go. The lowest numbers always go on the ends, alternating from left to right where-as the highest number will go in the “middle” then split the array. Work from the outside to the inside instead of inside out. We’ll see where this takes me.

I really should start using something other than Java for variety and to work out the other languages I’m familiar with, C, JS, PHP, even AndroidOS using a nice GUI; but not today.

Anyway, here’s the problem description:

The pyramids of Egypt are some of the most fascinating structures in the world. To honor the great pyramids we’ll be introducing pyramid sort. Pyramid sort works so that the highest numbers are in the center of the array and the lowest are on the edges. When comparing 2 numbers the smaller number goes on the left. So if the array contains 1,2,3 then 1 goes on the left with 2 on the far right and 3 in the middle. Here are 2 more examples:

> psort([1,2,3,4,5])
[1,3,5,4,2]

> psort([1,3,5,7,9,11])
[1,5,9,11,7,3]

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: