Thanks for sharing your code.
Your example is a typical case of duplicated code you have two places where the code looks very similar (and is logically the same) but has some minor differences.
On the other hand your example is a special case because we can simply convert the input of one of the duplicated parts to the form of the other one:
public class Sort {
private static <E extends Comparable<E>> void swap(List<E> sequence,
int positionOne, int positionTwo) {
E temp = sequence.get(positionOne);
sequence.set(positionOne, sequence.get(positionTwo));
sequence.set(positionTwo, temp);
}
public static <E extends Comparable<E>> List<E> selectionSort(List<E> sequence) {
for (int i = 0; i < sequence.size(); i++) {
int minPosition = -1;
E minValue = sequence.get(i);
for (int j = i + 1; j < sequence.size(); j++) {
E secondPosition = sequence.get(j);
if (minValue.compareTo(secondPosition) > 0) {
minPosition = j;
minValue = sequence.get(j);
}
}
if (minPosition >= 0) {
swap(sequence, i, minPosition);
}
}
return sequence;
}
public static <E extends Comparable<E>> E[] selectionSort(E[] sequence) {
return selectionSort(new ArrayList(Arrays.asList(sequence))).toArray(new E[sequence.length]);
}
public static void main(String[] args) {
Integer[] integers = {1, 6, 88, 7, 44, 3, 11};
System.out.println("Before: " + Arrays.toString(integers));
Sort.selectionSort(integers);
System.out.println("Later: " + Arrays.toString(integers));
}
}
However...
The more general approach is to refactor one (or both) of the similar code fragments to make them (partially) the same.
In your example the difference at both places is the way the elements are addressed and accessed. We need to introduce an indirection, to provide an input type independent way to do this.
In this example an interface is the way to go:
interface MySequence<E extends Comparable<E>>{
E getElementAt(int index);
void setElementAt(int index, E element);
int elementCount();
}
You could "reuse" method names from one of the duplicated parts but I intentionally use different names to make my point...
Now in each of the methods we first create an anonymous inner class from this interface. Lets start with the two swap() methods:
private static <E extends Comparable<E>> void swap(List<E> sequence, int positionOne, int positionTwo) {
MySequence<E> mySequence = new MySequence<E>() {
public E getElementAt(int index) {
return sequence.get(index);
}
public void setElementAt(int index, E element) {
sequence.set(index, element);
}
public int elementCount() {
return sequence.size();
}
};
E temp = sequence.get(positionOne);
sequence.set(positionOne, sequence.get(positionTwo));
sequence.set(positionTwo, temp);
}
private static <E extends Comparable<E>> void swap(E[] sequence, int positionOne, int positionTwo) {
MySequence<E> mySequence = new MySequence<E>() {
public E getElementAt(int index) {
return sequence[index];
}
public void setElementAt(int index, E element) {
sequence[index] = element;
}
public int elementCount() {
return sequence.length;
}
};
E temp = sequence[positionOne];
sequence[positionOne] = sequence[positionTwo];
sequence[positionTwo] = temp;
}
Then we replace any following occurrence of sequence in that method with mySequence:
private static <E extends Comparable<E>> void swap(List<E> sequence, int positionOne, int positionTwo) {
MySequence<E> mySequence = new MySequence<E>() {
public E getElementAt(int index) {
return sequence.get(index);
}
public void setElementAt(int index, E element) {
sequence.set(index, element);
}
public int elementCount() {
return sequence.size();
}
};
E temp = mySequence.getElementAt(positionOne);
mySequence.setElementAt(positionOne, mySequence.getElementAt(positionTwo));
mySequence.setElementAt(positionTwo, temp);
}
You hopefully can do this for the other version of swap() yourself...
Now both swap() methods had a differing part (the anonymous inner class of type MySequence) and a equal part (the thee following lines).
Actually we have more code then before, but we are going to reduce it in a few minutes...
Select the three identical lines in one of the methods and
apply your IDEs automated refactoring extract method to create a new version of swap():
private static <E extends Comparable<E>> void swap(MySequence<E> mySequence, int positionOne, int positionTwo) {
E temp = mySequence.getElementAt(positionOne);
mySequence.setElementAt(positionOne, mySequence.getElementAt(positionTwo));
mySequence.setElementAt(positionTwo, temp);
}
private static <E extends Comparable<E>> void swap(List<E> sequence, int positionOne, int positionTwo) {
MySequence<E> mySequence = new MySequence<E>() {
public E getElementAt(int index) {
return sequence.get(index);
}
public void setElementAt(int index, E element) {
sequence.set(index, element);
}
public int elementCount() {
return sequence.size();
}
};
swap(mySequence, positionOne, positionTwo);
}
The replace the three duplicated lines in the other original swap() method with a call to the new one too.
private static <E extends Comparable<E>> void swap(E[] sequence, int positionOne, int positionTwo) {
MySequence<E> mySequence = new MySequence<E>() {
public E getElementAt(int index) {
return sequence[index];
}
public void setElementAt(int index, E element) {
sequence[index] = element;
}
public int elementCount() {
return sequence.length;
}
};
swap(mySequence, positionOne, positionTwo);
}
Next step is to remove the old versions of swap(). click on the name if one of these and invoke your IDEs automated refactoring inline method. Repeat this with the otehr old version too.
Now your selectionSort() methods look like this:
public static <E extends Comparable<E>> List<E> selectionSort(List<E> sequence) {
for (int i = 0; i < sequence.size(); i++) {
int minPosition = -1;
E minValue = sequence.get(i);
for (int j = i + 1; j < sequence.size(); j++) {
E secondPosition = sequence.get(j);
if (minValue.compareTo(secondPosition) > 0) {
minPosition = j;
minValue = sequence.get(j);
}
}
if (minPosition >= 0) {
MySequence<E> mySequence = new MySequence<E>() {
public E getElementAt(int index) {
return sequence.get(index);
}
public void setElementAt(int index, E element) {
sequence.set(index, element);
}
public int elementCount() {
return sequence.size();
}
};
swap(mySequence, i, minPosition);
}
}
return sequence;
}
Here we move the instantiation of MySequence to the top of each method:
public static <E extends Comparable<E>> List<E> selectionSort(List<E> sequence) {
MySequence<E> mySequence = new MySequence<E>() {
public E getElementAt(int index) {
return sequence.get(index);
}
public void setElementAt(int index, E element) {
sequence.set(index, element);
}
public int elementCount() {
return sequence.size();
}
};
for (int i = 0; i < sequence.size(); i++) {
int minPosition = -1;
E minValue = sequence.get(i);
for (int j = i + 1; j < sequence.size(); j++) {
E secondPosition = sequence.get(j);
if (minValue.compareTo(secondPosition) > 0) {
minPosition = j;
minValue = sequence.get(j);
}
}
if (minPosition >= 0) {
swap(mySequence, i, minPosition);
}
}
return sequence;
}
And again we change any further occurence of sequence within each method to mySequence:
public static <E extends Comparable<E>> List<E> selectionSort(List<E> sequence) {
MySequence<E> mySequence = new MySequence<E>() {
public E getElementAt(int index) {
return sequence.get(index);
}
public void setElementAt(int index, E element) {
sequence.set(index, element);
}
public int elementCount() {
return sequence.size();
}
};
for (int i = 0; i < mySequence.elementCount(); i++) {
int minPosition = -1;
E minValue = mySequence.getElementAt(i);
for (int j = i + 1; j < mySequence.elementCount(); j++) {
E secondPosition = mySequence.getElementAt(i);
if (minValue.compareTo(secondPosition) > 0) {
minPosition = j;
minValue = mySequence.getElementAt(i);
}
}
if (minPosition >= 0) {
swap(mySequence, i, minPosition);
}
}
return sequence;
}
No we apply the same technique as with the swap() method. Move the identical lines of both methods to a new method using your IDEs automated refactoring extract method:
private static <E extends Comparable<E>> void selectionSort(MySequence<E> mySequence) {
for (int i = 0; i < mySequence.elementCount(); i++) {
int minPosition = -1;
E minValue = mySequence.getElementAt(i);
for (int j = i + 1; j < mySequence.elementCount(); j++) {
E secondPosition = mySequence.getElementAt(i);
if (minValue.compareTo(secondPosition) > 0) {
minPosition = j;
minValue = mySequence.getElementAt(i);
}
}
if (minPosition >= 0) {
swap(mySequence, i, minPosition);
}
}
}
public static <E extends Comparable<E>> List<E> selectionSort(List<E> sequence) {
MySequence<E> mySequence = new MySequence<E>() {
public E getElementAt(int index) {
return sequence.get(index);
}
public void setElementAt(int index, E element) {
sequence.set(index, element);
}
public int elementCount() {
return sequence.size();
}
};
selectionSort(mySequence);
return sequence; // ATTENTION! this line is NOT identical because of the type of sequence...
}
And replace the extracted part in the other original selectionSort() method too.
Thats it!
The code might even be shorter if we would use tree functional interfaces and lambda expression at the cost of more parameters at the new methods instead of one interface. But I doubt that it would increase readability and it definitely would add possibilities for errors.
The important insight is that we did not change the logic of the program since all changes we did are safe in that respect.
Nevertheless you should always have a set of automated UnitTest to guard your refactorings...
Collections.sort()andArrays.sort()? \$\endgroup\$Sort.insertionSort(myList)and not use the default tim sort \$\endgroup\$