Quick Sort By Hand

Here is a rough by hand quick sort algorithm example :

Quick Sort

Quick Sort is very popular and widely used sort algorithm. Quick Sort is generally unstable. But there are ways to make quick sort stable, it depends on the actual implementation.

A sorting algorithm is stable if it maintains the relative order of the items in the final output i.e. Two objects with equal keys should appear in the same order in the sorted output as they appear in the input array to be sorted.

Quick Sort is divide and conquer type of an algorithm and key part of the quick sort is the partitioning implementation. Partitioning basically divides the input list into multiples parts and sorts each one of them recursively. Quick Sort is in place sort i.e. no extra storage space (variables) are required for quick sort algorithm.

Quick Sort algorithm works as follows:

For a given list
1. Pick a "pivot" element
2. "Partition" the array into three parts:
   i. All elements in this part are less than the pivot
  ii. The pivot itself (one element)
 iii. All elements in this part are greater than or equal to pivot
3. Apply the quick sort algorithm to the first and the third part recursively.

Partitioning is the most crucial part of quick sort and it should be done in place. There are different techniques for choosing a pivot element and partitioning.

Best and average case performance for quick sort is O(nlogn). Its worst case performance is O(n^2).
Again quick sort is very widely used algorithm. If we do random shuffling of the list at the beginning of quick sort, then it almost guarantees O(nlogn) performance.

Simplest implementation of Quick Sort in java is as follows:

package computer.science;

import java.util.Random;

public class QuickSort {

public static void sort(int a[]) {

quicksort(a, 0, a.length - 1);

}

private static void quicksort(int[] a, int lo, int hi) {

int i = lo;

int j = hi;

int pivot = a[(lo + hi) / 2];

// partition

while (i <= j) {

while (a[i] < pivot)

i++;

while (a[j] > pivot)

j--;

if (i <= j) {

if (i != j) // optimization

swap(a, i, j);

i++;

j--;

}

}

// quick sort left side

if (lo < j)

quicksort(a, lo, j);

// quick sort right side

if (i < hi)

quicksort(a, i, hi);

}

private static void swap(int[] a, int x, int y) {

int t = a[x];

a[x] = a[y];

a[y] = t;

}

public static void main(String[] args) {

final int LENGTH = 100;

int[] a = new int[LENGTH];

Random random = new Random();

for (int i = 0; i < LENGTH; i++) {

a[i] = random.nextInt(100);

}

System.out.println("Before sort : ");

display(a);

long startTime = System.nanoTime();

sort(a);

long endTime = System.nanoTime();

System.out.println("After sort : ");

display(a);

double sortTime = (endTime - startTime) / 1000000.0;

System.out.println("Estimated Time for Sort: " 

                                 + sortTime + " milliseconds.");

}

private static void display(int[] a) {

for (int i = 0; i < a.length; i++) {

System.out.print(a[i]);

System.out.print(" ");

}

System.out.println();

}

}

Merge Sort

Merge Sort algorithm works as follows:

While the list has more than one elements:
  Divide the list in two halves
  Sort first half
  Sort second half
  Merge sorted lists

This strategy is called divide-and-conquer method. We take advantage of the recursion technique in merge sort. So there are two operations happening recursively, dividing the list into two halves and merging them back. The base case for the recursion is when the list size is one.

Following diagram illustrates merge sort algorithm:

The number of times the list of size n is divided is equal to log(n). Where log(n) resembles to height of a virtual tree created during recursive calls to merge sort.

The time complexity of merge function is linear i.e. it takes exactly n operations to merge two lists of size n/2. Hence the overall time complexity of merge sort is O(n log n).

Here is a java implementation of a merge sort algorithm:

public class MergeSort {

public static void sort(int[] a) {

int left = 0; // start index of the list

int right = a.length - 1; // end index of the list

int[] aux = new int[a.length];

mergeSort(a, aux, left, right);

}

private static void mergeSort(int[] a, int[] aux, 

                                      int left, int right) {

if (left < right) {

int center = (left + right) / 2;

mergeSort(a, aux, left, center);

mergeSort(a, aux, center + 1, right);

merge(a, aux, left, center + 1, right);

}

}

private static void merge(int[] a, int[] aux, int left, 

                                          int right, int rightEnd) {

int leftEnd = right - 1;

int numOfElements = rightEnd - left + 1;

int k = left; // start index to save merged result

while (left <= leftEnd && right <= rightEnd) {

if (a[left] <= a[right]) {

aux[k++] = a[left++];

} else {

aux[k++] = a[right++];

}

}

// copy leftover elements from first list

while (left <= leftEnd) {

aux[k++] = a[left++];

}

// copy leftover elements from second list

while (right <= rightEnd) {

aux[k++] = a[right++];

}

// copy auxiliary back to a

for (int i = 0; i < numOfElements; i++, rightEnd--) {

a[rightEnd] = aux[rightEnd];

}

}

}

