Shell Sort

Discussion

The worse-case time complexity of shell sort depends on the increment sequence. For the increments 1 4 13 40 121..., which is what is used here, the time complexity is O(n^3/2). For other increments, time complexity is known to be O(n^4/3) and even O(n·lg²(n)). Neither tight upper bounds on time complexity nor the best increment sequence are known.

Because shell sort is based on insertion sort, shell sort inherits insertion sort's adaptive properties. The adapation is not as dramatic because shell sort requires one pass through the data for each increment, but it is significant. For the increment sequence shown above, there are log₃(n) increments, so the time complexity for nearly sorted data is O(n·log₃(n)).

Because of its low overhead, relatively simple implementation, adaptive properties, and sub-quadratic time complexity, shell sort may be a viable alternative to the O(n·lg(n)) sorting algorithms for some applications when the data to be sorted is not very large.

Algorithm

h = 1
while h < n, h = 3*h + 1
while h > 0,
    h = h / 3
    for k = 1:h, insertion sort a[k:h:n]
    → invariant: each h-sub-array is sorted
end

Properties

• Not stable
• O(1) extra space
• O(n^3/2) time as shown (see below)
• Adaptive: O(n·lg(n)) time when nearly sorted

• References

  Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.
  Programming Pearls by Jon Bentley. Addison Wesley, 1986.
  Quicksort is Optimal by Robert Sedgewick and Jon Bentley, Knuthfest, Stanford University, January, 2002.
  Bubble-sort with Hungarian ("Csángó") folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.
  Select-sort with Gypsy folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.
  The Beauty of Sorting YouTube video, Dynamic Graphics Project, Computer Systems Research Group, University of Toronto.

Selection Sort

Element	1	2	3	4	5	6	7	8
Data	27	63	1	72	64	58	14	9
1st pass	1	63	27	72	64	58	14	9
2nd pass	1	9	27	72	64	58	14	63
3rd pass	1	9	14	72	64	58	27	63...

The selection sort marks the first element (27). It then goes through the remaining data to find the smallest number (1). It swaps this with the first element and the smallest element is now in its correct position. It then marks the second element (63) and looks through the remaining data for the next smallest number (9). These two numbers are then swapped. This process continues until n-1 passes have been made.

Algorithm

for i = 1:n,
    k = i
    for j = i+1:n, if a[j] < a[k], k = j
    → invariant: a[k] smallest of a[i..n]
    swap a[i,k]
    → invariant: a[1..i] in final position
end

Properties

• Not stable
• O(1) extra space
• Θ(n²) comparisons
• Θ(n) swaps
• Not adaptive

Discussion

From the comparions presented here, one might conclude that selection sort should never be used. It does not adapt to the data in any way (notice that the four animations above run in lock step), so its runtime is always quadratic.

However, selection sort has the property of minimizing the number of swaps. In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice.

References

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.

Programming Pearls by Jon Bentley. Addison Wesley, 1986.

Quicksort is Optimal by Robert Sedgewick and Jon Bentley, Knuthfest, Stanford University, January, 2002.

Bubble-sort with Hungarian ("Csángó") folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

Select-sort with Gypsy folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

The Beauty of Sorting YouTube video, Dynamic Graphics Project, Computer Systems Research Group, University of Toronto.

Insertion Sort

Element	1	2	3	4	5	6	7	8
Data	27	63	1	72	64	58	14	9
1st pass	27	63	1	72	64	58	9	14
2nd pass	27	63	1	72	64	9	14	58
3rd pass	27	63	1	72	9	14	58	64...

The insertion sort starts with the last two elements and creates a correctly sorted sub-list, which in the example contains 9 and 14. It then looks at the next element (58) and inserts it into the sub-list in its correct position. It takes the next element (64) and does the same, continuing until the sub-list contains all the data.

Algorithm

for i = 2:n,
    for (k = i; k > 1 and a[k] < a[k-1]; k--) 
        swap a[k,k-1]
    → invariant: a[1..i] is sorted
end

Properties

• Stable
• O(1) extra space
• O(n²) comparisons and swaps
• Adaptive: O(n) time when nearly sorted
• Very low overhead

