package random; import java.util.Arrays; public class InsertionSort { public int[] insertionSort(int[] arr){ for(int i = 1; i < arr.length; i++){ for(int j = i; j > 0; j--){//pay attention to this inner for loop, it's decrementing j until it equals to zero if(arr[j] < arr[j-1]){ int temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; } } } return arr; } public static void main(String...strings){ int[] arr = new int[]{8, 3, 2, 4, 5, 9, 4, 1, 9, 9}; InsertionSort test = new InsertionSort(); System.out.println(Arrays.toString(test.insertionSort(arr))); } }

# Month: May 2016

## QuickSort

QuickSort doesn’t require extra space, average time is O(nlgn).

Idea:

- Pick a pivot and sort all elements in the array that are smaller than the pivot to the left of the chosen pivot, and all that are bigger than the pivot to the right of it
- recursively sort two sublists
- Note: the pivot could be chosen in multiple ways:
- you can pick
*first*element in the array - you can pick
*last*element in the array - you can pick
*median*element in the array - you can pick
*random*element in the array

- you can pick
- The pivot you pick could result in completely different sorting efficiency under extreme cases: http://stackoverflow.com/questions/2415193/worst-case-for-quicksort-when-can-it-occur

The following *partition()* method takes the last element as the pivot. In its *partition() *method: it sets the last element as the pivot, then it keeps an index i = low-1, then use another index j to loop through all elements from *low* to *high-1*, when we find any element nums[j] that is smaller than or equal to pivot (i.e. nums[high]), ** we increment i by 1 first**, then we swap nums[j] with nums[i], notice, we swap nums[j] with

*, not with nums[high] or anything else, we swap nums[high] after we finish iterating through*

**nums[i]***low*to

*high-1*, this is to do this: place all elements that are smaller than the pivot to the

*of the pivot, after iterating through from*

**left***low*to

*high-1*, we swap nums[i+1] with nums[high], this is to place nums[high] (i.e. current pivot) to the correct position, then we return i+1 as the pivot as all elements from

*low*to

*i*are sorted already.

I put my *partition()* function into this site and it’s accepted: http://www.practice.geeksforgeeks.org/problem-page.php?pid=700151

int[] quickSort_20160628(int[] nums){ quickSort_20160628(nums, 0, nums.length-1); return nums; } void quickSort_20160628(int[] nums, int low, int high) { if(low < high){ int pi = partition_20160628(nums, low, high); quickSort_20160628(nums, low, pi-1); quickSort_20160628(nums, pi+1, high); } } int partition_20160628(int[] nums, int low, int high) { int pivot = nums[high]; int i = low-1; for(int j = low; j <= high-1; j++){ if(nums[j] <= pivot){ i++; int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } int temp = nums[i+1]; nums[i+1] = nums[high]; nums[high] = temp; return i+1; }

Then, just out of curiosity, I followed the same pattern, implemented the *partition()* function by picking the first element as the pivot, similar idea in the *partition()* function: similar to the *partition() *function in choosing last as pivot where it uses a for loop to find all elements that are smaller than pivot to place them to the left most possible, this *partition_pivot_first_20160628*I() function uses a for loop to find all elements that are bigger than the chosen pivot and places them to the right most possible.

Cool! I figured this partition method myself by completely understanding it first. Praise the Lord!

Also, don’t forget to put if(low < high){} at the main function!!! Otherwise, it won’t work!

It’s also accepted here: http://www.practice.geeksforgeeks.org/problem-page.php?pid=700151

int[] quickSort_pivot_first_20160628(int[] nums){ quickSort_pivot_first_20160628(nums, 0, nums.length-1); return nums; } private void quickSort_pivot_first_20160628(int[] nums, int low, int high) { if (low < high) { int pi = partition_pivot_first_20160628(nums, low, high); quickSort_pivot_first_20160628(nums, low, pi - 1); quickSort_pivot_first_20160628(nums, pi + 1, high); } } private int partition_pivot_first_20160628(int[] nums, int low, int high) { int pivot = nums[low]; int i = high+1; for(int j = high; j > low; j--){ if(nums[j] > pivot){ i--; int temp = nums[j]; nums[j] = nums[i]; nums[i] = temp; } } int temp = nums[low]; nums[low] = nums[i-1]; nums[i-1] = temp; return i-1; }

Implement quickSort() that takes median element as the pivot, it’s a bit different from the previous two, just in the way it’s written: it doesn’t use one more help function: *partition()*, instead, it uses just one function which does both recursion and partition. The fundamental idea behind the three is definitely the same: keep picking one element as pivot, keep placing all elements in the array that are smaller than the pivot to the left of the pivot and those that are bigger to the right.

int[] quickSort_pivot_median_20160628(int[] nums){ quickSort_pivot_median_20160628(nums, 0, nums.length-1); return nums; } void quickSort_pivot_median_20160628(int[] nums, int low, int high) { if(nums == null || nums.length == 0) return ; if(low >= high) return; int i = low, j = high, mid = (low+high)/2, pivot = nums[mid]; while(i <= j){ while(nums[i] < pivot) i++; while(nums[j] > pivot) j--; if(i <= j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; i++; j--; } } if(low < j) quickSort_pivot_median_20160628(nums, low, j); if(i < high) quickSort_pivot_median_20160628(nums, i, high); }

## Binary Tree Level Order Traversal II

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

Wrote again bug free on 8/12/2016, here’s the code.

I did it again, completely by myself, on 07/02/2016 and made it AC’ed. Cool!

public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> result = new ArrayList<List<Integer>>(); Queue<TreeNode> q = new LinkedList<TreeNode>(); q.offer(root); while(!q.isEmpty() && root != null){ List<Integer> level = new ArrayList<Integer>(); int size = q.size(); for(int i = 0; i < size; i++){ TreeNode node = q.poll(); level.add(node.val); if(node.left != null) q.offer(node.left); if(node.right != null) q.offer(node.right); } result.add(level); } List<List<Integer>> realResult = new ArrayList<List<Integer>>(); for(int i = result.size()-1; i >= 0; i--){ realResult.add(result.get(i)); } return realResult; }

Same as I, just reverse the result before returning it.

public class Solution { public List&lt;List&lt;Integer&gt;&gt; levelOrderBottom(TreeNode root) { List&lt;List&lt;Integer&gt;&gt; result = new ArrayList&lt;List&lt;Integer&gt;&gt;(); if(root == null) return result; Queue&lt;TreeNode&gt; q = new LinkedList&lt;TreeNode&gt;(); q.offer(root); int currentLen = 0; while(!q.isEmpty()){ List&lt;Integer&gt; row = new ArrayList&lt;Integer&gt;(); currentLen = q.size(); for(int i = 0; i &lt; currentLen; i++){ TreeNode peek = q.poll(); row.add(peek.val); if(peek.left != null) q.offer(peek.left); if(peek.right != null) q.offer(peek.right); } result.add(row); } Collections.reverse(result); return result; } }

## Binary Tree Level Order Traversal

https://leetcode.com/problems/binary-tree-level-order-traversal/

Wrote again bug-free on 8/12/2016, here’s the code.

After a good month time, after deeply undestanding DFS and recursion, without looking at the previous code, I implemented the code again on 07/02/2016 and made it accepted the first time I try it! Praise the Lord! Just sort out the logic, the code flows out very naturally!

public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if(root == null) return result; Queue<TreeNode> q = new LinkedList<TreeNode>(); q.offer(root); while(!q.isEmpty() && root != null){ List<Integer> levelList = new ArrayList<Integer>(); int qSize = q.size(); for(int i = 0; i < qSize; i++){ TreeNode node = q.poll(); levelList.add(node.val); if(node.left != null) q.offer(node.left); if(node.right != null) q.offer(node.right); } result.add(levelList); } return result; }

Thanks to this awesome clear and easy to follow post: https://leetcode.com/discuss/35552/share-my-clean-and-easy-java-solution

A typical BFS solution, using a Queue to hold each node’s left and right children.

public class Solution { public List&lt;List&lt;Integer&gt;&gt; levelOrder(TreeNode root) { List&lt;List&lt;Integer&gt;&gt; result = new ArrayList&lt;List&lt;Integer&gt;&gt;(); if(root == null) return result; Queue&lt;TreeNode&gt; q = new LinkedList&lt;TreeNode&gt;(); int currentLen = 0; q.offer(root); while(!q.isEmpty()){ currentLen = q.size(); List&lt;Integer&gt; row = new ArrayList&lt;Integer&gt;(); for(int i = 0; i &lt; currentLen; i++){ TreeNode peek = q.poll(); row.add(peek.val); if(peek.left != null) q.offer(peek.left); if(peek.right != null) q.offer(peek.right); } result.add(row); } return result; } }

## SOA – Service Oriented Architecture

https://en.wikipedia.org/wiki/Service-oriented_architecture

“A service-oriented architecture (SOA) is an architectural pattern in computer software design in which application components provide services to other components via a communications protocol, typically over a network. The principles of service-orientation are independent of any vendor, product or technology.

A service is a self-contained unit of functionality, such as retrieving an online bank statement.”

**Advantages**

❑ Service Reusability

In SOA, an application is built by assembling small, self-contained, and loosely coupled pieces of functionality. Therefore, the services can be reused in multiple applications independent of their interactions with other services.

❑ Easy Maintainability

Since a service is an independent entity, it can be easily updated or maintained without having to worry about other services. Large, complex applications can thus be managed easily.

❑ Greater Reliability

SOA-based applications are more reliable since small, independent services are easier to test and debug as compared to massive chunks of code.

❑ Location Independence

The services are usually published to a directory where consumers can look them up. This approach allows a service to change its location at any time. However, the consumers are always able to locate their requested service through the directory look up.

❑ Improved Scalability and Availability

Multiple instances of a single service can run on different servers at the same time. This increases scalability and availability of the service.

❑ Improved Software Quality

Since services can be reused, there is no scope for redundant functionality. This helps reduce errors due to inconsistent data, and thereby improves the quality of code.

❑ Platform Independence

SOA facilitates the development of a complex product by integrating different products from different vendors independent of the platform and technology.

❑ Increased Productivity

Developers can reuse existing legacy applications and build additional functionality without having to develop the entire thing from scratch. This increases the developers’ productivity, and at the same time, substantially reduces the cost of developing an application.

**Disadvantages**

❑ Increased Overhead

Every time a service interacts with another service, complete validation of every input parameter takes place. This increases the response time and machine load, and thereby reduces the overall performance.

❑ Complex Service Management

The service needs to ensure that messages have been delivered in a timely manner. But as services keep exchanging messages to perform tasks, the number of these messages can go into millions even for a single application. This poses a big challenge to manage such a huge population of services.

❑ High Investment Cost

Implementation of SOA requires a large upfront investment by means of technology, development, and human resource.

SOA is not recommended for the following type of applications.

- Homogenous: Implementing SOA for applications that use the technologies of a single vendor will not be cost-effective. For example, if an application is built in Java, then it would be better to use methods of Java rather than using HTTP for inter-component communications.
- GUI-Based: SOA would not be suitable for applications with GUI functionality, e.g. a map manipulation application. Such applications require heavy data exchange, which in turn would increase the complexity of the application if SOA is used.
- Real-time: SOA is not desirable to be used with strictly-enforced response times since the services communicate asynchronously.
- Stand-alone: It would be futile to invest in SOA for stand-alone non-distributed applications, which do not require request and response-based calls.

The architecture for any software application needs to be selected wisely since it involves factors like investment cost and human effort. Once you are able to understand when and when not to apply the service-oriented architecture, you can make the best use of it in your software development process.