Problem with implementing bi-directional selection sort

Question

I am trying to implement bi-directional selection sort(double selection sort). A double-selection sort finds both the smallest and largest elements during its scan, and swaps the smallest into the first position, and the largest into the last position. The algorithm then proceeds looking at all the elements between the first and last.

I am able to get the logic required to perform the task.But,i think i am doing something wrong with comparing variables or maybe implementing comparable properly.

public void sort(T[] input) {

for(int i=0; i<input.length -1; i++){

    int min = i;
    int max = i;

    for(int j=i+1; j<input.length; j++){

        if(input[min].compareTo((input[j])) > 0  )
        {
            min = j;
            T swap = input[min];
            input[min] = input[i];
            input[i] = swap;

        }
    }

    for(int k=i+1; k<input.length; k++){

        if(input[max].compareTo((input[k])) < 0  )
        {
            max = k;
            T swap = input[max];
            input[max] = input[i];
            input[i] = swap;

        }
    }


}


}

///// Test File

   /** Returns true if the input array is ordered (every element ≤ 
    * the following one.)
    * 
    * @param data Array to check
     * @return     True if array is ordered
     */
    boolean isOrdered(Integer[] data) {
    for(int i = 0; i < data.length - 1; ++i)
        if(data[i] > data[i+1])
            return false;

    return true;
}

/** Counts the number of times x occurs in the array in.
 * 
 * @param in Array
 * @param x  Element to count
 * @return   Count of x's in the array
 */
int countElement(Integer[] in, Integer x) {
    int c = 0;
    for(int i : in) 
        if(i == x)
            c++;

    return c;
}

/** Returns true if both arrays contain the same elements, 
 * disregarding order (i.e., is one a permutation of the other).
 * @param in  Unsorted array
 * @param out Potentially-sorted array to check
 * @return    True if out is a permutation of in
 */
boolean sameElements(Integer[] in, Integer[] out) {
    for(Integer i : in)
        if(countElement(in,i) != countElement(out,i))
            return false;

    return true;
}

/** Creates an array of the given size filled with random values.
 * 
 * @param size Size of the resulting array
 * @return     Array of random values
 */
Integer[] randomArray(int size) {
    Integer[] arr = new Integer[size];
    for(int i = 0; i < size; ++i)
        arr[i] = Math.round((float)Math.random() * Integer.MAX_VALUE);

    return arr;
}

/** Tests the DoubleSelectionSort dss against the unsorted data.
 * 
 * @param dss  Sorter to use
 * @param data Array to sort and check
 */
void testSort(DoubleSelectionSort dss, Integer[] data) {
    Integer[] sorted = Arrays.copyOf(data, data.length);
    dss.sort(sorted);        

    assertTrue("Result of sort is not sorted in order", isOrdered(sorted));
    assertTrue("Result of sort has different elements from input", sameElements(data, sorted));
}

@Test
public void testSort() {
    System.out.println("sort");
    DoubleSelectionSort<Integer> dss = new DoubleSelectionSort<>();

    // Test on arrays size 0 to 100
    for(int i = 0; i <= 100; ++i)
        testSort(dss, randomArray(i));               
  }

}

testSort Failed : Result of Sort is not sorted in order

Answer 1

It seems that you are using wrong conditions in Sorting Logic of Selection Sort. I have given here example of Selection Sort function with generic type. Please have a look at this:

public static <E extends Comparable<E>> void selectionSort(E[] list)
{
    for(int i=0; i<list.length -1; i++)
    {
        int iSmall = i;

        for(int j=i+1; j<list.length; j++)
        {
            if(list[iSmall].compareTo((list[j])) > 0  )
            {
                iSmall = j;
            }
        }
        E iSwap = list[iSmall];
        list[iSmall] = list[i];
        list[i] = iSwap;

    }
}