Sunday, September 15, 2019

Largest Profit from Daily Stock Data

The problem is to take an array of daily stock prices and find the maximum profit from buying one day and selling on a later day (I assume, you cannot buy and sell on the same day and that you must pick one day to buy and one day to sell).

Basically, my algorithm sets buy dates and walks through the array until a date with a lesser value than the buy date occurs. If there are any dates between the buy date and the lesser value date, then the maximum value on these dates is considered the sell date for that buy date. If there are no dates between the buy date and the lesser value date, then the lesser value date becomes the sell date for the buy date. The lesser value date then becomes the next buy date.

Example 1. As an example, consider this array: 9, 10, 12, 11, 9, 5, 7, 10, 8, 4, 1, 3, 2. This array then becomes [9, 12][5, 10][4, 1][1, 3]. 9 is the first buy date and the first lesser value date is 5, so 12 becomes the first sell date (max value between 9 and 5). 5 becomes the second buy date and the second lesser value date is 4, so 10 becomes the second buy date (max value between 5 and 1). 4 is the third buy date and 1 is the third lesser value date, so 1 becomes the third sell date (no dates in between). Finally, 1 becomes the fourth buy date and there is no fourth lesser value date, so 3 becomes the fourth sell date (max value after 1). Therefore, the max profit is 10-5=5.

Example 2. Consider this array: 10, 8, 7, 4. This array becomes [10, 8][8, 7][7, 4]. 10 is the first buy date, 8 is the first lesser value date, so 8 becomes the first sell date (no dates in between). 8 is the second buy date, 7 is the second lesser value date, so 7 becomes the second sell date (no dates in between). 7 is the third buy date, 4 is the third lesser value date, so 4 becomes the third sell date (no dates in between). Therefore, the max profit is 7-8=-1.

Why does this work?

Let v_n denote the stock price on the nth day, where 0 <= n < N.  Let H be the set of all pairs (B, S) such that:
P1) 0 <= B < N
P2) 0 <= S < N
P3) B < S
P4) For any other values p, q such that:
   i) 0 <= p < N
   ii) 0 <= q < N
   iii) p < q
   Then v_q - v_p <= v_S - v_B

In other words, the Bth and Sth day represent the buy and sell dates respectively that will result in the maximum profit.

Now suppose, we have b, s, e such that:
T1) 0 <= b < N
T2) 0 <= s < N
T3) 0 <= e < N
T4) b < s
T5) s <= e
T6) For every j such that 0 <= j < b, then v_b < v_j
T7) For every j such that b <= j <= e, then v_b <= v_j and v_j <= v_s

Then, only one of the following can be true:
Q1) (b,s) is in H
Q2) For every j, k such that 0 <= j < N, b <= k <= e, (j, k) is not in H

Suppose (b,s) is not in H and there exists j, k such that 0 <= j < N, b <= k <= e where (j, k) is in H.  If (j, k) is in H, then by P3, 0 <= j < k <=e.  By T4, 0 <= j < b or b <= j < k <= e.  Then, by T6 and T7, v_b <= v_j.  By T7, v_k <= v_s.  Let p, q satisfy i), ii) and iii).  Then, v_s - v_b >= v_k - v_j >= v_q - v_p.  Therefore, (b,s) is in H, a contradiction.

Here, I have proven that if we find values b, s, e that satisfy properties 1) - 7), then either (b,s) provides the maximum profit by buying and selling on those days or selling on any days from b to e, including b and e, will not provide the maximum profit.  In other words, selling on any day from b to e, can only yield as much profit as selling on day s.  This allows us to rule out many days as potential selling days.  Also, if s happens to be the day to sell that will yield the most profit, buying on any day from 0 to s - 1, including 0 and s-1, can only yield as much profit as buying on day b.

Source

package algorithm;

/**
 * Assume stock prices are given in an array and you can pick one day to buy and a different day to sell
 * The sell day must be after the buy day
 * What is the profit from the best buy and sell?
 * @author sizu
 *
 */
public class BestBuyAndSell {
 
 public static void main(String[] args) throws Exception {
  int maxProfit1 = findMaxProfit(new int[] {9, 8, 12, 5, 9, 10, 1, 2});
  System.out.println("maxProfit1:"+maxProfit1); // 5
  
  int maxProfit2 = findMaxProfit(new int[] {15, 9, 8, 6, 3});
  System.out.println("maxProfit2:"+maxProfit2); // -1
  
  int maxProfit3 = findMaxProfit(new int[] {9, 8, 12, 5, 9, 10, 1, 15});
  System.out.println("maxProfit3:"+maxProfit3); //14
 }

 private static int findMaxProfit(int[] priceArray) throws Exception {
  if(priceArray.length < 2) {
   throw new Exception ("invalid argument");
  }
  int currentMax = priceArray[1] - priceArray[0]; // Arbitrarily to buy on day 1, sell on day 2
  int min = priceArray[0];
  Integer max = null;
  
  // O(n)
  for(int i=1; i<priceArray.length; i++) {
   int currentVal = priceArray[i];
   if(currentVal < min) {
    if(max != null) {
     int profit = max - min;
     if(profit > currentMax) {
      currentMax = profit;
     }
    } else {
     int profit = currentVal - min;
     if(profit > currentMax) {
      currentMax = profit;
     }
    }
    min = currentVal;
    max = null;
   } else if (max == null) {
    max = currentVal;
   } else if (currentVal > max) {
    max = currentVal;
   }
  }
  if(max != null) {
   int profit = max - min;
   if(profit > currentMax) {
    currentMax = profit;
   }
  }
  
  return currentMax;
 }
}

Output

maxProfit1:5
maxProfit2:-1
maxProfit3:14

Monday, September 9, 2019

Mergesort

Mergesort implementation from en.wikipedia.org.
package algorithm;

