Write a simple program that will measure the time taken to sort an array of integers | compare various sorting algorithms selection sort, insertion sort, merge sort, Quick sort

Below has java program to compare time taken between Insertion Sort, Selection Sort, Quick Sort, Merge Sort.





import java.util.Random;

public class Sorting {
      private static final int SIZE = 16000;
      private static int[] z = new int[SIZE];
      private static int[] a = new int[SIZE];
      private static int[] b = new int[SIZE];

      public static void main(String[] args) {
            // Create and populate array with random values
            Random rand = new Random();
            int[] x = new int[SIZE];
            for (int i = 0; i < x.length; i++) {
                  x[i] = rand.nextInt(SIZE);
            }
            showArray(x);
            int[] y = new int[SIZE];
            y = x;
            z = x;
            a = x;
            // Insertion Sort
            long start = System.currentTimeMillis();
            insertionSort(x);
            long end = System.currentTimeMillis();
            System.out.println("It took " + (end - start) / 1000.0
                        + " seconds to sort " + SIZE + " elements.");
           
            // Selection sort

            start = System.currentTimeMillis();
            selectionSort(y);
            end = System.currentTimeMillis();
            System.out.println("It took " + (end - start) / 1000.0
                        + " seconds to sort " + SIZE + " elements.");

            // Quicksort

            start = System.currentTimeMillis();
            quickSort(0, z.length - 1);
            end = System.currentTimeMillis();
            System.out.println("It took " + (end - start) / 1000.0
                        + " seconds to sort " + SIZE + " elements.");

            // Mergesort

            start = System.currentTimeMillis();
            mergeSort(0, a.length - 1);
            end = System.currentTimeMillis();
            System.out.println("It took " + (end - start) / 1000.0
                        + " seconds to sort " + SIZE + " elements.");

      }

      private static void showArray(int[] x) {
            System.out.print("[");
            for (int i = 0; i < x.length - 1; i++) {
                  System.out.print(x[i] + ", ");
            }
            System.out.println(x[x.length - 1] + "]");
      }

      // Add sorting algorithms here // Insertion, Selection, Quicksort, Mergesort
      public static void insertionSort(int[] arr) {
            int i, j, newValue;
            for (i = 1; i < arr.length; i++) {
                  newValue = arr[i];
                  j = i;
                  while (j > 0 && arr[j - 1] > newValue) {
                        arr[j] = arr[j - 1];
                        j--;
                  }
                  arr[j] = newValue;
            }
      }
 //selection sort
      public static void selectionSort(int[] x) {

            for (int i = 0; i < x.length - 1; i++) {
                  int minIndex = i;
                  for (int j = i + 1; j < x.length; j++) {
                        if (x[minIndex] > x[j]) {
                              minIndex = j;
                        }
                  }
                  if (minIndex != i) {

                        int temp = x[i];
                        x[i] = x[minIndex];
                        x[minIndex] = temp;
                  }
            }
      }
// Quick sort
      public static void quickSort(int low, int high) {

            int i = low, j = high;
            // the pivot element from the middle of the list
            int pivot = z[low + (high - low) / 2];
            // divide into two lists
            while (i <= j) {
                  while (z[i] < pivot) {
                        i++;
                  }
                  while (z[j] > pivot) {
                        j--;
                  }

                  if (i <= j) {
                        swap(i, j);
                        i++;
                        j--;
                  }
            }

            if (low < j)
                  quickSort(low, j);
            if (i < high)
                  quickSort(i, high);
      }

      public static void swap(int i, int j) {
            int temp = z[i];
            z[i] = z[j];
            z[j] = temp;
      }
// Merge Sort
      public static void mergeSort(int low, int high) {
            System.out.print("");
            // Check if low is smaller then high, if not then the array is sorted
            if (low < high) {
                  // Get the index of the element which is in the middle
                  int middle = low + (high - low) / 2;
                  // Sort the left side of the array
                  mergeSort(low, middle);
                  // Sort the right side of the array
                  mergeSort(middle + 1, high);
                  // Combine them both
                  merge(low, middle, high);
            }
      }

