Sorting and removing duplicates

[Shane]

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);
}
System.out.println("");
sort(AnArray);
for (i =0;i<AnArray.length;i++){
System.out.println(i +" : "+AnArray);
}
System.out.println("\nmkUniq\n");
mkUniq(AnArray);
for (i =0;i<AnArray.length;i++){
System.out.println(i +" : "+AnArray);
}
return AnArray;
}

public int[] mkUniq(int[] AnArray){
for (int i =0;i<AnArray.length;i++){
System.out.println(i +" : "+AnArray);
}
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 != AnArray[i-1])
{
myArray[cloneCount] = AnArray;
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);

}
}

 

[Patricia Shanahan]

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 assume you are looking for advice on what to do next, when your
program does not do exactly what you want, and it is not obvious to you why.

I've written a description of one approach to debug, see
http://home.earthlink.net/~patricia_shanahan/debug/

Patricia

 

[Shane]

...

I assume you are looking for advice on what to do next, when your
program does not do exactly what you want, and it is not obvious to you
why.

I've written a description of one approach to debug, see
http://home.earthlink.net/~patricia_shanahan/debug/

Patricia

Hi
In a way no. I do not understand why a module that works as desired
when "freestanding" is not behaving the same way when called from another
module.

This is the output of the code I have already presented, when called with
the following array:

int[] testArray = new int[10];
testArray[0] = 5;
testArray[1] = 9;
testArray[2] = 5;
testArray[3] = 2;
testArray[4] = 1;
testArray[5] = 12;
testArray[6] = 5;
testArray[7] = 28;
testArray[8] = 3;
testArray[9] = 4;


Output:
Sort

Step 1
0 : 1
1 : 2
2 : 3
3 : 4
4 : 5
5 : 5
6 : 5
7 : 9
8 : 12
9 : 28

0 : 1
1 : 2
2 : 3
3 : 5
4 : 4
5 : 5
6 : 5
7 : 12
8 : 9
9 : 28

mkUniq

0 : 1
1 : 2
2 : 3
3 : 5
4 : 4
5 : 5
6 : 5
7 : 12
8 : 9
9 : 28
0 : 1
1 : 2
2 : 3
3 : 5
4 : 4
5 : 5
6 : 5
7 : 12
8 : 9
9 : 28


As can be seen when the sort method is called on the unsorted array, it
returns a sorted array. When the sort method is called on what is then a
sorted array, it returns an unsorted array. My removal of duplicates
relies on the array being sorted.

 

[Patricia Shanahan]

Hi
In a way no. I do not understand why a module that works as desired
when "freestanding" is not behaving the same way when called from another
module.

....

In that situation, I would have two alternative theories:

1. A bug in the sort method that makes it fail for some inputs, but not
others.

2. A bug in how the sort method is being called when it is not
"freestanding".

You could find out which is true by replacing, just for debug purposes,
your sort with Arrays.sort. If it works with Arrays.sort, the problem is
in your sort code. If it does not work with Arrays.sort, the problem is
in how it is being called when it fails.

Patricia

 

[Z.]

I have been asked to implement quicksort (or mergesort) in an application,
and then remove any duplicates.

Why reinvent sorting?

Why not just use Arrays.sort() ?

 

[Patricia Shanahan]

Why reinvent sorting?

Why not just use Arrays.sort() ?

Shane explained later in the article "I am not allowed to use the
Collections sort method, as that would defeat the purpose of me
implementing one of the sorting methods.".

Patricia

 

[Shane]

...

In that situation, I would have two alternative theories:

1. A bug in the sort method that makes it fail for some inputs, but not
others.

I think this is my best place to start looking, specifically at input arrays
which are already sorted.

2. A bug in how the sort method is being called when it is not
"freestanding".

This is what I was concerned about. I believe that when I call sort(int[]
AnArray) I am calling a 'driver' for quickSort(int []arr, int low, int
high)
I tried calling quickSort(int []arr, int low, int high) instead, but got the
same result.

 

[Shane]

Shane wrote:

//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]))
;

I am doing two things wrong here. I am comparing arr to pivot (pivot is
an index, not a value held at the index)
And pivot is pointing at the middle of the array, when it should be pointing
at the high-1 position (the value held at middle is moved to 'high -1' in
order to get it out of the way)

 

[Z.]

Shane explained later in the article "I am not allowed to use the
Collections sort method, as that would defeat the purpose of me
implementing one of the sorting methods.".

Oh, duh! How did I miss that?! (embarrassed look)