public class mergesort {
 public static void main(String[] args) {
  System.out.println("Case I");
  int[] numbers = new int[] {3, 7, 8, 5, 2, 1, 9, 5, 4};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  mergesort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");
  
  System.out.println("Case II");
  numbers = new int[] {9, 8, 7, 6, 5, 4, 3, 2, 1};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  mergesort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");

  System.out.println("Case III");
  numbers = new int[] {5, 5, 5, 5, 5, 5, 5, 5, 5};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  mergesort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");

  System.out.println("Case IV");
  numbers = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  mergesort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");
 }

 private static void printArray(int start, int end, int[] numbers, String text) {
  String out = "{";
  String del = "";
  for(int i=start; i < end + 1; i++) {
   out = out + del + numbers[i] + "";
   del = ",";
  }
  out = out + "}";
  System.out.println(text+":"+out);
 }
 
 // O(n log n)
 private static void mergesort(int[] numbers) {
  int[] temparray = new int[numbers.length];
  
  // Outer loop is O(log n) - Divide and Conquer
  mergesortAlgorithm(0, numbers.length - 1, numbers, temparray);
 }

 private static void mergesortAlgorithm(int start, int end, int[] numbers, int[] temparray) {
  if(end == start) {
   return;
  } else {
   int numbersInFirstHalf = (end - start + 1)/2; // This is Math.floor
   int firstHalfStart = start;
   int firstHalfEnd = start + numbersInFirstHalf - 1;
   int secondHalfStart = start + numbersInFirstHalf;
   int secondHalfEnd = end;
   
   // Outer loop is O(log n) - Divide and Conquer
   mergesortAlgorithm(firstHalfStart, firstHalfEnd, numbers, temparray);
   mergesortAlgorithm(secondHalfStart, secondHalfEnd, numbers, temparray);
   
   mergeSorted(start, end, numbers, temparray, firstHalfStart, firstHalfEnd, secondHalfStart, secondHalfEnd);

   // Copy sorted back into original
   copyArrayElements(start, end, temparray, start, numbers);
   printArray(start, end, numbers, "sorted_subarray");
  }
 }

 private static void mergeSorted(int start, int end, int[] numbers,
   int[] temparray, int firstHalfStart, int firstHalfEnd,
   int secondHalfStart, int secondHalfEnd) {

  int tempindex = start;
  
  int firstNum = numbers[firstHalfStart];
  int secondNum = numbers[secondHalfStart];
  
  // Inner loop is O(n) 
  while(true) {
   if(firstNum < secondNum) {
    temparray[tempindex] = firstNum;
    tempindex++;
    firstHalfStart++;
    if(firstHalfStart == firstHalfEnd + 1) {
     copyArrayElements(secondHalfStart, secondHalfEnd, numbers, tempindex, temparray);
     return;
    } else {
     firstNum = numbers[firstHalfStart];
    }
   } else {
    temparray[tempindex] = secondNum;
    tempindex++;
    secondHalfStart++;
    if(secondHalfStart == secondHalfEnd + 1) {
     copyArrayElements(firstHalfStart, firstHalfEnd, numbers, tempindex, temparray);
     return;
    } else {
     secondNum = numbers[secondHalfStart];
    }
   }
  }
 }

 private static void copyArrayElements(int fromStart, int fromEnd, int[] from,
   int toStart, int[] to) {
  for(int i=fromStart; i<=fromEnd; i++){
   to[toStart] = from[i];
   toStart++;
  }
 }
}
Output
Case I
pre_sort:{3,7,8,5,2,1,9,5,4}
sorted_subarray:{3,7}
sorted_subarray:{5,8}
sorted_subarray:{3,5,7,8}
sorted_subarray:{1,2}
sorted_subarray:{4,5}
sorted_subarray:{4,5,9}
sorted_subarray:{1,2,4,5,9}
sorted_subarray:{1,2,3,4,5,5,7,8,9}
post_sort:{1,2,3,4,5,5,7,8,9}
Case II
pre_sort:{9,8,7,6,5,4,3,2,1}
sorted_subarray:{8,9}
sorted_subarray:{6,7}
sorted_subarray:{6,7,8,9}
sorted_subarray:{4,5}
sorted_subarray:{1,2}
sorted_subarray:{1,2,3}
sorted_subarray:{1,2,3,4,5}
sorted_subarray:{1,2,3,4,5,6,7,8,9}
post_sort:{1,2,3,4,5,6,7,8,9}
Case III
pre_sort:{5,5,5,5,5,5,5,5,5}
sorted_subarray:{5,5}
sorted_subarray:{5,5}
sorted_subarray:{5,5,5,5}
sorted_subarray:{5,5}
sorted_subarray:{5,5}
sorted_subarray:{5,5,5}
sorted_subarray:{5,5,5,5,5}
sorted_subarray:{5,5,5,5,5,5,5,5,5}
post_sort:{5,5,5,5,5,5,5,5,5}
Case IV
pre_sort:{1,2,3,4,5,6,7,8,9}
sorted_subarray:{1,2}
sorted_subarray:{3,4}
sorted_subarray:{1,2,3,4}
sorted_subarray:{5,6}
sorted_subarray:{8,9}
sorted_subarray:{7,8,9}
sorted_subarray:{5,6,7,8,9}
sorted_subarray:{1,2,3,4,5,6,7,8,9}
post_sort:{1,2,3,4,5,6,7,8,9}

Sunday, September 8, 2019

Treesort

Treesort implementation via
en.wikipedia.org. Treesort is O(n log n). The outer loop iterates over each element putting it into the tree which is O(n). The inner loop inserts into the tree in O(log n). To print the loop takes O(n), touching each node once. This is O(n + n log n) = O(n log n).

package algorithm;

import java.util.LinkedHashSet;
import java.util.Set;
import java.util.Stack;