Test program to test merge sort algorithm:

import java.util.Random;

public class SortTest {

public final static int LENGTH = 10;

public static void main(String[] args) {

int[] a = new int[LENGTH];

Random random = new Random();

for (int i = 0; i < LENGTH; i++) {

a[i] = random.nextInt(100);

}

System.out.println("Before sort : ");

display(a);

long startTime = System.nanoTime();

MergeSort.sort(a);

long endTime = System.nanoTime();

System.out.println("After sort : ");

display(a);

double sortTime = (endTime - startTime) / 1000000.0;

System.out.println("Estimate Time for Sort: "

                              + sortTime + " milliseconds.");

}

private static void display(int[] a) {

for (int i = 0; i < a.length; i++) {

System.out.print(a[i]);

System.out.print(" ");

}

System.out.println();

}

}

Insertion Sort

Insertion Sort works as follows:

1. Divide the given list into two parts: sorted and unsorted
2. Iterate over unsorted list and insert each element into the sorted list at a proper position
3. So the elements in the sorted list are always in order

Following diagram illustrates this method:

Pseudocode for Insertion Sort:

Insertion-Sort(LIST)

  for j = 2 to LIST.length
      key = LIST[j]
      // insert key into sorted sequence LIST[1 .. j-1]
      i = j - 1
      while i >= 0 and key < LIST[i]
          LIST[i + 1] = LIST[i]
          i = i - 1    
      LIST[i + 1] = key

And here is a Java implementation of Insertion sort algorithm:

public class InsertionSort {
public static void sort(int[] list) {
for (int j = 1; j < list.length; j++) {
int key = list[j];
int i = j - 1;
while (i >= 0 && key < list[i]) {
list[i + 1] = list[i];
i--;
}
list[i + 1] = key;
}
}
}

Worst case running time for insertion sort is quadratic i.e. O(n^2).
Best case (when the array is already sorted) running time is linear i.e. O(n).

Space complexity for insertion sort is O(1) i.e. it requires constant amount of extra storage, in this case only one temporary variable which is "key".

Insertion sort is often a choice when the list is nearly sorted or when the list size small. Insertion is stable because it maintains the order of items which are equal.

Selection Sort - Algorithm Analysis

Let us look at the time and space complexity of the Selection Sort algorithm.

As seen in the above diagram, for n element list, there are total n -1 iterations required. Total number of comparisons required in the first iteration is n - 1, in second iteration n - 2, in third iteration n -2 and so on. This is comparison scenario is equivalent to summation series.

Hence, the time complexity of selection sort using asymptotic Big(O) notation is O(n^2). 

If we consider the swap operations, selection sort takes n swaps (1 swap operation in each iteration). According to the asymptotic notation, the value n^2 will dominate for large values of n. Hence this constant value of swap operations can also be dropped for algorithm analysis. So worst case running time for selection sort is O(n^2).

Space complexity for selection sort is O(1). Extra space is required only during swap operation.

Selection Sort

In selection sort algorithm, list is divided into 2 lists: sorted & unsorted list.
In each iteration, smallest element is selected from unsorted list and appended to the sorted list.

While starting the scan of list, assume that the first element is the smallest, then compare it with the rest of the elements in the list, save the index of smallest element along the way. Once all the elements are scanned, swap the starting index element with the minimum index element (if the indices are different).

Here is a Java implementation of a selection sort algorithm:

In the next post, we will look at the time & space complexity of the selection sort algorithm.

Bubble Sort: Illustrated

Bubble sort is called "Bubble Sort" because the largest item in the list bubbles up to the end of a list after each iteration.

Following images illustrate this concept.

In this example the length of an array is 6.
In first iteration of a for loop (where j = 1), index i starts at 0 and ends at 5 (lenght - j).

In second iteration of a for loop (where j = 2), index i starts at 0 and ends at 4 (lenght - j).

In third iteration of a for loop (where j = 2), index i starts at 0 and ends at 3 (lenght - j).

In fourth iteration of a for loop (where j = 3), index i starts at 0 and ends at 2 (lenght - j).

In this iteration, there was no swapping of items as the list is already sorted. Hence the while loop terminates.

As you can see, after each iteration of a for loop, the length of an iteration reduces by 1 (because of an optimization condition i < length - j). Another optimization used is the boolean variable "swapped", if there no swaps during an iteration, that means the list is already sorted. So we can terminate outer loop immediately.

Optimized Bubble Sort in Java

Bubble sort is a simplest sorting algorithm which is used as a traditional method to introduce sorting concept to the students of computer science. Though it is not very efficient algorithm, it illustrates the sorting methodology very well.

Here is a bubble sort algorithm with "two optimizations" (think!!) :

Could you find out the optimizations used in above java code?
Best case running time for this algorithm in O(n) and worst case running time is O(n^2).