Quick Sort in C++

In my ongoing attempts to improve my programming skills, I've just read about quick sort.  Here is my quick/vague/one line/summary description of quick sort.  The quicksort algorithm works by recursively putting smaller elements to the left of a pivot and larger elements to the right of a pivot until your array is sorted.

Below is my attempt at coding up a working algorithm in C++.  The basic framework of the algorithm is as follows.

void quick_sort( vector & v, int start, int end ) {
    // partition the vector 
    int pivot = partition( v, start, end-1 );

    // recursive calls for each half.
    if ( start < pivot -1 ) 
        quick_sort( v, start, pivot-1 );
    if ( pivot < end ) 
        quick_sort( v, pivot, end );

    return;
}

The meat of the algorithm is in the partition() function. In this function, we do a few things.

1. Pick a pivot value.
2. Move all elements that are less than the pivot to the left of the pivot value.
3. Move all elements that are greater than the pivot value to the right of the pivot value.
4. Return the position of the pivot.  

Here's my code for a pivot function.

int partition( vector & v, int start, int end ) {
    int pivot =  v[ (start + end) / 2 ];

    while( start <= end ) {
       while( v[ start ] < pivot ) start++;
       while( v[ end ] > pivot ) end--;

       // swap values
       if ( start <= end ) {
           int tmp = v[start];
           v[start] = v[end];
           v[end] = tmp;

           start++;
           end--;
       }
    }
    return start;
}

Notes on quick sort.

• I think there are several other ways to write this algorithm.  Different implementations can affect things like how much memory is used, whether it is stable sort, and the overall performance.  
• One example where the implementation can affect performance is the choice of pivot.  I set the pivot as the mid point of the array, but it can be any value. If the input was already sorted, reverse sorted, or random, the pivot position can affect the performance of the algorithm (for better or worse).
• It took me a while to get the algorithm working because it was pretty easy to to have an off by one error in many places.  

Still on the search for my next computer

Like most programmers, once I get stuck on a problem, I can't stop thinking about it until I find a solution.  These days I have been shopping for a new computer.

My current computer, a HP DV2000 laptop, circa 2006, works OK.  Over the years, I have only made two upgrades: I doubled my RAM from one to two GB and I have switched my primary operating system to Linux Ubuntu over Windows XP.  For reference, my wife and I actually have the same exact computer, except that she didn't make any upgrades.  Amazingly, both computers have been working fine for all of these years.  (The only real deterioration is that neither of our batteries hold much of a charge, which could be fixed for 20 dollars).

So, even though my current laptop functions just fine, in the last couple of months, I thought it was about time that I (and my wife) upgrade our machines.  I'm not exactly sure why.  Maybe it's well placed advertisements, maybe it's my wife's subtle coaxing, or maybe it's the stark difference between my dual display powerhouse work setup versus my aging home laptop - but I think it's about time for an upgrade.

My wife says that I am not a good shopper, and she is right.  I know that I only have a finite amount of energy per day, and finding deals is something that I just do not want to spend any attention on.  If I'm shopping for a pair of jeans, I'll walk into the Gap and buy the first pair that sort of fit me OK.  In contrast, my wife will start browsing online for Jeans, eventually go to the Gap, take a hard look at every pair they have, go home, look for deals online, order three different pairs of jeans, try each pair on a few times, return two of them, and  voila, she has a pair of jeans.  In the end, it's clear that she looks better than I do.

But for a new computer, I have taken on her exhaustive approach and I have been scouring the world wide web for my and my wife's next laptop.  For my own reference, here are the upgrades from my current laptop that I am hoping to get for both my wife and I. 

• 2GB to 8 GB of RAM. 
• 80 GB hard drive to at least a 128 GB solid state drive.   
• 5.5 Lbs to less than 4lbs total weight.
• S-video or VGA output to HDMI output.

The one place we diverge is in the operating system.  My wife is looking for a Windows machine, but I'd like to use OS X or Ubuntu.

In the end, I decided to give the 13.3-Inch Apple MacBook Air a try.  I just put in an order for a refurbished model for  $999 ($1087 with tax).  It only has 4 GB of RAM, which I couldn't upgrade, because it is refurbished.  This will be a learning experience for me, because I have never owned a Mac before.

For my wife, we decided to get the 15" Samsung Series 9 a try. It has 8 GB of RAM, runs Windows 7, and is 3.6 lbs.

It's been a quick 7 years since our last laptop purchase, and I hope these new machines could serve us for a long time as well.  If they last us through 2020, that would be pretty remarkable.

I started this post saying that once I get a problem in my head, I can't stop thinking about it until I reach some conclusion.  After several days of shopping, reading reviews, and evaluating my needs, I couldn't take shopping anymore.  So, the only resolution was to make a decision and commit to one choice. I'm glad I made a choice so that I can go back to building apps, learning about coding and programming and doing anything else besides shopping.

Android update - 4.2.2