public class treesort {
 public static void main(String[] args) {
  System.out.println("Case I");
  int[] numbers = new int[] {3, 7, 8, 5, 2, 1, 9, 5, 4};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  treesort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");
  
  System.out.println("Case II");
  numbers = new int[] {9, 8, 7, 6, 5, 4, 3, 2, 1};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  treesort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");

  System.out.println("Case III");
  numbers = new int[] {5, 5, 5, 5, 5, 5, 5, 5, 5};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  treesort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");

  System.out.println("Case IV");
  numbers = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  treesort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");
 }

 private static void printArray(int start, int end, int[] numbers, String text) {
  String out = "{";
  String del = "";
  for(int i=start; i < end + 1; i++) {
   out = out + del + numbers[i] + "";
   del = ",";
  }
  out = out + "}";
  System.out.println(text+":"+out);
 }

 private static void printHeap(TreeSortNode rootNode, String text) {
  Set<TreeSortNode> currentNodes = new LinkedHashSet<TreeSortNode>();
  Set<TreeSortNode> nextNodes = new LinkedHashSet<TreeSortNode>();
  
  currentNodes.add(rootNode);
  boolean foundChildNode = true;
  while(foundChildNode) {
   foundChildNode = false;
   
   String out = "";
   String del = "";
   for(TreeSortNode currentNode: currentNodes) {
    String printedValue = "" + currentNode.value;
    if(currentNode.value == null) {
     printedValue = "X";
    }
    out = out + del + printedValue;
    del = " ";
    if(currentNode.left != null) {
     nextNodes.add(currentNode.left);
     foundChildNode = true;
    } else {
     TreeSortNode placeHolder = new TreeSortNode();
     nextNodes.add(placeHolder);
    }
    if(currentNode.right != null) {
     foundChildNode = true;
     nextNodes.add(currentNode.right);
     foundChildNode = true;
    } else {
     TreeSortNode placeHolder = new TreeSortNode();
     nextNodes.add(placeHolder);
    }
   }
   System.out.println(text+":"+out);
   currentNodes = nextNodes;
   nextNodes = new LinkedHashSet<TreeSortNode>();
  }
 }
 
 // O(n log n)
 private static void treesort(int[] numbers) {
  if(numbers.length < 1) {
   return;
  }
  TreeSortNode root = new TreeSortNode();
  root.value = numbers[0];
  printHeap(root, "root");
  
  // O(n) on outer loop
  for(int i=1; i<numbers.length; i++) {
   TreeSortNode newNode = new TreeSortNode();
   newNode.value = numbers[i];
   
   insertNode(newNode, root);
  }
  
  // O(n) convert tree to array
  printTreeToArray(root, numbers);
 }

 private static void insertNode(TreeSortNode newNode, TreeSortNode root) {
  TreeSortNode parentNode = root;
  boolean inserted = false;
  
  // O(log n) on inner loop to insert into tree
  while(!inserted) {
   if(newNode.value < parentNode.value) {
    if(parentNode.left == null) {
     parentNode.left = newNode;
     inserted = true;
     printHeap(root, "left_insert");
    } else {
     parentNode = parentNode.left;
    } 
   } else { // newNode.value >= parentNode.value
    if(parentNode.right == null) {
     parentNode.right = newNode;
     inserted = true;
     printHeap(root, "right_insert");
    } else {
     parentNode = parentNode.right;
    }
   }
  }
 }

 
 private static void printTreeToArray(TreeSortNode root, int[] numbers) {
  int index = 0;
  Stack<TreeSortNode> stack = new Stack<TreeSortNode>(); // In stack if haven't printed
  TreeSortNode analyzeNode = root;
  System.out.println("root.value:"+root.value);
  
  // O(n) to traverse the tree
  while(true) {
   if(analyzeNode != null) {
    stack.push(analyzeNode);
    
    analyzeNode = analyzeNode.left;
   } else {
    if(stack.isEmpty()) {
     break;
    } else {
     analyzeNode = stack.pop();
    }
    
    numbers[index] = analyzeNode.value;
    printArray(0, index, numbers, "tree_to_array");
    index++;
    
    analyzeNode = analyzeNode.right;
   }
  }
 }

