Sorting

Introduction

Sorting is ordering a list of objects. We can distinguish two types of sorting. If the number of objects is small enough to fits into the main memory, sorting is called internal sorting. If the number of objects is so large that some of them reside on external storage during the sort, it is called external sorting. In this chapter we consider the following internal sorting algorithms

• Bucket sort
• Bubble sort
• Insertion sort
• Selection sort
• Heapsort
• Mergesort

O(n) algorithms

Bucket Sort

Suppose we need to sort an array of positive integers {3,11,2,9,1,5}. A bucket sort works as follows: create an array of size 11. Then, go through the input array and place integer 3 into a second array at index 3, integer 11 at index 11 and so on. We will end up with a sorted list in the second array.
Suppose we are sorting a large number of local phone numbers, for example, all residential phone numbers in the 412 area code region (about 1 million) We sort the numbers without use of comparisons in the following way. Create an a bit array of size 10⁷. It takes about 1Mb. Set all bits to 0. For each phone number turn-on the bit indexed by that phone number. Finally, walk through the array and for each bit 1 record its index, which is a phone number.
We immediately see two drawbacks to this sorting algorithm. Firstly, we must know how to handle duplicates. Secondly, we must know the maximum value in the unsorted array.. Thirdly, we must have enough memory - it may be impossible to declare an array large enough on some systems.
The first problem is solved by using linked lists, attached to each array index. All duplicates for that bucket will be stored in the list. Another possible solution is to have a counter. As an example let us sort 3, 2, 4, 2, 3, 5. We start with an array of 5 counters set to zero.

0	1	2	3	4	5
0	0	0	0	0	0

Moving through the array we increment counters:

0	1	2	3	4	5
0	0	2	2	1	1

Next,we simply read off the number of each occurrence: 2 2 3 3 4 5.

O(n²) algorithms

Bubble Sort

The algorithm works by comparing each item in the list with the item next to it, and swapping them if required. In other words, the largest element has bubbled to the top of the array. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items.

void bubbleSort(int ar[])
{
   for (int i = (ar.length - 1); i >= 0; i--)
   {
      for (int j = 1; j ≤ i; j++)
      {
         if (ar[j-1] > ar[j])
         {
              int temp = ar[j-1];
              ar[j-1] = ar[j];
              ar[j] = temp;
   } } } }

Example. Here is one step of the algorithm. The largest element - 7 - is bubbled to the top:

7, 5, 2, 4, 3, 9
5, 7, 2, 4, 3, 9
5, 2, 7, 4, 3, 9
5, 2, 4, 7, 3, 9
5, 2, 4, 3, 7, 9
5, 2, 4, 3, 7, 9

The worst-case runtime complexity is O(n²). See explanation below 
 

Selection Sort

The algorithm works by selecting the smallest unsorted item and then swapping it with the item in the next position to be filled.
The selection sort works as follows: you look through the entire array for the smallest element, once you find it you swap it (the smallest element) with the first element of the array. Then you look for the smallest element in the remaining array (an array without the first element) and swap it with the second element. Then you look for the smallest element in the remaining array (an array without first and second elements) and swap it with the third element, and so on. Here is an example,

void selectionSort(int[] ar){
   for (int i = 0; i ‹ ar.length-1; i++)
   {
      int min = i;
      for (int j = i+1; j ‹ ar.length; j++)
            if (ar[j] ‹ ar[min]) min = j;
      int temp = ar[i];
      ar[i] = ar[min];
      ar[min] = temp;
} }

Example.

29, 64, 73, 34, 20,
20, 64, 73, 34, 29,
20, 29, 73, 34, 64
20, 29, 34, 73, 64
20, 29, 34, 64, 73 

The worst-case runtime complexity is O(n²).

Insertion Sort

To sort unordered list of elements, we remove its entries one at a time and then insert each of them into a sorted part (initially empty):