      public static void merge(int low, int middle, int high) {

            // Copy both parts into the temp array
            for (int i = low; i <= high; i++) {
                  b[i] = a[i];
            }

            int i = low;
            int j = middle + 1;
            int k = low;
            // copy the smallest values from either the left or the right side back
            // to the original array
            while (i <= middle && j <= high) {
                  if (b[i] <= b[j]) {
                        a[k] = b[i];
                        i++;
                  } else {
                        a[k] = b[j];
                        j++;
                  }
                  k++;
            }
            // copy the rest of the left side of the array into the target array
            while (i <= middle) {
                  a[k] = b[i];
                  k++;
                  i++;
            }

      }

}

Output:

What is String args[] in Java main method | Why use String args[] in main method | java concept

 What is String args is used for or Why we use String arg[] in main method is a common doubt among Java beginners. First thing newbies exposed while learning Java programming language is writing HelloWorld program in Java, Though HelloWorld is smallest sort of program, it contains lot of useful information and concept for newbies Java programmers, one of them is main method and it's different attribute. Though I covered bit of String args[], while discussing Why main is public static in Java, I thought to write this article to explain String args array in more detail. Let's see a simple Java HelloWorld again to understand more about String args in Java.

public class HelloJava{
      
        public static void main(String args[]){
           System.out.println("Helloworld in Java");
        }
}


What is String args in Java main methodString args[], which is actually an array of java.lang.String type, and it's name is args here. It's not necessary to name it args always, you can name it strArray or whatever you like, but most programmer prefer to name it args, because that's what everyone else do. When we run a Java program from command prompt, we can pass some input to our Java program. Those inputs are stored in this String args array. For example if we modify our program to print content of String args[], as shown below:

public class StringArgsTest {

    public static void main(String args[]) {

        System.out.println("String arguments passed while running this Java Program : ");
        for(String argument : args){
            System.out.println(argument);
        }     
    }   
}



and after compiling, we run this Java program as  java StringArgsTest Java J2EE Android, then this program will print following output :

String arguments passed while running this Java Program :
Java
J2EE
Android

because, we have passed three arguments separated by white space. If you want to combine multiple words, which has some white space in between, then you can enclose them in double quotes. If we run our program again with following command :

java StringArgsTest "This is one argument" "This is another argument"

it will print:

String arguments passed while running this Java Program :
This is one argument
This is another argument

By the way, if you are using Eclipse to run Java Program, then you can provide String argument to your Java program using "Run Configuration". When you run Java program, by right click on Java class with main method, it creates a Run Argument for that class. you can access them as Right click-->Run As-->Run Configuration. In second tab, you can see two section Program Arguments and VM Arguments. You can pass all your String arguments from this program arguments section. As shown in this image

By the way, you can write your String args[] as String[] args as well, because both are valid way to declare String array in Java. Another interesting thing to note is that, from Java 5 onwards, you can varargs or variable arguments in main method instead of String args[]. Which means following declaration of main method is also valid : public static void main(String... args), and you can access this variable argument as normal array in Java. E.g. if we use this syntax of main, in your earlier program we don't need to change anything else, it would work, just like it is working now.

Thread.State in Java? BLOCKED vs WAITING | What is Thread.State in Java? What's it used for?

Thread.State - This is a static nested class (Read more about nested classes in the article - Nested Classes & Inner Classes in Java >>) of the Thread class. This is one of the additions of Java 5 and this class actually inherits the abstract class Enum which is the common base class of all Java language enumeration types i.e., Thread.State is actually is actually an enumeration type.