 public static class TreeSortNode {
  Integer value;
  TreeSortNode left;
  TreeSortNode right;
 }
}
Output
Case I
pre_sort:{3,7,8,5,2,1,9,5,4}
root:3
right_insert:3
right_insert:X 7
right_insert:3
right_insert:X 7
right_insert:X X X 8
left_insert:3
left_insert:X 7
left_insert:X X 5 8
left_insert:3
left_insert:2 7
left_insert:X X 5 8
left_insert:3
left_insert:2 7
left_insert:1 X 5 8
right_insert:3
right_insert:2 7
right_insert:1 X 5 8
right_insert:X X X X X X X 9
right_insert:3
right_insert:2 7
right_insert:1 X 5 8
right_insert:X X X X X 5 X 9
left_insert:3
left_insert:2 7
left_insert:1 X 5 8
left_insert:X X X X 4 5 X 9
root.value:3
tree_to_array:{1}
tree_to_array:{1,2}
tree_to_array:{1,2,3}
tree_to_array:{1,2,3,4}
tree_to_array:{1,2,3,4,5}
tree_to_array:{1,2,3,4,5,5}
tree_to_array:{1,2,3,4,5,5,7}
tree_to_array:{1,2,3,4,5,5,7,8}
tree_to_array:{1,2,3,4,5,5,7,8,9}
post_sort:{1,2,3,4,5,5,7,8,9}
Case II
pre_sort:{9,8,7,6,5,4,3,2,1}
root:9
left_insert:9
left_insert:8 X
left_insert:9
left_insert:8 X
left_insert:7 X X X
left_insert:9
left_insert:8 X
left_insert:7 X X X
left_insert:6 X X X X X X X
left_insert:9
left_insert:8 X
left_insert:7 X X X
left_insert:6 X X X X X X X
left_insert:5 X X X X X X X X X X X X X X X
left_insert:9
left_insert:8 X
left_insert:7 X X X
left_insert:6 X X X X X X X
left_insert:5 X X X X X X X X X X X X X X X
left_insert:4 X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
left_insert:9
left_insert:8 X
left_insert:7 X X X
left_insert:6 X X X X X X X
left_insert:5 X X X X X X X X X X X X X X X
left_insert:4 X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
left_insert:3 X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
left_insert:9
left_insert:8 X
left_insert:7 X X X
left_insert:6 X X X X X X X
left_insert:5 X X X X X X X X X X X X X X X
left_insert:4 X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
left_insert:3 X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
left_insert:2 X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
left_insert:9
left_insert:8 X
left_insert:7 X X X
left_insert:6 X X X X X X X
left_insert:5 X X X X X X X X X X X X X X X
left_insert:4 X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
left_insert:3 X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
left_insert:2 X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
left_insert:1 X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
root.value:9
tree_to_array:{1}
tree_to_array:{1,2}
tree_to_array:{1,2,3}
tree_to_array:{1,2,3,4}
tree_to_array:{1,2,3,4,5}
tree_to_array:{1,2,3,4,5,6}
tree_to_array:{1,2,3,4,5,6,7}
tree_to_array:{1,2,3,4,5,6,7,8}
tree_to_array:{1,2,3,4,5,6,7,8,9}
post_sort:{1,2,3,4,5,6,7,8,9}
Case III
pre_sort:{5,5,5,5,5,5,5,5,5}
root:5
right_insert:5
right_insert:X 5
right_insert:5
right_insert:X 5
right_insert:X X X 5
right_insert:5
right_insert:X 5
right_insert:X X X 5
right_insert:X X X X X X X 5
right_insert:5
right_insert:X 5
right_insert:X X X 5
right_insert:X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X 5
right_insert:5
right_insert:X 5
right_insert:X X X 5
right_insert:X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 5
right_insert:5
right_insert:X 5
right_insert:X X X 5
right_insert:X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 5
right_insert:5
right_insert:X 5
right_insert:X X X 5
right_insert:X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 5
right_insert:5
right_insert:X 5
right_insert:X X X 5
right_insert:X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 5
root.value:5
tree_to_array:{5}
tree_to_array:{5,5}
tree_to_array:{5,5,5}
tree_to_array:{5,5,5,5}
tree_to_array:{5,5,5,5,5}
tree_to_array:{5,5,5,5,5,5}
tree_to_array:{5,5,5,5,5,5,5}
tree_to_array:{5,5,5,5,5,5,5,5}
tree_to_array:{5,5,5,5,5,5,5,5,5}
post_sort:{5,5,5,5,5,5,5,5,5}
Case IV
pre_sort:{1,2,3,4,5,6,7,8,9}
root:1
right_insert:1
right_insert:X 2
right_insert:1
right_insert:X 2
right_insert:X X X 3
right_insert:1
right_insert:X 2
right_insert:X X X 3
right_insert:X X X X X X X 4
right_insert:1
right_insert:X 2
right_insert:X X X 3
right_insert:X X X X X X X 4
right_insert:X X X X X X X X X X X X X X X 5
right_insert:1
right_insert:X 2
right_insert:X X X 3
right_insert:X X X X X X X 4
right_insert:X X X X X X X X X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 6
right_insert:1
right_insert:X 2
right_insert:X X X 3
right_insert:X X X X X X X 4
right_insert:X X X X X X X X X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 6
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 7
right_insert:1
right_insert:X 2
right_insert:X X X 3
right_insert:X X X X X X X 4
right_insert:X X X X X X X X X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 6
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 7
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 8
right_insert:1
right_insert:X 2
right_insert:X X X 3
right_insert:X X X X X X X 4
right_insert:X X X X X X X X X X X X X X X 5
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 6
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 7
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 8
right_insert:X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 9
root.value:1
tree_to_array:{1}
tree_to_array:{1,2}
tree_to_array:{1,2,3}
tree_to_array:{1,2,3,4}
tree_to_array:{1,2,3,4,5}
tree_to_array:{1,2,3,4,5,6}
tree_to_array:{1,2,3,4,5,6,7}
tree_to_array:{1,2,3,4,5,6,7,8}
tree_to_array:{1,2,3,4,5,6,7,8,9}
post_sort:{1,2,3,4,5,6,7,8,9}

Saturday, September 7, 2019

Heapsort

This implementation comes from en.wikipedia.org.  The outer loop runs O(n) times and the inner loop is O(log n) so the whole algorithm is O(n log n).

In general, quicksort would be faster to implement in practice because heapsort is actually not a divide and conquer algorithm, which is true O(log n).

Here, we implemented the sift down method which repairs a broken heap.  This is O(n/2*2) since the inner loop iterates through all parent nodes (only half the nodes) but compares to both children.  The number of parent nodes decreases by 1 each time the inner loop executes.  This implementation is O(n^2/2) = O(n^2).

--------
-------
------
-----
----
---
--
-

package algorithm;

public class heapsort {
 public static void main(String[] args) {
  System.out.println("Case I");
  int[] numbers = new int[] {3, 7, 8, 5, 2, 1, 9, 5, 4};
  printArrayAndHeap(0, numbers.length - 1, numbers, "pre_sort");
  heapsort(numbers);
  printArrayAndHeap(0, numbers.length - 1, numbers, "post_sort");

  System.out.println("Case II");
  numbers = new int[] {9, 8, 7, 6, 5, 4, 3, 2, 1};
  printArrayAndHeap(0, numbers.length - 1, numbers, "pre_sort");
  heapsort(numbers);
  printArrayAndHeap(0, numbers.length - 1, numbers, "post_sort");

  System.out.println("Case III");
  numbers = new int[] {5, 5, 5, 5, 5, 5, 5, 5, 5};
  printArrayAndHeap(0, numbers.length - 1, numbers, "pre_sort");
  heapsort(numbers);
  printArrayAndHeap(0, numbers.length - 1, numbers, "post_sort");

  System.out.println("Case IV");
  numbers = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
  printArrayAndHeap(0, numbers.length - 1, numbers, "pre_sort");
  heapsort(numbers);
  printArrayAndHeap(0, numbers.length - 1, numbers, "post_sort");
 }

