Insertion Sort


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)));
}
}

Advertisements

QuickSort

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

Idea:

  1. 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
  2. recursively sort two sublists
  3. Note: the pivot could be chosen in multiple ways:
    1. you can pick first element in the array
    2. you can pick last element in the array
    3. you can pick median element in the array
    4. you can pick random element in the array
  4. 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 nums[i], not with nums[high] or anything else, we swap nums[high] after we finish iterating through low to high-1, this is to do this: place all elements that are smaller than the pivot to the left of the pivot, after iterating through from 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_20160628I() 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&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;();
Queue&lt;TreeNode&gt; q = new LinkedList&lt;TreeNode&gt;();
q.offer(root);
while(!q.isEmpty() &amp;&amp; root != null){
List&lt;Integer&gt; level = new ArrayList&lt;Integer&gt;();
int size = q.size();
for(int i = 0; i &lt; 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&lt;List&lt;Integer&gt;&gt; realResult = new ArrayList&lt;List&lt;Integer&gt;&gt;();
for(int i = result.size()-1; i &gt;= 0; i--){
realResult.add(result.get(i));
}
return realResult;
}

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


public class Solution {
public List&amp;lt;List&amp;lt;Integer&amp;gt;&amp;gt; levelOrderBottom(TreeNode root) {
List&amp;lt;List&amp;lt;Integer&amp;gt;&amp;gt; result = new ArrayList&amp;lt;List&amp;lt;Integer&amp;gt;&amp;gt;();
if(root == null) return result;
Queue&amp;lt;TreeNode&amp;gt; q = new LinkedList&amp;lt;TreeNode&amp;gt;();
q.offer(root);
int currentLen = 0;
while(!q.isEmpty()){
List&amp;lt;Integer&amp;gt; row = new ArrayList&amp;lt;Integer&amp;gt;();
currentLen = q.size();
for(int i = 0; i &amp;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&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;();
q.offer(root);
while(!q.isEmpty() &amp;&amp; root != null){
List&lt;Integer&gt; levelList = new ArrayList&lt;Integer&gt;();
int qSize = q.size();
for(int i = 0; i &lt; 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&amp;lt;List&amp;lt;Integer&amp;gt;&amp;gt; levelOrder(TreeNode root) {
List&amp;lt;List&amp;lt;Integer&amp;gt;&amp;gt; result = new ArrayList&amp;lt;List&amp;lt;Integer&amp;gt;&amp;gt;();
if(root == null) return result;
Queue&amp;lt;TreeNode&amp;gt; q = new LinkedList&amp;lt;TreeNode&amp;gt;();
int currentLen = 0;
q.offer(root);
while(!q.isEmpty()){
currentLen = q.size();
List&amp;lt;Integer&amp;gt; row = new ArrayList&amp;lt;Integer&amp;gt;();
for(int i = 0; i &amp;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.”

 

http://www.buzzle.com/articles/advantages-and-disadvantages-of-service-oriented-architecture-soa.html

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.

  1. 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.
  2. 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.
  3. Real-time: SOA is not desirable to be used with strictly-enforced response times since the services communicate asynchronously.
  4. 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.