Thread.State enumeration contains the possible states of a Java thread in the underlying JVM. These states are different from the Operating System thread states. The possible values of the Thread.State are:-

    NEW - this state represents a new thread which is not yet started.
    RUNNABLE - this state represents a thread which is executing in the underlying JVM. Here executing in JVM doesn't mean that the thread is always executing in the OS as well - it may wait for a resource from the Operating system like the processor while being in this state.
    BLOCKED - this state represents a thread which has been blocked and is waiting for a moniotor to enter/re-enter a synchronized block/method. A thread gets into this state after calling Object.wait method.
    WAITING - this state represnts a thread in the waiting state and this wait is over only when some other thread performs some appropriate action. A thread can get into this state either by calling - Object.wait (without timeout), Thread.join (without timeout), or LockSupport.park methods.
    TIMED_WAITING - this state represents a thread which is required to wait at max for a specified time limit. A thread can get into this state by calling either of these methods: Thread.sleep, Object.wait (with timeout specified), Thread.join (with timeout specified), LockSupport.parkNanos, LockSupport.parkUntil
    TERMINATED - this state reprents a thread which has completed its execution either by returning from the run() method after completing the execution OR by throwing an exception which propagated from the run() method and hence caused the termination of the thread.

Difference between BLOCKED state and WAITING / TIMED_WAITING states?


When a thread calls Object.wait method, it releases all the acquired monitors and is put into WAITING (or TIMED_WAITING if we call the timeout versions of the wait method) state. Now when the thread is notified either by notify() or by notifyAll() call on the same object then the waiting state of the thread ends and the thread starts attempting to regain all the monitors which it had acquired at the time of wait call. At one time there may be several threads trying to regain (or maybe gain for the first time) their monitors. If more than one threads attempt to acquire the monitor of a particular object then only one thread (selected by the JVM scheduler) is granted the monitor and all other threads are put into BLOCKED state. Got the difference?

Difference between WAITING and TIMED_WAITING states?

The difference is quite obvious between the two. A thread in a TIMED_WAITING state will wait at max for the specified timeout period whereas a thread in the WAITING state keeps waiting for an indefinite period of time. For example, if a thread has called Object.wait method to put itself into WAITING state then it'll keep waiting until the thread is interrupted either by notify() method (OR by notifyAll() method) call on the same object by another thread. Similarly, if a thread has put itself into WAITING state by calling Thread.join method then it'll keep waiting until the specified thread terminates.

We can easily figure out that a thread in a WAITING state will always be dependent on an action performed by some other thread whereas a thread in TIMED_WAITING is not completely dependent on an action performed by some other thread as in this case the wait ends automatically after the completion of the timeout period.

Java : Static Initialization Blocks and their alternatives in Java | what is initialization blocks in java

The easiest way of initializing fields (static or instance) in Java at the time of their declaration is simply by providing a compile time constant value of a compatible data type. For example:


public class InitializationWithConstants{

public static int staticIntField = 100;
private boolean instanceBoolField = true;

}


This type of initialization has its limitation due to its simplicity and it can not support initialization based even on some moderately complex logic - like initializing only selected elements of a complex array using some logic in a for loop.

Here comes the need for static initialization blocks and initializer blocks for initializing static and instance fields, respectively.

Static Initialization Blocks - what are they and how to use them?

It's a normal block of code enclosed within a pair of braces and preceded by a 'static' keyword. These blocks can be anywhere in the class definition where we can have a field or a method. The Java runtime guarantees that all the static initialization blocks are called in the order in which they appear in the source code and this happens while loading of the class in the memory.


public class InitializationWithStaticInitBlock{

public static int staticIntField;
private boolean instanceBoolField = true;

static{
 //compute the value of an int variable 'x'
 staticIntField = x;
}
}


Since static initialization blocks are actually code-blocks so they will allow us to initialize even those static fields which require some logical processing to be done for them to get their initial values.

Alternative to Static Initialization Blocks

A private static method is a suitable alternative to the static initialization blocks. In fact it has some advantages over static initialization blocks as well like you can re-use a private static method to re-initialize a static field in case you need it. So, you kind of get more flexibility with a private static method in comparison to the corresponding static initialization block. This should not mislead that a 'public' static method can't do the same. But, we are talking about a way of initializing a class variable and there is hardly any reason to make such a method 'public'. More about how to pick the access control modifiers here - Choosing a suitable access control modifier >>


public class InitializationWithPrivateStaticMethod{

public static int staticIntField = privStatMeth();
private boolean instanceBoolField = true;

private static int privStatMeth() {
 //compute the value of an int variable 'x'
 return x;
}
}