 private static void printArrayAndHeap(int i, int j, int[] numbers, String text) {
  printArray(i,j,numbers, text);
  printHeap(i,j,numbers);
 }

 private static void printArray(int start, int end, int[] numbers, String text) {
  String out = "{";
  String del = "";
  for(int i=start; i < end + 1; i++) {
   out = out + del + numbers[i] + "";
   del = ",";
  }
  out = out + "}";
  System.out.println(text+":"+out);
 }

 private static void printHeap(int start, int end, int[] numbers) {
  int depth = (int) Math.ceil((Math.log(end+2)/Math.log(2)));
  int currentLevel = 0;

  while(currentLevel < depth) {
   int firstAtCurrentLevel = (int) Math.pow(2, currentLevel) - 1;
   int firstAtNextLevel = (int) Math.pow(2, currentLevel + 1) - 1;
   
   String heapout = "";
   for(int index = firstAtCurrentLevel; index < firstAtNextLevel; index++) {
    if(index <= end) {
     heapout = heapout + " " + numbers[index];
    }
   }
   System.out.println("level:"+currentLevel+" heap:"+heapout);
   currentLevel++;
  }
 }

 // O(n^2)
 private static void heapsort(int[] numbers) {
  // O(n) on outer loop
  for(int i=0; i<numbers.length; i++) {
   bubbleUpLargestAndPlaceAtEnd(0, numbers.length - 1 - i, numbers);
  }
 }

 private static void bubbleUpLargestAndPlaceAtEnd(int start, int end, int[] numbers) {
  if(end == 0) {
   return;
  }
  int startingIndex = (int) Math.floor(end+1/2) - 1;
  
  // O(n) on inner loop - Though n decreases - Fixing broken heap is O(n)
  for(int i=startingIndex; i > -1; i--) {
   swapParentWithLargestChild(start, end, numbers, i);
  }
  
  // Move largest from 0th place to end of array
  int largest = numbers[start];
  int last = numbers[end];
  numbers[end] = largest;
  numbers[start] = last; 
  printArrayAndHeap(start, end, numbers, "put_largest_at_end");
 }