Discussion

Although it is one of the elementary sorting algorithms with O(n²) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).

For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.

References

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.

Programming Pearls by Jon Bentley. Addison Wesley, 1986.

Quicksort is Optimal by Robert Sedgewick and Jon Bentley, Knuthfest, Stanford University, January, 2002.

Bubble-sort with Hungarian ("Csángó") folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

Select-sort with Gypsy folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

The Beauty of Sorting YouTube video, Dynamic Graphics Project, Computer Systems Research Group, University of Toronto.

Exchange (Bubble) Sort

Element	1	2	3	4	5	6	7	8
Data	27	63	1	72	64	58	14	9
1st pass	27	1	63	64	58	14	9	72
2nd pass	1	27	63	58	14	9	64	72
3rd pass	1	27	58	14	9	63	64	72...

The first two data items (27 and 63) are compared and the smaller one placed on the left hand side. The second and third items (63 and 1) are then compared and the smaller one placed on the left and so on. After all the data has been passed through once, the largest data item (72) will have "bubbled" through to the end of the list. At the end of the second pass, the second largest data item (64) will be in the second last position. For n data items, the process continues for n-1 passes, or until no exchanges are made in a single pass.

Algorithm

for i = 1:n,
    swapped = false
    for j = n:i+1, 
        if a[j] < a[j-1], 
            swap a[j,j-1]
            swapped = true
    → invariant: a[1..i] in final position
    break if not swapped
end

Properties

• Stable
• O(1) extra space
• O(n²) comparisons and swaps
• Adaptive: O(n) when nearly sorted

References

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.

Programming Pearls by Jon Bentley. Addison Wesley, 1986.

Quicksort is Optimal by Robert Sedgewick and Jon Bentley, Knuthfest, Stanford University, January, 2002.

Bubble-sort with Hungarian ("Csángó") folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

Select-sort with Gypsy folk dance YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

The Beauty of Sorting YouTube video, Dynamic Graphics Project, Computer Systems Research Group, University of Toronto.

Manhattan Interview Questions Technical (JAVA)

These are the latest Interview Questions by Manhattan Associates. i.e., in the Technical round.

Tell me about yourself?

2. Write a program on palindrome (they test your programming knowledge)

3. Write a program to generate Fibonacci series (they test your programming knowledge)

4. What do you know about SingleTon class? and write a program on it and explain how to call the SingleTon class from other class.

5. You explicitly made a SingleTon class reference as null then what happends to other user who is using this SingleTon class reference?

6. What happens when we do like this? i.e., what will be the output?

String s = "Hello";

s.concat("world");

System.out.println(s);

7. If we modify the question like this what happends?

String s = null;

s.concat(“ABC”);

System.out.println(s.toLowerCase());

8. ­­­­How many ways you can iterate collections? What are they?

9. What is the difference between Enumerator and Iterator?

10. Which method will be called when we call the add() at 1 & at 2

public class A

{

public void add(int a, int b){......}

public void add(float a, float b){.....}

public void add(double a, double b){.....}



public static void main(String ar[]){

A a = new A();

a.add(1,2);----------à1

a.add(1.0,2.0); -------à2

}

}

11. How remove() will work in HashSet class?

12. What is the difference between Hashtable and HashMap?

13. How to reverse a list?

14. What are invariant variables?

15. If we have architecture like this which is seen in below, you will be having the jar files with classes in the D:/> directory. You need to copy all the classes to C:/> directory using ANT?

16. Java supports pass by value or pass by reference?



J2EE

1. What is the difference between dynamic include and static include?

2. How many request dispatchers are there? (As per servlets and jsp’s)?

3. How JVM executes when the anchor statement is like this?

<a href=”servlet/testServlet1” method=”post”>Click Here</a>

4. What is the difference between sendRedirect() and forward()?

5. What is a servlet? And what is the hierarchy?

6. What is the difference between GenericServlet and HttpServlet?

Struts

1. How many different types of action classes are there in your project?

2. Scenario: If there is a login page and you have to take those values i.e., you have to take username and password and store those values in the database. Tell me flow how you will do it.

SQL

1. What is cursor? And tell me different types of cursors