Java : Connecting to an HTTP Web Service from VBA Excel via a Proxy Server

Though MSDN suggests using stubs generated from the WSDL by MS Soap Toolkit for connecting to an HTTP Web Service from within VBA Excel, but it might not work as you would like it to, especially for a SOA-compliant web service and particularly in the cases where you need to access the service via a Proxy Server.

I have used the SOAP Connector called 'httpConnector30' successfully to connect to an HTTP Web Service without any issues. This connector is a part of the Microsoft SOAP Library named MSSOAPLib30 and you got to make sure that this library is referenced in your Excel installation. If it's not already there in your excel, just add the corresponding DLL and you're done.

Using httpConnector30 is different from consuming a Web Service by creating the stubs using MS Soap Toolkit. 'httpConnector30' requires you to specify the actual Web Service URL whereas the toolkit asks you the WSDL url and creates stubs accordingly, which you use in your VBA code. I personally think using 'httpConnector30' is easier and more straightforward if you have the service url.

Before we jump on to the code listed below, let's understand what all the code does broadly:-

    Instantiating the SOAP Connector
    Setting up the Proxy Server and Port (if access needed via Proxy)
    Setting up the Web Service URL (not WSDL url)
    Setting up Timeout period for the service call
    Setting up the SOAP Action i.e., the actual method to be called
    Beginning SOAP Message and getting connector's Input Stream
    Building up the SOAP Request (as per your Web Service definition)
    Sending the SOAP Message (this is where the service call is made)
    Initializing the SOAP Reader and reading the SOAP Response

Note: in the below code I have not shown the exception handling blocks, which you should include to grab and handle the potential errors gracefully. For example: you should first check the 'connector' as 'Not Nothing' before trying to load the 'reader' with connector's output stream.