 private static void swapParentWithLargestChild(int start, int end,
  int[] numbers, int i) {
  int parent = numbers[i];
  if(i*2 + 2 <= end) {
   int rightChild = numbers[i*2 + 2];
   if(rightChild > parent) {
    numbers[i] = rightChild;
    numbers[i*2 + 2] = parent;
    parent = rightChild;
    printArrayAndHeap(start, end, numbers, "swap_right_child");
   }
  }
  if(i*2 + 1 <= end) {
   int leftChild = numbers[i*2 + 1];
   if(leftChild > parent) {
    numbers[i] = leftChild;
    numbers[i*2 + 1] = parent;
    printArrayAndHeap(start, end, numbers, "swap_left_child");
   }
  }
 }
}
Output
Case I
pre_sort:{3,7,8,5,2,1,9,5,4}
level:0 heap: 3
level:1 heap: 7 8
level:2 heap: 5 2 1 9
level:3 heap: 5 4
swap_right_child:{3,7,9,5,2,1,8,5,4}
level:0 heap: 3
level:1 heap: 7 9
level:2 heap: 5 2 1 8
level:3 heap: 5 4
swap_right_child:{9,7,3,5,2,1,8,5,4}
level:0 heap: 9
level:1 heap: 7 3
level:2 heap: 5 2 1 8
level:3 heap: 5 4
put_largest_at_end:{4,7,3,5,2,1,8,5,9}
level:0 heap: 4
level:1 heap: 7 3
level:2 heap: 5 2 1 8
level:3 heap: 5 9
swap_right_child:{4,7,8,5,2,1,3,5}
level:0 heap: 4
level:1 heap: 7 8
level:2 heap: 5 2 1 3
level:3 heap: 5
swap_right_child:{8,7,4,5,2,1,3,5}
level:0 heap: 8
level:1 heap: 7 4
level:2 heap: 5 2 1 3
level:3 heap: 5
put_largest_at_end:{5,7,4,5,2,1,3,8}
level:0 heap: 5
level:1 heap: 7 4
level:2 heap: 5 2 1 3
level:3 heap: 8
swap_left_child:{7,5,4,5,2,1,3}
level:0 heap: 7
level:1 heap: 5 4
level:2 heap: 5 2 1 3
put_largest_at_end:{3,5,4,5,2,1,7}
level:0 heap: 3
level:1 heap: 5 4
level:2 heap: 5 2 1 7
swap_right_child:{4,5,3,5,2,1}
level:0 heap: 4
level:1 heap: 5 3
level:2 heap: 5 2 1
swap_left_child:{5,4,3,5,2,1}
level:0 heap: 5
level:1 heap: 4 3
level:2 heap: 5 2 1
put_largest_at_end:{1,4,3,5,2,5}
level:0 heap: 1
level:1 heap: 4 3
level:2 heap: 5 2 5
swap_left_child:{1,5,3,4,2}
level:0 heap: 1
level:1 heap: 5 3
level:2 heap: 4 2
swap_right_child:{3,5,1,4,2}
level:0 heap: 3
level:1 heap: 5 1
level:2 heap: 4 2
swap_left_child:{5,3,1,4,2}
level:0 heap: 5
level:1 heap: 3 1
level:2 heap: 4 2
put_largest_at_end:{2,3,1,4,5}
level:0 heap: 2
level:1 heap: 3 1
level:2 heap: 4 5
swap_left_child:{2,4,1,3}
level:0 heap: 2
level:1 heap: 4 1
level:2 heap: 3
swap_left_child:{4,2,1,3}
level:0 heap: 4
level:1 heap: 2 1
level:2 heap: 3
put_largest_at_end:{3,2,1,4}
level:0 heap: 3
level:1 heap: 2 1
level:2 heap: 4
put_largest_at_end:{1,2,3}
level:0 heap: 1
level:1 heap: 2 3
swap_left_child:{2,1}
level:0 heap: 2
level:1 heap: 1
put_largest_at_end:{1,2}
level:0 heap: 1
level:1 heap: 2
post_sort:{1,2,3,4,5,5,7,8,9}
level:0 heap: 1
level:1 heap: 2 3
level:2 heap: 4 5 5 7
level:3 heap: 8 9
Case II
pre_sort:{9,8,7,6,5,4,3,2,1}
level:0 heap: 9
level:1 heap: 8 7
level:2 heap: 6 5 4 3
level:3 heap: 2 1
put_largest_at_end:{1,8,7,6,5,4,3,2,9}
level:0 heap: 1
level:1 heap: 8 7
level:2 heap: 6 5 4 3
level:3 heap: 2 9
swap_right_child:{7,8,1,6,5,4,3,2}
level:0 heap: 7
level:1 heap: 8 1
level:2 heap: 6 5 4 3
level:3 heap: 2
swap_left_child:{8,7,1,6,5,4,3,2}
level:0 heap: 8
level:1 heap: 7 1
level:2 heap: 6 5 4 3
level:3 heap: 2
put_largest_at_end:{2,7,1,6,5,4,3,8}
level:0 heap: 2
level:1 heap: 7 1
level:2 heap: 6 5 4 3
level:3 heap: 8
swap_right_child:{2,7,3,6,5,4,1}
level:0 heap: 2
level:1 heap: 7 3
level:2 heap: 6 5 4 1
swap_left_child:{2,7,4,6,5,3,1}
level:0 heap: 2
level:1 heap: 7 4
level:2 heap: 6 5 3 1
swap_right_child:{4,7,2,6,5,3,1}
level:0 heap: 4
level:1 heap: 7 2
level:2 heap: 6 5 3 1
swap_left_child:{7,4,2,6,5,3,1}
level:0 heap: 7
level:1 heap: 4 2
level:2 heap: 6 5 3 1
put_largest_at_end:{1,4,2,6,5,3,7}
level:0 heap: 1
level:1 heap: 4 2
level:2 heap: 6 5 3 7
swap_left_child:{1,4,3,6,5,2}
level:0 heap: 1
level:1 heap: 4 3
level:2 heap: 6 5 2
swap_right_child:{1,5,3,6,4,2}
level:0 heap: 1
level:1 heap: 5 3
level:2 heap: 6 4 2
swap_left_child:{1,6,3,5,4,2}
level:0 heap: 1
level:1 heap: 6 3
level:2 heap: 5 4 2
swap_right_child:{3,6,1,5,4,2}
level:0 heap: 3
level:1 heap: 6 1
level:2 heap: 5 4 2
swap_left_child:{6,3,1,5,4,2}
level:0 heap: 6
level:1 heap: 3 1
level:2 heap: 5 4 2
put_largest_at_end:{2,3,1,5,4,6}
level:0 heap: 2
level:1 heap: 3 1
level:2 heap: 5 4 6
swap_right_child:{2,4,1,5,3}
level:0 heap: 2
level:1 heap: 4 1
level:2 heap: 5 3
swap_left_child:{2,5,1,4,3}
level:0 heap: 2
level:1 heap: 5 1
level:2 heap: 4 3
swap_left_child:{5,2,1,4,3}
level:0 heap: 5
level:1 heap: 2 1
level:2 heap: 4 3
put_largest_at_end:{3,2,1,4,5}
level:0 heap: 3
level:1 heap: 2 1
level:2 heap: 4 5
swap_left_child:{3,4,1,2}
level:0 heap: 3
level:1 heap: 4 1
level:2 heap: 2
swap_left_child:{4,3,1,2}
level:0 heap: 4
level:1 heap: 3 1
level:2 heap: 2
put_largest_at_end:{2,3,1,4}
level:0 heap: 2
level:1 heap: 3 1
level:2 heap: 4
swap_left_child:{3,2,1}
level:0 heap: 3
level:1 heap: 2 1
put_largest_at_end:{1,2,3}
level:0 heap: 1
level:1 heap: 2 3
swap_left_child:{2,1}
level:0 heap: 2
level:1 heap: 1
put_largest_at_end:{1,2}
level:0 heap: 1
level:1 heap: 2
post_sort:{1,2,3,4,5,6,7,8,9}
level:0 heap: 1
level:1 heap: 2 3
level:2 heap: 4 5 6 7
level:3 heap: 8 9
Case III
pre_sort:{5,5,5,5,5,5,5,5,5}
level:0 heap: 5
level:1 heap: 5 5
level:2 heap: 5 5 5 5
level:3 heap: 5 5
put_largest_at_end:{5,5,5,5,5,5,5,5,5}
level:0 heap: 5
level:1 heap: 5 5
level:2 heap: 5 5 5 5
level:3 heap: 5 5
put_largest_at_end:{5,5,5,5,5,5,5,5}
level:0 heap: 5
level:1 heap: 5 5
level:2 heap: 5 5 5 5
level:3 heap: 5
put_largest_at_end:{5,5,5,5,5,5,5}
level:0 heap: 5
level:1 heap: 5 5
level:2 heap: 5 5 5 5
put_largest_at_end:{5,5,5,5,5,5}
level:0 heap: 5
level:1 heap: 5 5
level:2 heap: 5 5 5
put_largest_at_end:{5,5,5,5,5}
level:0 heap: 5
level:1 heap: 5 5
level:2 heap: 5 5
put_largest_at_end:{5,5,5,5}
level:0 heap: 5
level:1 heap: 5 5
level:2 heap: 5
put_largest_at_end:{5,5,5}
level:0 heap: 5
level:1 heap: 5 5
put_largest_at_end:{5,5}
level:0 heap: 5
level:1 heap: 5
post_sort:{5,5,5,5,5,5,5,5,5}
level:0 heap: 5
level:1 heap: 5 5
level:2 heap: 5 5 5 5
level:3 heap: 5 5
Case IV
pre_sort:{1,2,3,4,5,6,7,8,9}
level:0 heap: 1
level:1 heap: 2 3
level:2 heap: 4 5 6 7
level:3 heap: 8 9
swap_right_child:{1,2,3,9,5,6,7,8,4}
level:0 heap: 1
level:1 heap: 2 3
level:2 heap: 9 5 6 7
level:3 heap: 8 4
swap_right_child:{1,2,7,9,5,6,3,8,4}
level:0 heap: 1
level:1 heap: 2 7
level:2 heap: 9 5 6 3
level:3 heap: 8 4
swap_right_child:{1,5,7,9,2,6,3,8,4}
level:0 heap: 1
level:1 heap: 5 7
level:2 heap: 9 2 6 3
level:3 heap: 8 4
swap_left_child:{1,9,7,5,2,6,3,8,4}
level:0 heap: 1
level:1 heap: 9 7
level:2 heap: 5 2 6 3
level:3 heap: 8 4
swap_right_child:{7,9,1,5,2,6,3,8,4}
level:0 heap: 7
level:1 heap: 9 1
level:2 heap: 5 2 6 3
level:3 heap: 8 4
swap_left_child:{9,7,1,5,2,6,3,8,4}
level:0 heap: 9
level:1 heap: 7 1
level:2 heap: 5 2 6 3
level:3 heap: 8 4
put_largest_at_end:{4,7,1,5,2,6,3,8,9}
level:0 heap: 4
level:1 heap: 7 1
level:2 heap: 5 2 6 3
level:3 heap: 8 9
swap_left_child:{4,7,1,8,2,6,3,5}
level:0 heap: 4
level:1 heap: 7 1
level:2 heap: 8 2 6 3
level:3 heap: 5
swap_right_child:{4,7,3,8,2,6,1,5}
level:0 heap: 4
level:1 heap: 7 3
level:2 heap: 8 2 6 1
level:3 heap: 5
swap_left_child:{4,7,6,8,2,3,1,5}
level:0 heap: 4
level:1 heap: 7 6
level:2 heap: 8 2 3 1
level:3 heap: 5
swap_left_child:{4,8,6,7,2,3,1,5}
level:0 heap: 4
level:1 heap: 8 6
level:2 heap: 7 2 3 1
level:3 heap: 5
swap_right_child:{6,8,4,7,2,3,1,5}
level:0 heap: 6
level:1 heap: 8 4
level:2 heap: 7 2 3 1
level:3 heap: 5
swap_left_child:{8,6,4,7,2,3,1,5}
level:0 heap: 8
level:1 heap: 6 4
level:2 heap: 7 2 3 1
level:3 heap: 5
put_largest_at_end:{5,6,4,7,2,3,1,8}
level:0 heap: 5
level:1 heap: 6 4
level:2 heap: 7 2 3 1
level:3 heap: 8
swap_left_child:{5,7,4,6,2,3,1}
level:0 heap: 5
level:1 heap: 7 4
level:2 heap: 6 2 3 1
swap_left_child:{7,5,4,6,2,3,1}
level:0 heap: 7
level:1 heap: 5 4
level:2 heap: 6 2 3 1
put_largest_at_end:{1,5,4,6,2,3,7}
level:0 heap: 1
level:1 heap: 5 4
level:2 heap: 6 2 3 7
swap_left_child:{1,6,4,5,2,3}
level:0 heap: 1
level:1 heap: 6 4
level:2 heap: 5 2 3
swap_right_child:{4,6,1,5,2,3}
level:0 heap: 4
level:1 heap: 6 1
level:2 heap: 5 2 3
swap_left_child:{6,4,1,5,2,3}
level:0 heap: 6
level:1 heap: 4 1
level:2 heap: 5 2 3
put_largest_at_end:{3,4,1,5,2,6}
level:0 heap: 3
level:1 heap: 4 1
level:2 heap: 5 2 6
swap_left_child:{3,5,1,4,2}
level:0 heap: 3
level:1 heap: 5 1
level:2 heap: 4 2
swap_left_child:{5,3,1,4,2}
level:0 heap: 5
level:1 heap: 3 1
level:2 heap: 4 2
put_largest_at_end:{2,3,1,4,5}
level:0 heap: 2
level:1 heap: 3 1
level:2 heap: 4 5
swap_left_child:{2,4,1,3}
level:0 heap: 2
level:1 heap: 4 1
level:2 heap: 3
swap_left_child:{4,2,1,3}
level:0 heap: 4
level:1 heap: 2 1
level:2 heap: 3
put_largest_at_end:{3,2,1,4}
level:0 heap: 3
level:1 heap: 2 1
level:2 heap: 4
put_largest_at_end:{1,2,3}
level:0 heap: 1
level:1 heap: 2 3
swap_left_child:{2,1}
level:0 heap: 2
level:1 heap: 1
put_largest_at_end:{1,2}
level:0 heap: 1
level:1 heap: 2
post_sort:{1,2,3,4,5,6,7,8,9}
level:0 heap: 1
level:1 heap: 2 3
level:2 heap: 4 5 6 7
level:3 heap: 8 9

