Sorting and removing duplicates
I have been asked to implement quicksort (or mergesort) in an application,
and then remove any duplicates.
I have done just that, however, I have been further told that I should call
my sort method from within my remove duplicates method.
When my methods are called independently they work perfectly. However when
I call the sort method from within the remove duplicates method, the array
returned is not sorted correctly.
I am not allowed to use the Collections sort method, as that would defeat
the purpose of me implementing one of the sorting methods.
Here is my code (please keep the chuckles down ;-)
I have placed several superfluous System.out.println calls in the code for
help with [my] troubleshooting.
public class MyRemoveDup implements RemoveDup {
public int[] makeUnique(int[] AnArray) {
System.out.println("Step 1");
int i;
for (i =0;i<AnArray.length;i++){
System.out.println(i +" : "+AnArray[i]);
}
System.out.println("");
sort(AnArray);
for (i =0;i<AnArray.length;i++){
System.out.println(i +" : "+AnArray[i]);
}
System.out.println("\nmkUniq\n");
mkUniq(AnArray);
for (i =0;i<AnArray.length;i++){
System.out.println(i +" : "+AnArray[i]);
}
return AnArray;
}
public int[] mkUniq(int[] AnArray){
for (int i =0;i<AnArray.length;i++){
System.out.println(i +" : "+AnArray[i]);
}
int cloneCount = 1;
//Create another array, to copy the unique elements from the sorted to.
int [] myArray = new int[AnArray.length];
//Obviously the first element will be unique :-)
myArray[0]=AnArray[0];
for (int i = 1;i < AnArray.length;i++){
if (AnArray[i] != AnArray[i-1])
{
myArray[cloneCount] = AnArray[i];
cloneCount++;
}
}
int [] Clone = new int[AnArray.length -(AnArray.length-cloneCount)];
System.arraycopy(myArray, 0, Clone, 0, Clone.length);
return Clone;
}
public static int[] swapper(int []myArray, int x, int y){
//System.out.println("Start x: " + myArray[x] + " and y:" + myArray[y]);
int holder =0;
holder = myArray[x];
myArray[x] = myArray[y];
myArray[y] = holder;
//System.out.println("Finish x: " + myArray[x] + " and y:" + myArray[y]);
return myArray;
}
public static void quickSort(int []arr, int low, int high){
//set the pivot to the middle element
int middle = (low + high )/2;
if (low + 3 >= high){
// sort the low, high, and middle elements
if ( arr[middle]<(arr[low]))
arr = swapper(arr, middle, low);
if ( arr[high]<(arr[low]))
arr = swapper(arr, high, low);
if ( arr[high]<(arr[middle]))
arr = swapper(arr, high, middle);
}else{
//sort the low, high, and middle elements
if ( arr[middle]<(arr[low]))
arr = swapper(arr, middle, low);
if ( arr[high]<(arr[low]))
arr = swapper(arr, high, low);
if ( arr[high]<(arr[middle]))
arr = swapper(arr, high, middle);
//Place pivot at position 'high' -1
arr = swapper(arr, middle, high -1);
int pivot = middle;
//Sort the elements relative to the pivot
int i,j;
for (i = low, j = high -1; ;)
{
while(arr[++i]<pivot)
;
while(pivot < (arr[--j]))
;
if (i<j)
arr = swapper(arr, i, j);
else
break;
}
//Restore pivot
arr = swapper(arr, i, high -1);
quickSort(arr, low, i-1);
quickSort(arr, i+1, high);
}
}
public void sort(int[] AnArray) {
System.out.println("Sort");
quickSort(AnArray, 0, AnArray.length -1);
}
}
--
Q: What do you get when you cross a mosquito with a rock climber?
A: Nothing. You can't cross a vector and a scalar.