Exercise 5 (Simple Sorting, Runtime Complexity)

Sorting and Removing duplicates:

• Create a class IntArray which represents a dynamically growing integer array for storing values of primitive type int without autoboxing. (As demonstrated in the lecture.)
  
• Implement a modified version of the insertionSort() method from the lecture so that it removes duplicates as it sorts. Use the following approach:
• Whenever a duplicate is found, write over one of the duplicated items with Integer.MIN_VALUE and let the insertion sort algorithm continue.
• When the sort is finished, cut of the head of the sorted array. (The part which is filled with Integer.MIN_VALUE.)
• What would be a better approach for sorting and removing duplicates?
• Compare your modified insertionSort() method with the suggested better approach and document the results. Explain your results and use the Big O Notation.
  
• Submit your implementation of IntArray and a document (simple txt or pdf) which contains your comparison results and the explanation of the results.

Hint:

You can use System.nanoTime() to compare the two different approaches for sorting and removing duplicates. E.g.:

// Create two big (e.g. 10000 random elements) unsorted IntArrays, which contain exactly the same elements for comparing the two different approaches.
...

time = System.nanoTime();
... // Call the first method for sorting and removing duplicates
System.out.println("Insertion Sort method needs ms: " + (System.nanoTime()-time)/1000000);

time = System.nanoTime();
... // Call the second method for sorting and removing duplicates
System.out.println("Other method needs ms: " + (System.nanoTime()-time)/1000000);