void insertionSort(int[] ar)
{
   for (int i=1; i ‹ ar.length; i++)
   {
      int index = ar[i]; int j = i;
      while (j > 0 && ar[j-1] > index)
      {
           ar[j] = ar[j-1];
           j--;
      }
      ar[j] = index;
} }

Example. We color a sorted part in green, and an unsorted part in black. Here is an insertion sort step by step. We take an element from unsorted part and compare it with elements in sorted part, moving form right to left.

29, 20, 73, 34, 64
29, 20, 73, 34, 64
20, 29, 73, 34, 64
20, 29, 73, 34, 64
20, 29, 34, 73, 64
20, 29, 34, 64, 73 

Let us compute the worst-time complexity of the insertion sort. In sorting the most expensive part is a comparison of two elements. Surely that is a dominant factor in the running time. We will calculate the number of comparisons of an array of N elements:

we need 0 comparisons to insert the first element
we need 1 comparison to insert the second element
we need 2 comparisons to insert the third element
...
we need (N-1) comparisons (at most) to insert the last element

Totally,

1 + 2 + 3 + ... + (N-1) = O(n²)

The worst-case runtimecomplexity is O(n²).What is the best-case runtime complexity? O(n). The advantage of insertion sort comparing it to the previous two sorting algorithm is that insertion sort runs in linear time on nearly sorted data.

O(n log n) algorithms

Mergesort

Merge-sort is based on the divide-and-conquer paradigm. It involves the following three steps:

• Divide the array into two (or more) subarrays
• Sort each subarray (Conquer)
• Merge them into one (in a smart way!)

Example. Consider the following array of numbers

27  10  12  25  34  16  15  31

divide it into two parts

27  10  12  25            34  16  15  31

divide each part into two parts

27  10            12  25            34  16            15  31

divide each part into two parts

27       10       12       25       34       16       15       31


merge (cleverly-!) parts


10  27            12  25            16  34            15  31

merge parts

10  12  25  27                 15  16  31  34

merge parts into one

10  12  15  16  25  27  31  34

How do we merge two sorted subarrays? We define three references at the front of each array.
We keep picking the smallest element and move it to a temporary array, incrementing the corresponding indices.

Complexity of Mergesort

Suppose T(n) is the number of comparisons needed to sort an array of n elements by the MergeSort algorithm. By splitting an array in two parts we reduced a problem to sorting two parts but smaller sizes, namely n/2. Each part can be sort in T(n/2). Finally, on the last step we perform n-1 comparisons to merge these two parts in one. All together, we have the following equation

T(n) = 2*T(n/2) + n - 1

The solution to this equation is beyond the scope of this course. However I will give you a resoning using a binary tree. We visualize the mergesort dividing process as a tree

Lower bound

What is the lower bound (the least running time in the worst-case) for all sorting comparison algorithms? A lower bound is a mathematical argument saying you can't hope to go faster than a certain amount. The preceding section presented O(n log n) mergesort, but is this the best we can do? In this section we show that any sorting algorithm that sorts using comparisons must make O(n log n) such comparisons.
Suppose we have N elements. How many different arrangements can you make? There are N possible choices for the first element, (N-1) possible choices for the second element, .. and so on. Multiplying them, we get N! (N factorial.)
Next, we observe that each comparison cut down the number of all possible comparisons by a factor 2. Any comparison sorting algorithm can always be put in the form of a decision tree. And conversely, a tree like this can be used as a sorting algorithm. This figure illustrates sorting a list of {a₁, a₂, a₃} in the form of a dedcision tree:
Observe, that the worst case number of comparisons made by an algorithm is just the longest path in the tree. At each leaf in the tree, no more comparisons to be made. Therefore, the number of leaves cannot be more than 2^x, where x is the maximum number of comparisons (or the longest path in the tree). On the other hand, as we counded in the previous paragraph, the number of all possible permutatioins is n!. Combining these two facts, gives us the following equality:
2^x ≥ N! where x is the number of comparisons. By taking logarithm, implies
x ≥ log N! Using the Stirling formula for N!, we finally arrive at
x ≥ N log N or
x = O(N Log N)