Bubblesort

Bubble sort based on en.wikipedia.org. This algorithm is O(n^2) because the inner loop has O(n) comparisons and the outer loop runs O(n) times.  The inner loop can be optimized to reduce by 1 each time.  Also, when no swaps are made, it can exit.  This is O(n^2/2 - k^2/2) = O(n^2).

--------
-------
------
-----
----

package algorithm;

public class bubblesort {
 public static void main(String[] args) {
  System.out.println("Case I");
  int[] numbers = new int[] {3, 7, 8, 5, 2, 1, 9, 5, 4};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  bubblesort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");
  
  System.out.println("Case II");
  numbers = new int[] {9, 8, 7, 6, 5, 4, 3, 2, 1};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  bubblesort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");

  System.out.println("Case III");
  numbers = new int[] {5, 5, 5, 5, 5, 5, 5, 5, 5};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  bubblesort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");

  System.out.println("Case IV");
  numbers = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  bubblesort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");
 }

 private static void printArray(int start, int end, int[] numbers, String text) {
  String out = "{";
  String del = "";
  for(int i=start; i < end + 1; i++) {
   out = out + del + numbers[i] + "";
   del = ",";
  }
  out = out + "}";
  System.out.println(text+":"+out);
 }
 
 // O(n^2)
 private static void bubblesort(int[] numbers) {
  int n = numbers.length; // First optimization is that nth largest number is put in place on nth iteration, so no need to check last n after n iterations
  boolean swapped = false; // Second optimization is that if no swap occurs, the array is already sorted, so can exit
  
  // O(n)
  for(int i=0; i < numbers.length; i++) {
   swapped = lookForSwaps(numbers, n);
   
   if(!swapped) {
    return;
   }
   n = n - 1;
  }
 }