Additionally, I've assumed that the first node (except the generic envelope and body) of the SOAP Response is actually a List and hence I've put a loop to iterate through it. 'Set response = reader.RPCResult.childNodes' actually sets the 'response' to the first node of the SOAP Response as read from the reader (which itself is loaded with the connector's output stream).

Just to make your service consumption code robust and independent of the Response Structure changes (like addition of new nodes and/or reordering of nodes), in your client code, you should iterate through all the SOAP Response nodes and compare the current node name with your Service Response node names (you can get them in the service WSDL) and subsequently handle the particular node, say inside an if-block. This will make sure that your code doesn't fail abruptly in case Service Response Structure changes. For example: it will avoid any code failure say because you had written it assuming the first node in the response was a List and let's say the service response structure changes make it the second node in the response - maybe because the service provider needed to add another field in the response and also wished to make that the first field. I know the service provide will certainly let the client developers know about the changes, but if you make your code flexible to such possible changes, nothing like it... right?


Public Sub HTTPConnectivityTest()
 
   'Instantiating the SOAP Connector
   Dim connector As New MSSOAPLib30.HttpConnector30
 
   'Setting up the Proxy Server and Port
   connector.Property("ProxyServer") = "fully-qualified-proxy-server-or-IPAddress:Port"

 
   'Setting up the Web Service URL
   connector.Property("EndPointURL") = "http://web-service-server:port/webservices/SampleService.v1"
 
   'Setting up Timeout period for the service call
   connector.Property("Timeout") = 2000 '2 minutes
 
   'Setting up the SOAP Action i.e., the actual method to be called
   connector.Property("SoapAction") = "urn:getSampleData"
 
   'Beginning SOAP Message
   connector.BeginMessage
 
   'Initializing SOAP Serializer with connector's input stream
   Dim writer As New MSSOAPLib30.SoapSerializer30
   writer.Init connector.InputStream

   'Building the SOAP Request - envelope and body
   writer.startEnvelope              ' <SOAP-ENV:Envelope>
   writer.startBody                  ' <SOAP-ENV:Body>

   'Populating the SOAP Request with actual input parameters
   writer.startElement "SampleServiceRequest", "service namespace", , "s3"   ' <SampleServiceRequest>
 
   writer.startElement "inputParam1"   ' <inputParam1>
   writer.writeString "param1 value"    ' value of inputParam1
   writer.endElement                 ' </inputParam1>

   writer.startElement "inputParam2"   ' <inputParam2>
   writer.writeString "param2 value"        ' value of inputParam2
   writer.endElement                 ' </inputParam2>

   writer.startElement "inputParam3"   ' <inputParam3>
   writer.writeString "param3 value"        ' value of inputParam3
   writer.endElement                 ' </inputParam3>

   'Populating list-type parameter
   writer.startElement "paramList"   ' <paramList>

    'Adding node #1 to the list-type param
    writer.startElement "paramListNode"    ' <paramListNode>
     writer.startElement "nodeParam1"          ' <nodeParam1>
      writer.writeString "value1"                    ' value of nodeParam1
     writer.endElement                          ' </nodeParam1>
 
     writer.startElement "nodeParam2"          ' <nodeParam2>
      writer.writeString "value1"                    ' value of nodeParam2
     writer.endElement                          ' </nodeParam2>
    writer.endElement                          ' </paramListNode>

    'Adding node #2 to the list-type param
    writer.startElement "paramListNode"    ' <paramListNode>
     writer.startElement "nodeParam1"          ' <nodeParam1>
      writer.writeString "value2"                    ' value of nodeParam1
     writer.endElement                          ' </nodeParam1>
 
     writer.startElement "nodeParam2"          ' <nodeParam2>
      writer.writeString "value2"                    ' value of nodeParam2
     writer.endElement                          ' </nodeParam2>
    writer.endElement                          ' </paramListNode>
 
   'Population of list-type param ends here
   writer.endElement                          ' </paramList>

   'Finishing the SOAP Request
   writer.endElement                 ' </SampleServiceRequest>
   writer.endBody                    ' </SOAP-ENV:Body>
   writer.endEnvelope                ' </SOAP-ENV:Envelope>
 
   'Sending the SOAP Message (this is where the service call is made)
   connector.EndMessage
 
   'Defining SOAP Reader and initializing it with connector's output stream
   Dim reader As New MSSOAPLib30.SoapReader30
   reader.Load connector.OutputStream
 
   'Parsing the SOAP Response
   Dim response As MSXML2.IXMLDOMNodeList

   'Setting the response to the first node of the SOAP Response
   Set response = reader.RPCResult.childNodes
   Dim node As MSXML2.IXMLDOMNode

   'Iterating through the first node of SOAP Response knowing it is a list
   For Each node In response
    Dim nodeName As String
    Dim nodeValue As String
 
    nodeName = node.nodeName
    nodeValue = node.nodeTypedValue
 
    'Showing the Node Name and Value on Alert Boxes
    MsgBox node.nodeName & ": " & node.nodeTypedValue
   Next node
End Sub

Java concept : Abstract Class and Interface Interview Questions Answers in Java

 Abstract class and interface is very popular in any object oriented programming language or Java interview, and there are always one or more questions from this. Interface is more common, because of its popularity among designers but questions from abstract class also pops up now and than. Interview questions from abstract class is more common on junior level or you say under 2 years experience of  Java programmers, while interface related questions are mostly asked on senior level Java interview e.g. 4 or 6 years of experience. They are mostly asked along with other Java design pattern questions, e.g. Decorator pattern or Factory pattern . Any way, in this article we will see mix of these interview questions from abstract class and interface. All questions has been asked in various Java interviews and difficulty level for these question is easy for most of Java developer. It’s mostly fact based questions, but some questions like difference between abstract class and interface in Java, and when to prefer abstract class over interface can be really tricky.


Frequently asked Abstract class and Interface questions in Java

Java abstract class and interface interview Question answersHere is my list of questions, this not only explains rules related to abstract class but also shares some tricky questions about using abstract class and interface. If you have asked any question on this topic, which you don’t see in this list, than please share with us as comment


1) Can abstract class have constructors in Java?
Yes, abstract class can declare and define constructor in Java. Since you can not create instance of abstract class,  constructor can only be called during constructor chaining, i.e. when you create instance of concrete implementation class. Now some interviewer, ask what is the purpose of constructor, if you can not instantiate abstract class? Well, it can still be used to initialize common variables, which are declared inside abstract class, and used by various implementation. Also even if you don’t provide any constructor, compiler will add default no argument constructor in abstract class, without that your subclass will not compile, since first statement in any constructor implicitly calls super(), default super class constructor in Java.