Sorting in Java

In this section we discuss four different ways to sort data in Java.

Arrays of primitives

An array of primitives is sorted by direct invocation of Arrays.sort method

int[] a1 = {3,4,1,5,2,6};
Arrays.sort(a1);

Arrays of objects

In order to sort an array of abstract object, we have to make sure that objects are mutually comparable. The idea of comparable is extension of equals in a sence than we need to know not only that two objects are not equal but which one is larger or smaller. This is supported by the Comparable interface. This interface contains only one method with the following signature:

 public int compareTo(Object obj);

The returned value is negative, zero or positive depending on whether this object is less, equals or greater than parameter object. Note a difference between the equals() and compareTo() methods. In the following code example we design a class of playing cards that can be compared based on their values:

class Card implements Comparable<Card>
{
   private String suit;
   private int value;

   public Card(String suit, int value)
   {
      this.suit = suit;
      this.value = value;
   }
   public int getValue()
   {
      return value;
   }
   public String getSuit()
   {
      return suit;
   }
   public int compareTo(Card x)
   {
      return getValue() - x.getValue();
   }
}

Suppose that the Card class implements the Comparable interface, then we can sort a group of cards by envoking by Arrays.sort method.

Card[] hand = new Card[5];
Random rand = new Random();
for (int i = 0; i ‹ 5; i++)
 hand[i] = new Card(rand.nextInt(5), rand.nextInt(12));
Arrays.sort(hand);

It is important to recognize that if a class implements the Comparable interface than compareTo() and equals() methods must be correlated in a sense that if x.compareTo(y)==0, then x.equals(y)==true. The default equals() method compares two objects based on their reference numbers and therefore in the above code example two cards with the same value won't be equal. And a final comment, if the equals() method is overriden than the hashCode() method must also be overriden, in order to maintain the following properety: if x.equals(y)==true, then x.hashCode()==y.hashCode().

Collection of comparable objects

Mutually comparable objects in a collection are sorted by Collections.sort method:

ArrayList‹Integer> a2 = new ArrayList‹Integer> (5);
...
Collections.sort(a2);

Android : Passing data between main thread and worker threads

Android : Passing data between main thread and worker threads.

There may be situations where you want to spawn a thread from your Activity or Service to handle long
running (and may be blocking) tasks. In such cases, its sometimes necessary to pass data back and forth
between the main thread and the worker thread(s). E.g. if the worker thread finishes a task and returns the result
to the main activity to display the results OR you want to keep a worker thread around and ask it to switch
between tasks depending on some message you pass to it.

In the past, I faced some problems understanding these concepts associated with different classes in
 android.os like the Handler, Looper, HandlerThread etc...

I'll try to explain these concepts in a simple language. Probably most of these explanations are from the
developer documentation, but I thought consolidating these at one place may help to get a good picture.

Ok. So, when an application runs, it runs in a Main thread called as the UI thread. Any other thread can be
created using the standard java.lang.Thread class. As I said in a typical situation you will spawn a thread,
may be pass some data to it OR the thread may pass back some data to the Main thread from time to time
as well as when its done executing.

Let us consider the task where we need to send data to a worker thread. So first, we create a worker thread.

STEP 1: Create a worker thread

class MyThread extends Thread {
    @Override
    public void run(){
    }
}

In our main thread...

MyThread mThread = new MyThread();
mThread.start();

When you have to pass any messages to a thread or get messages from a thread, the receiving thread 
needs a MessageQueue. By default, a thread created by using the java.lang.Thread class will not have a
MessageQueue associated with it. Its just a plain old thread as in the Fig. 1 (Yes, I know. What an innovative
diagram !! :D ).




Now, we need to attach a MessageQueue to our thread. The Looper class provides the method prepare() to
create a message queue for a thread. We need to call this method from the receiving thread's run method.

STEP 2: Call the Looper methods

class MyThread extends Thread {

    @Override