I use the Samsung Galaxy Nexus phone with Verizon Wireless as my carrier, and today I was updated to v 4.2.2.  Android 4.2 is still 'Jelly Bean', and so this is a minor update.

I immediately noticed a few nice new features.

Multiple Lock Screens
We are now able to have multiple lockscreens.  By default, one of the extra lockscreens is the camera app.  In the past, if I wanted to take a picture, I had to enter my password to unlock my phone, find the camera app icon and then take a picture.  Now, with an additional lockscreen, all I have to do is swipe to the right, and the camera app opens.

As of now, only a small portion of my apps support widgets that can be embedded into the lockscreen.  However, I'm sure app developers like myself will eventually build widgets to use on the lockscreen.

Improved settings screen
I used to use an app/widget called "Power Toggles" which gave me quick access to a few settings that I would toggle on and off, like turning on wifi or adjusting the screen brightness.  Android 4.2.2 now provides a quick settings widget.  This is available from the notification center.  Here's a screen shot.

This quick settings widget looks similar to some tools my wife has on her Samsung Galaxy Note and other Samsung Android phones that I have seen.

Improved clock app

The clock app from Android now has a timer and a stop watch.  Both look much better than any existing app.  I actually was so fed up with the existing set of clock apps, I thought about building an app to replace the stock Android Clock app.  It looks like the Android team has beaten me to the punch, and I really like the final product.  It would be nice if you could add the timer app to the lock screen, but it doesn't look available yet.  I guess it's just one step at a time.

Updated camera app

It looks like the camera app has been updated.  I don't really use the camera too much, so I can't remember how it has changed.  I can just tell that it looks a little bit different.

Overall, this update has improved in ways that I have found useful without taking away anything.  

Heap Sort with C++

In my attempt to improve my programming skills, I just read about the heap sort algorithm.
Here are my notes and code where I try to understand and implement the heapsort algorithm in C++.

Step one of the heapsort is to build a valid heap.  When someone says heap sort, we are looking at a binary heap.  A binary heap is a binary tree where all levels of a heap are filled (except possibly the last level) and where every parent is greater than either of its children.

For example, if you have an array or vector with these values:
[ 6,  8, 1 , 5, 7, 3,  2... ]
A binary heap would have this shape:

          6
      8        1
    5   7    3   2
...

and we would say 6 is the parent of 8 and 1, 8 is the parent of 5 and 7, etc ...  However, while this binary heap has the right shape, it fails to meet the criteria where every parent is greater than or equal to either of its children.

In order to transform an invalid heap to a valid one, I wrote the functions heapify() and shiftDown():

void heapify( vector & v, int start, int end )  {
    int midPos = ( end - start ) / 2;
    for ( int pos = midPos; pos >= 0; pos-- ) {
        shiftDown( v, pos, end );
    }
}
void shiftDown( vector & v, int parent_pos, int end_pos ) {

    // Sift the parent down the right child?
    int right_child_pos = ( parent_pos * 2 ) + 2;
    if ( right_child_pos < end_pos &&
         v[ parent_pos ] < v[ right_child_pos ] ) {
         int tmp = v[ parent_pos ];
         v[ parent_pos ] = v[ right_child_pos ];
         v[ right_child_pos ] = tmp;
         shiftDown( v, right_child_pos, end_pos );
     }

    // Sift the parent down the left child?
    int left_child_pos = ( parent_pos * 2 ) + 1;
    if ( left_child_pos < end_pos &&
         v[ parent_pos ] < v[ left_child_pos ] ) {
         int tmp = v[ parent_pos ];
         v[ parent_pos ] = v[ left_child_pos ];
         v[ left_child_pos ] = tmp;
         shiftDown( v, left_child_pos, end_pos );
     }

}

The heapify()  function walks from the parent that is on the lowest level of the heap (sits at n/2) to the parent at the top of the heap (position = 0).
For each parent, we use shiftDown() to shift values down the tree until the rule where any parent is greater than or equal to any child is fulfilled.

Given the above functions, we have a partially sorted list where the larger values are at the top of the heap, which is the start of the array.  To get a sorted array where the values go from smallest to largest, we cherry pick the top of the heap to get the max value then rebuild the heap, as follows:

void heapSort( vector & v )  {
    int numItems = v.size();
    heapify( v, 0, numItems - 1);

    for ( int end_pos = numItems - 1; end_pos >= 0; end_pos-- ) {
        int tmp = v[ 0 ]; 
        v[ 0 ] = v[ end_pos ];
        v[ end_pos ] = tmp;

        heapify( v, 0, end_pos);
    }
}

For the sake of testing I also wrote this function to print the array to look like a heap.

void print_as_heap( const vector & v ) {
    int max_row_size = 1;
    int row_size = 0;
    vector::const_iterator it ;
    for ( it = v.begin(); it != v.end(); it ++ ) {
        std::cout << " " << *it;
        row_size++;

        if ( row_size == max_row_size ) {
            std::cout << std::endl;
            row_size = 0;
            max_row_size *= 2;
        }
    }
    std::cout << std::endl;
}

