To the insertSort.java program (Listing 3.3), add a method called noDups() that
ID: 3675646 • Letter: T
Question
To the insertSort.java program (Listing 3.3), add a method called noDups() that removes duplicates from a previously sorted array without disrupting the order. (You can use the insertionSort() method to sort the data, or you can simply use main() to insert the data in sorted order.) One can imagine schemes in which all the items from the place where a duplicate was discovered to the end of the array would be shifted down one space every time a duplicate was discovered, but this would lead to slow O(N2) time, at least when there were a lot of duplicates. In your algorithm, make sure no item is moved more than once, no matter how many duplicates there are. This will give you an algorithm with O(N) time.
Explanation / Answer
public ArrayIns(int max) // constructor
{
a = new long[max]; // create the array
nElems = 0; // no items
}
public void insert(long value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}
public void display() // displays array contents
{
for(int j=0; j<nElems; j++) // for each element,
System.out.print(a[j] + " "); // display it
System.out.println("");
}
public void insertionSort()
{
int in, out;
for(out=1; out<nElems; out++)
{
long temp = a[out];
in = out;
while(in>0 && a[in-1] >= temp) // until one is smaller,
{
a[in] = a[in-1]; // shift item to right
--in; // go left one position
}
a[in] = temp; // insert marked item
}
}
public long median()
{
int medianIndex = nElems / 2;
return a[medianIndex];
}
public void noDups()
{
for(int i = 0 ; i < nElems; i++) // set loop to step through
for(int j = i+1; j <nElems; j++) // compare starting from the next element
if(a[i] == a[j]) // if a duplicate is found
{
this.delete(a[j]); // delete it
j--; // to check the element j+2, which now becomes j+1 and would be skipped otherwise
}
}
public boolean delete(long value)
{
int j;
for(j=0; j<nElems; j++)
if( value == a[j] )
break;
if(j==nElems)
return false;
else
{
for(int k=j; k<nElems; k++)
a[k] = a[k+1];
nElems--;
return true;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.