    public void run(){

           Looper.prepare();

           Looper.loop();

    }

}

As you see, there is one more Looper method called in the code. This loop() method will start running the
message loop for the current thread. In simple terms, it will start looking at the MessageQueue and processing
the messages. This is how I interpret the Looper as in Fig. 2.

But, who sends the messages to the MessageQueue and how are these processed ? There is a class called
the Handler. The Hander allows us to send and process Messages (as well as Runnable Objects) associated
with the thread's MessageQueue. So, we need to create a Handler. It is important to note that the Handler 
is associated with the thread that creates it ! The Handler provides methods to handle (receive) Messages
as well as send and schedule messages. For details, please refer to documentation.

STEP 3: Create a Handler to receive the Messages

class MyThread extends Thread {

    public Handler mHandler;

    @Override

    public void run(){

           Looper.prepare();

           mHandler = new Handler() {

                   public void handleMessage(Message msg) {

                       // Act on the message

                   }

           };

           Looper.loop();

    }

}

If you notice, this code is the same that is listed on the Looper documentation page here.  Few things to
mention here are. The Handler is created in this thread, hence it is associated with the default Looper
(read MessageQueue) in the current thread. There are constructors for the Handler that allow us to specify
the Looper (again, read MessageQueue). This allows us to write a cleaner code by writing the Handler class
separately and passing on a Looper (again, again, read MessageQueue) when the Handler is created. I'll get
to this in a while. But as I have insisted, it is worth noting that whenever the developer documentation refers
to a Looper, you can assume they are talking about a queue. I'm really not sure why they have surfaced the
Looper class. It creates more confusion (at least for me). Also, when dealing with passing the messages, with
this mechanism, we really need not care of the MessageQueue call. That is the reason I haven't linked it to the
 documentation. Anyways... things are what they are ! For me, I like to interpret this whole mechanism as
depicted in Fig. 3.

Let me know if you like PAT or your way of viewing it !

So, now any other thread having the reference to mHandler will be able to call the send or post methods of
the Handler class to send a Message (or a runnable object) to our thread. The code for sending message will
look like:

Message msg = Message.obtain();

msg.obj =  // Some Arbitrary object

mHandler.sendMessage(msg);

Pretty simple yeah ! Btw, there are various methods to set/get data for the Message object which can be found
in the developer documentation for the Message class.

Summary of Steps :

1. Create a Handler in the receiving thread [If it is the main thread, create one in the main thread]. By default the
handler will be associated with the default queue (Looper).

2. So, if the receiving thread is created by using java.lang.Thread, then we need to call the Looper.prepare() and
Looper.loop() in order to set up the message queue for the thread.

3.  In the sending thread, prepare a message object (or a Runnable object)

4. Get a reference to the Handler in the sending thread and call the send/post methods on it to send a message.

HandlerThread:

Since by default java.lang.Thread doesn't contain a message queue (Looper), Android provides a class called
as the HandlerThread which already contains a message queue. The only difference in using the HandlerThread
class over the method described above is that you need not call the Looper.* methods.

On creation of a HandlerThread, Android will create a thread containing the looper. So, in the main thread the
code will look like:

HandlerThread myThread = new HandlerThread("Worker Thread");  

myThread.start(); 

We separately create a Handler as follows:

class MyHandler extends Handler { 

    public MyHandler(Looper myLooper) { 

        super(myLooper);
    }
    public void handleMessage(Message msg) { 

    }
} 

Now in the main thread, we get the looper for the HandlerThread and pass it when we create the Handler as follows:

Looper mLooper = myThread.getLooper(); 

MyHandler mHandler = new MyHandler(mLooper); 

Whenever we want to send a message from the main thread, we do it in a similar fashion.

Message msg = mHandler.obtainMessage(); 

msg.obj =  // Some Arbitrary object

mHandler.sendMessage(msg); 

I like to visualize this as shown below in Fig. 4 where we write the Handler separately and then pass a looper to it on
 its creation.