Tuesday, July 15, 2014
Quicksort is one of the very popular sorting algorithm in programming, often used to sort large list of numbers. Though their are numerous algorithm available to sort list of objects, including integer, string and floating point number, quicksort is best for general purpose. It's a divide and conquer algorithm, where we divide the given array with respect to a particular element, known as 'pivot' such that the lower partition of the array are less than the pivot and upper partition elements of the array are higher than the pivot. Quicksort is also one of the best example of recursion. It's naturally recursive, because it sort the large list by dividing into smaller sub-list and then applying same algorithm on those. Base case of recursion is when list contains either one or zero element, in that case they are sorted. Quicksort is well ahead with primitive sorting algorithms e.g. insertion sort, selection sort and bubble sort. Average time complexity of quicksort is O(nlogn), while in worst case it's performance is similar to bubble sort i.e. O(n^2). Apparently worst case of quicksort is the best case of insertion sort, where they have to sort an already sorted list. In this article, we will learn how to implement quicksort algorithm in Java using recursion. We will also learn how quicksort works, and how it sorts large list of unsorted number. In last section, we will see some important things about quicksort.
Tuesday, June 24, 2014
One of the common programming practice question thrown to beginners is to write a program to calculate sum of digits in a integral number. For example, if input is 123456 then output or sum of digit is (1+2+3+4+5+6) = 21. Additional condition is you can not use any third party or library method to solve this problem. This program is not as simple as it looks and that's why its a good exercise, you must know some basic programming techniques e.g. loops, operators, and logic formation to solve this problem. Let's see how we can solve this problem using Java programming language. In order to calculate sum of digits we must get digits as numbers. So your first challenge is how do you get the digits as numbers? How do we extract 6 out of 123456? If you have done exercises like palindrome check or reversing number, then you should know that there is very old technique of getting last digit from a number by using modulus operator. If we do 123456%10 then we will get 6, which is last digit. In order to get all digits we can use a loop, something like while loop. Now our next challenge is how do we reduce number in each iteration so that our loop will finish as soon as we are done with all digits of number? Now coming from same palindrome problem, you can use technique of dividing number by 10 to get rid of last digit or reduce it by factor of 10. For example 123456/10 will give you 12345, which is one digit less than original number. So you got your end condition for while loop, check until number is not equal to zero. These two techniques are very important and can be used in variety of problem, so always remember these.
Monday, June 16, 2014
Abstract class is a special class in Java, it can not be instantiated and that's why can not be used directly. At first concept of abstraction, abstract class and interface all look useless to many developers, because you can not implement any method in interface, you can not create object of abstract class, so why do you need them. Once they face biggest constant of software development, yes that is CHANGE, they understand how abstraction at top level can help in writing flexible software. A key challenge while writing software (Java Programs, C++ programs) is not just to cater today's requirement but also to ensure that nurture requirement can be handled without any architectural or design change in your code. In short, your software must be flexible enough to support future changes. Abstract class and inheritance collectively ensures that most of the code are written using abstract and higher level classes, so that it can leverage Inheritance and Polymorphism to support future changes. This is actually one of the most useful design principle, also known as "Programming for interfaces rather than implementation". Abstract class and abstract method are two ways through which Java assist you on coding at certain level of abstraction. We will look at syntax level details, capability and limitation of abstract class at later half of article, but you must understand why abstract class is important. More importantly, why you, a Java programmer, must understand motive and use of abstract class. From my years of experience, I can say that making a class at first an interface or abstract class is a good practice, it will not only help you to test your code quickly by supplying mock objects, but also help you to write code at certain level of abstraction. In this article, we will understand why we need abstract class and abstract method and learn how to use them by writing a simple example.