The end.

Google retires google reader

I just heard that Google will be retiring Google Reader.  Reader was the first RSS feeds aggregator that I have ever used. And like many firsts, it is something that I loved. I have a twitter account, Facebook and a Google+ account, but the content I get from those channels is incredibly shallow.  Maybe it is my fault and I should friend or follow more interesting people. But really, such is the nature of those social media. You post quips, comments and tweets with a link and that's it.  I prefer blog posts that have paragraphs of thought on a single subject.  Thus Google reader was my favorite social media tool.

From the standpoint of a user, retiring Google reader is a bummer, but as a developer, this makes me happy.  Somewhere in the bowels of Google there are developers who built this product.  Either they have just lost the fight and their project was killed, or they have been relieved of their duties from having to support a product that they were tired of working on.  If I were them, and I have been in both scenarios, I'd be happy.  While it sucks when your project is retired or put on the back burner, it still means you will work on something new.  New means that you will learn about a new product, business, or technology. And learning makes most developers I know happy. 

Thinking about the company, I think this is great. Supporting applications or features just because there are users drives me crazy.  Its good to give users what they want. It is bad to let clients drive the direction of your product.  For whatever reason, Google decided that this product costs more than the benefits it provided, and they had the guts to kill it. 

Telling clients that they know what is best for them may sound arrogant, but I also think its true and good. Google has developers, who only have so much time to write code, debug issues, and develop products. As long as they spend some time listening to users and tracking their usage patterns, those developers are the only ones who can assess if its better to support reader or go in another direction.  A user would never be able to make that decision.

It will be a pain to find a new application that will fill the void left by Google.  I hope they provide something else that replaces it.  If not, I'm sure someone will develop a similar application or maybe I'd build something for myself.

Android notifications

Notifications are great.  Instead of manually opening an app and checking for updates (to see if you have any new emails or text messages), your smart phone works in the background and sends you alerts when updates are available.

I created a simple notification ( the one on top is mine ).

Here is some code to set up a simple notification:

// Set which activity is opened when you click on 
// the notification in the notification bar. 
// You can just re-open your app.
Intent intent = new Intent(this, MainActivity.class);

// Set these flags to re-open your app.  If it's not  
// killed you won't create a new activity.
intent.setFlags( Intent.FLAG_ACTIVITY_CLEAR_TOP |
                 Intent.FLAG_ACTIVITY_SINGLE_TOP );

// Make the pending intent. Give this to the notification
// so that your activity can be called.
PendingIntent pIntent = PendingIntent.getActivity(this, 0, intent, 0);

// Build the notification.
// With a title, text, and pending intent.
Notification notification = new Notification.Builder(this)
  .setContentTitle("Alert! You are notified.")
  .setContentText("Click to open app.")
  .setSmallIcon(R.drawable.ic_launcher)
  .setContentIntent(pIntent)
  .build();

// Hide the notification after its selected
notification.flags |= Notification.FLAG_AUTO_CANCEL ;
     
NotificationManager notificationManager = (NotificationManager)   
  getSystemService(NOTIFICATION_SERVICE);
notificationManager.notify(0, notification);

There are lots of bells and whistles (literally) that can be added to your notifications (I think).  This simple code demonstrates how simple it is to create a simple notification.

Resources:
http://www.vogella.com/articles/AndroidNotifications/article.html

Taxes

I just did my taxes today.  Here are some observations.

Turbotax is not linux friendly.
I am running Ubuntu and my default browser is chromium.  After logging into their site, I got a warning saying that I had to use either Internet Explorer, Firefox, Safari or Chrome.  I guess Chromium isn't the same as Chrome. Ok, no problem, I have firefox.  I switched browsers, logged in again, but was denied access again.  I didn't feel like debugging the problem, so I decided to log off of my ubuntu operating system and use Windows.  That's what dual booting is all about.  So there's one more reason why I can't wipe Windows from my life completely.

Turbotax is pretty user friendly.
I used Turbotax last year, and it was able to remember some of my information.  Since none of the major financial details in my life changed at all (lived in the same place, worked for the same employers, and so on), it was great that Turbotax was able to auto-populate a lot of details.  I'm not sure why, but it was able to import alot of my wife's information while I had to input some more items, but it was more or less very easy to use.  I finished inputting the details in about 15 minutes.

No default is the default.
For many screens in the Turbotax wizard there are a series of options with the final one being none of the above.  For example, they might ask, have you worked over seas, or worked in the military, or made money gambling etc ... and you can check yes to one or more of these.  But there's also another choice at the end that says, None of the above.  I hate it when that None of the above choice isn't selected by default.  I guess that's just a pet-peave of mine.  If it weren't for having to click on that choice, I might have been able to finish my taxes in 10 minutes.