2) Can abstract class implements interface in Java? does they require to implement all methods?
Yes, abstract class can implement interface by using implements keyword. Since they are abstract, they don’t need to implement all methods. It’s good practice to provide an abstract base class, along with an interface to declare Type. One example of this is java.util.List interface and corresponding java.util.AbstractList abstract class. Since AbstractList implements all common methods,  concrete implementations like LinkedList and ArrayList are free from burden of implementing all methods, had they implemented List interface directly. It’s best of both world, you can get advantage of interface for declaring type, and flexibility of abstract class to implement common behavior at one place. Effective Java has a nice chapter on how to use interface and abstract class in Java, which is worth reading.


3) Can abstract class be final in Java?

No, abstract class can not be final in Java. Making them final will stop abstract class from being extended, which is the only way to use abstract class. They are also opposite of each other, abstract keyword enforces to extend a class, for using it, on the other hand, final keyword prevents a class from being extended. In real world also, abstract signifies incompleteness, while final is used to demonstrate completeness. Bottom line is, you can not make your class abstract and final in Java, at same time, it’s a compile time error.

4) Can abstract class have static methods in Java?
Yes, abstract class can declare and define static methods, nothing prevents from doing that. But, you must follow guidelines for making a method static in Java, as it’s not welcomed in a object oriented design, because static methods can not be overridden in Java. It’s very rare, you see static methods inside abstract class, but as I said, if you have very good reason of doing it, then nothing stops you.


5) Can you create instance of abstract class?

No, you can not create instance of abstract class in Java, they are incomplete. Even though, if your abstract class don’t contain any abstract method, you can not create instance of it. By making a class abstract,  you told compiler that, it’s incomplete and should not be instantiated. Java compiler will throw error, when a code tries to instantiate abstract class.

6) Is it necessary for abstract class to have abstract method?
No, It’s not mandatory for an abstract class to have any abstract method. You can make a class abstract in Java, by just using abstract keyword in class declaration. Compiler will enforce all structural restriction, applied to abstract class, e.g. now allowing to create any instance. By the way, it’s debatable whether you should have abstract method inside abstract class or interface. In my opinion, abstract class should have abstract methods, because that’s the first thing programmer assumes, when he see that class. That would also go nicely along principle of least surprise.

7) Difference between abstract class and interface in Java?
This is the most important and one of the classic Java Interview question. I don’t know, how many times I have seen this question at all most all levels of Java interviews. One reason, which makes this question interesting is ability to produce example. It’s easy to answers questions on core OOPS concepts like Abstraction, Encapsulation, Polymorphism and Inheritance, but when it comes to subtle points like this, candidate more often fumbled. You can see this post for all syntactical difference between abstract class and interface, but it deserve a post on it’s own.

8) When do you favor abstract class over interface?
This is the follow-up of previous interview questions on abstract class and interface. If you know syntactical difference, you can answer this question quite easily, as they are the one, which drives the decision. Since it’s almost impossible to add a new method on a published interface, it’s better to use abstract class, when evolution is concern. Abstract class in Java evolves better than interface. Similarly, if you have too many methods inside interface, you are creating pain for all it’s implementation, consider providing an abstract class for default implementation. This is the pattern followed in Java collection package, you can see AbstractList provides default implementation for List interface.

9) What is abstract method in Java?
An abstract method is a method without body. You just declare method, without defining it and use abstract keyword in method declaration.  All method declared inside Java Interface are by default abstract. Here is an example of abstract method in Java

                public void abstract printVersion();

Now, In order to implement this method, you need to extend abstract class and override this method.

10) Can abstract class contains main method in Java ?
Yes, abstract class can contain main method, it just another static method and you can execute Abstract class with main method, until you don’t create any instance.