2. What is trigger? And where you have used triggers in your project?

3. What are joins? And tell me what are different joins are available?

4. Do we need compulsory two tables to use joins?

How to use For each Loop

for loop:

void cancelAll(Collection<TimerTask> c) {
    for (Iterator<TimerTask> i = c.iterator(); i.hasNext(); )
        i.next().cancel();
}

         The iterator is just clutter. Furthermore, it is an opportunity for error. The iterator variable occurs three times in each loop: that is two chances to get it wrong. The for-each construct gets rid of the clutter and the opportunity for error. Here is how the example looks with the for-each construct:

foreach loop:

void cancelAll(Collection<TimerTask> c) {
    for (TimerTask t : c)
        t.cancel();
}        When you see the colon (:) read it as “in.” The loop above reads as “for each TimerTask t in c.” As you can see, the for-each construct combines beautifully with generics. It preserves all of the type safety, while removing the remaining clutter. Because you don't have to declare the iterator, you don't have to provide a generic declaration for it. (The compiler does this for you behind your back, but you need not concern yourself with it.)

Where for each loop should and should not be used:

It is not usable for loops where you need to replace elements in a list or array as you traverse it.
Finally, it is not usable for loops that must iterate over multiple collections in parallel.
Advantages of for each loop:

Less error prone code.
Improved readability
Less number of variables to clean up

Java Sorting: Difference b/w Comparable and Comparator

Java Comparators and Comparables? What are they? How do we use them? This is a question we received from one of our readers. This article will discuss the java.util.Comparator and java.lang.Comparable in details with a set of sample codes for further clarifications.

What are Java Comparators and Comparables?

As both names suggest (and you may have guessed), these are used for comparing objects in Java. Using these concepts; java objects can be
sorted according to a predefined order.

Two of these concepts can be explained as follows.

Comparable

A comparable object is capable of comparing itself with another object. The class itself must implements the java.lang.Comparable interface in order to be able to compare its instances.

Comparator

A comparator object is capable of comparing two different objects. The class is not comparing its instances, but some other class’s instances. This comparator class must implement the java.util.Comparator interface.

Do we need to compare objects?

The simplest answer is yes. When there is a list of objects, ordering these objects into different orders becomes a must in some situations. For example; think of displaying a list of employee objects in a web page. Generally employees may be displayed by sorting them using the employee id. Also there will be requirements to sort them according to the name or age as well. In these situations both these (above defined) concepts will become handy.

How to use these?

There are two interfaces in Java to support these concepts, and each of these has one method to be implemented by user.
Those are;

java.lang.Comparable: int compareTo(Object o1)
This method compares this object with o1 object. Returned int value has the following meanings.

1. positive – this object is greater than o1
2. zero – this object equals to o1
3. negative – this object is less than o1

java.util.Comparator: int compare(Object o1, Objecto2)
This method compares o1 and o2 objects. Returned int value has the following meanings.

1. positive – o1 is greater than o2
2. zero – o1 equals to o2
3. negative – o1 is less than o2

java.util.Collections.sort(List) and java.util.Arrays.sort(Object[]) methods can be used to sort using natural ordering of objects.
java.util.Collections.sort(List, Comparator) and java.util.Arrays.sort(Object[], Comparator) methods can be used if a Comparator is available for comparison.

The above explained Employee example is a good candidate for explaining these two concepts. First we’ll write a simple java beans to represent the Employee.

public class Employee {
private int empId;
private String name;
private int age;

public Employee(int empId, String name, int age) {
// set values on attributes
}
// getters & setters
}

Next we’ll create a list of Employees for using in different sorting requirements. Employees are added to a List without any specific order in the following class.

import java.util.*;

public class Util {

public static List<Employee> getEmployees() {

List<Employee> col = new ArrayList<Employee>();

col.add(new Employee(5, "Frank", 28));
col.add(new Employee(1, "Jorge", 19));
col.add(new Employee(6, "Bill", 34));
col.add(new Employee(3, "Michel", 10));
col.add(new Employee(7, "Simpson", 8));
col.add(new Employee(4, "Clerk",16 ));
col.add(new Employee(8, "Lee", 40));
col.add(new Employee(2, "Mark", 30));

return col;
}
}