 private static boolean lookForSwaps(int[] numbers, int n) {
  int first = numbers[0]; 
  boolean swapped = false;
  
  // O(n) on inner loop - Though n decreases
  for(int j=1; j < n; j++) {
   int second = numbers[j];
   if(first > second) {
    swap(numbers, j, first, second);
    swapped = true;
   } else {
    first = second;
   }
  }
  
  return swapped;
 }

 private static void swap(int[] numbers, int j, int first,
   int second) {
  numbers[j-1] = second;
  numbers[j] = first;
  printArray(0, numbers.length - 1, numbers, "swapped");
 }
}
Output
Case I
pre_sort:{3,7,8,5,2,1,9,5,4}
swapped:{3,7,5,8,2,1,9,5,4}
swapped:{3,7,5,2,8,1,9,5,4}
swapped:{3,7,5,2,1,8,9,5,4}
swapped:{3,7,5,2,1,8,5,9,4}
swapped:{3,7,5,2,1,8,5,4,9}
swapped:{3,5,7,2,1,8,5,4,9}
swapped:{3,5,2,7,1,8,5,4,9}
swapped:{3,5,2,1,7,8,5,4,9}
swapped:{3,5,2,1,7,5,8,4,9}
swapped:{3,5,2,1,7,5,4,8,9}
swapped:{3,2,5,1,7,5,4,8,9}
swapped:{3,2,1,5,7,5,4,8,9}
swapped:{3,2,1,5,5,7,4,8,9}
swapped:{3,2,1,5,5,4,7,8,9}
swapped:{2,3,1,5,5,4,7,8,9}
swapped:{2,1,3,5,5,4,7,8,9}
swapped:{2,1,3,5,4,5,7,8,9}
swapped:{1,2,3,5,4,5,7,8,9}
swapped:{1,2,3,4,5,5,7,8,9}
post_sort:{1,2,3,4,5,5,7,8,9}
Case II
pre_sort:{9,8,7,6,5,4,3,2,1}
swapped:{8,9,7,6,5,4,3,2,1}
swapped:{8,7,9,6,5,4,3,2,1}
swapped:{8,7,6,9,5,4,3,2,1}
swapped:{8,7,6,5,9,4,3,2,1}
swapped:{8,7,6,5,4,9,3,2,1}
swapped:{8,7,6,5,4,3,9,2,1}
swapped:{8,7,6,5,4,3,2,9,1}
swapped:{8,7,6,5,4,3,2,1,9}
swapped:{7,8,6,5,4,3,2,1,9}
swapped:{7,6,8,5,4,3,2,1,9}
swapped:{7,6,5,8,4,3,2,1,9}
swapped:{7,6,5,4,8,3,2,1,9}
swapped:{7,6,5,4,3,8,2,1,9}
swapped:{7,6,5,4,3,2,8,1,9}
swapped:{7,6,5,4,3,2,1,8,9}
swapped:{6,7,5,4,3,2,1,8,9}
swapped:{6,5,7,4,3,2,1,8,9}
swapped:{6,5,4,7,3,2,1,8,9}
swapped:{6,5,4,3,7,2,1,8,9}
swapped:{6,5,4,3,2,7,1,8,9}
swapped:{6,5,4,3,2,1,7,8,9}
swapped:{5,6,4,3,2,1,7,8,9}
swapped:{5,4,6,3,2,1,7,8,9}
swapped:{5,4,3,6,2,1,7,8,9}
swapped:{5,4,3,2,6,1,7,8,9}
swapped:{5,4,3,2,1,6,7,8,9}
swapped:{4,5,3,2,1,6,7,8,9}
swapped:{4,3,5,2,1,6,7,8,9}
swapped:{4,3,2,5,1,6,7,8,9}
swapped:{4,3,2,1,5,6,7,8,9}
swapped:{3,4,2,1,5,6,7,8,9}
swapped:{3,2,4,1,5,6,7,8,9}
swapped:{3,2,1,4,5,6,7,8,9}
swapped:{2,3,1,4,5,6,7,8,9}
swapped:{2,1,3,4,5,6,7,8,9}
swapped:{1,2,3,4,5,6,7,8,9}
post_sort:{1,2,3,4,5,6,7,8,9}
Case III
pre_sort:{5,5,5,5,5,5,5,5,5}
post_sort:{5,5,5,5,5,5,5,5,5}
Case IV
pre_sort:{1,2,3,4,5,6,7,8,9}
post_sort:{1,2,3,4,5,6,7,8,9}