Exploring the Worst Case Complexity of Quicksort

The quicksort algorithm has the best case complexity of O(n log n) when each pivot in the sort divides the list into two equal uniform pieces [1]. The worst case occurs when the pivot always divides the list into one list of size 1 and one list of size N - 1. Such as when sorting an already sorted array and the pivot is always chosen as the last element in the list. The complexity of quicksort in this case is an unfortunate O(n2). For this reason, it is recommended to use a random pivot point. This gives an average case of O(n log n) [2]. However, this does not remove the worst case scenario.

For example, consider this array:

array = {44,88,7,2,1,999,1040,23,123,89,2009}
with these given “random” pivots:
4,3,2,7,4,7,9,8,8,9

You get this result:

   algorithms, quicksort, java, big-o

Login Screen with NgAndroid

Edit*

With the release of the official Android data binding library NgAndroid has been deprecated.




I really don’t like writing user interface glue code. Enough said about that.

TL;DR

NgAndroid is an effecient compile time annotation processor that generates two data binding and layout controllers for Android MVC. NgAndroid is currently unstable.

The code for a login screen can be found below or here.

   android, ngandroid

NgAndroid Introduction

Edit*

This tutorial is out of date. See Login Screen with NgAndroid for a tutorial on the lastest version of NgAndroid.


NgAndroid


It’s finally here. The Android UI framework has become as simple and powerful as AngularJS. Sort of.

The project ngAndroid (which is still in beta) on Github has done something that some might not think is possible; NgAndroid brings Angular type directives and data-binding to Android xml attributes.

If you don’t know anything about AngularJS then you probably don’t know why this is such an exciting anouncement. You can learn more at Angular’s website but a previous knowledge of AngularJS is not required to revel in the epicness that is about to be laid before your eyes.

   android, angular

Creating a striped view in Android

Have you ever said to yourself, ‘Wow, this view needs some stripes, but there is no android:stripes=“true” attribute and I don’t know how to draw stripes using the canvas’? If so, this is the perfect place for you. Or, if you need to draw stripes and figured you’d check the internet for an easy solution before you tried it yourself than you are also in the right place.

For those of you who just want the code here it is.

public class StripedView extends View {

    private static final float STRIPE_WIDTH_PERCT = .05f;
    private static final float STRIPE_OFFSET_PERCT = .2f;
    private Path stripespath = new Path();
    private Paint blackPaint = new Paint();

    public StripedView(Context context) {
        super(context);
    }

    public StripedView(Context context, AttributeSet attrs) {
        super(context, attrs);
    }

    public StripedView(Context context, AttributeSet attrs, int defStyleAttr) {
        super(context, attrs, defStyleAttr);
    }

    @TargetApi(Build.VERSION_CODES.LOLLIPOP)
    public StripedView(Context context, AttributeSet attrs, int defStyleAttr, int defStyleRes) {
        super(context, attrs, defStyleAttr, defStyleRes);
    }
    //init()
    {
        blackPaint.setAntiAlias(true);
    }

    @Override
    protected void onDraw(Canvas canvas) {
        super.onDraw(canvas);
        drawStripes(canvas, 0, getHeight(), 0, getWidth(), blackPaint);
    }

    private void drawStripes(Canvas canvas, float topy, float bottomy, float startx, float endx, Paint p){
        if(bottomy - topy < 1){
            return;
        }
        stripespath.reset();
        float width = (bottomy - topy) * STRIPE_WIDTH_PERCT;
        float offset = (bottomy - topy) * STRIPE_OFFSET_PERCT;
        for(float xPos = startx - offset; xPos <= endx; xPos += offset + width){
            stripespath.moveTo(xPos, topy);
            stripespath.lineTo(xPos + width, topy);
            stripespath.lineTo(xPos + offset + width, bottomy);
            stripespath.lineTo(xPos + offset, bottomy);
            stripespath.lineTo(xPos, topy);
        }
        canvas.drawPath(stripespath, p);
    }
}
Which will result in something that looks like this.