Sorting in natural ordering

Employee’s natural ordering would be done according to the employee id. For that, above Employee class must be altered to add the comparing ability as follows.

public class Employee implements Comparable<Employee> {
private int empId;
private String name;
private int age;

/**
* Compare a given Employee with this object.
* If employee id of this object is 
* greater than the received object,
* then this object is greater than the other.
*/
public int compareTo(Employee o) {
return this.empId - o.empId ;
}
….
}

The new compareTo() method does the trick of implementing the natural ordering of the instances. So if a collection of Employee objects is sorted using Collections.sort(List) method; sorting happens according to the ordering done inside this method.

We’ll write a class to test this natural ordering mechanism. Following class use the Collections.sort(List) method to sort the given list in natural order.

import java.util.*;

public class TestEmployeeSort {

public static void main(String[] args) {     
List coll = Util.getEmployees();
Collections.sort(coll); // sort method
printList(coll);
}

private static void printList(List<Employee> list) {
System.out.println("EmpId\tName\tAge");
for (Employee e: list) {
System.out.println(e.getEmpId() + "\t" + e.getName() + "\t" + e.getAge());
}
}
}

Run the above class and examine the output. It will be as follows. As you can see, the list is sorted correctly using the employee id. As empId is an int value, the employee instances are ordered so that the int values ordered from 1 to 8.

EmpId Name Age
1 Jorge 19
2 Mark 30
3 Michel 10
4 Clerk 16
5 Frank 28
6 Bill 34
7 Simp 8
8 Lee 40

Sorting by other fields

If we need to sort using other fields of the employee, we’ll have to change the Employee class’s compareTo() method to use those fields. But then we’ll loose this empId based sorting mechanism. This is not a good alternative if we need to sort using different fields at different occasions. But no need to worry; Comparator is there to save us.

By writing a class that implements the java.util.Comparator interface, you can sort Employees using any field as you wish even without touching the Employee class itself; Employee class does not need to implement java.lang.Comparable or java.util.Comparator interface.

Sorting by name field

Following EmpSortByName class is used to sort Employee instances according to the name field. In this class, inside the compare() method sorting mechanism is implemented. In compare() method we get two Employee instances and we have to return which object is greater.

public class EmpSortByName implements Comparator<Employee>{

public int compare(Employee o1, Employee o2) {
return o1.getName().compareTo(o2.getName());
}
}

Watch out: Here, String class’s compareTo() method is used in comparing the name fields (which are Strings).

Now to test this sorting mechanism, you must use the Collections.sort(List, Comparator) method instead of Collections.sort(List) method. Now change the TestEmployeeSort class as follows. See how the EmpSortByName comparator is used inside sort method.

import java.util.*;

public class TestEmployeeSort {

public static void main(String[] args) {

List coll = Util.getEmployees();
//Collections.sort(coll);
//use Comparator implementation
Collections.sort(coll, new EmpSortByName());
printList(coll);
}

private static void printList(List<Employee> list) {
System.out.println("EmpId\tName\tAge");
for (Employee e: list) {
System.out.println(e.getEmpId() + "\t" + e.getName() + "\t" + e.getAge());
}
}
}

Now the result would be as follows. Check whether the employees are sorted correctly by the name String field. You’ll see that these are sorted alphabetically.

EmpId Name Age
6 Bill 34
4 Clerk 16
5 Frank 28
1 Jorge 19
8 Lee 40
2 Mark 30
3 Michel 10
7 Simp 8

Sorting by empId field

Even the ordering by empId (previously done using Comparable) can be implemented using Comparator; following class
does that.

public class EmpSortByEmpId implements Comparator<Employee>{

public int compare(Employee o1, Employee o2) {
return o1.getEmpId() - o2.getEmpId();
}
}

Explore further

Do not stop here. Work on the followings by yourselves and sharpen knowledge on these concepts.

1. Sort employees using name, age, empId in this order (ie: when names are equal, try age and then next empId)
2. Explore how & why equals() method and compare()/compareTo() methods must be consistence.

If you have any issues on these concepts; please add those in the comments section and we’ll get back to you.