javasortingselection-sort

Valid selection sort algorithm?


I've written the following method that uses selection sort to sort an array:

public T[] selection(T[] arr)
{
   T temp, min;
   for(int i = 0; i < arr.length-1; i++)
   {
      for(int j = i + 1; j < arr.length; j++)
      {
         min = arr[i];
         if(min.compareTo(arr[j]) > 0)
         {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
         }
      }
   return arr;
}

However, I am having trouble distinguishing my algorithm from a bubble sort. Does my sorting method pass for a selection sort method?


Solution

  • Your algorithm is actually something called exchange sort.

    In selection sort, you run a pass over the array to locate the smallest element. Whenever an element is found smaller than the smallest one discovered so far, you make a note of its position, but don’t move or swap it. Only once you’ve finished scanning the array elements do you swap the item you found to an earlier spot in the array. This means you always do a total of at most n - 1 swaps, one per iteration of the outer loop.

    That doesn’t correspond with what you have in your code, because you’re performing multiple swaps per iteration of the outer i loop. The algorithm you have is called exchange sort. It’s a legal sorting algorithm, and like selection sort at the end of each iteration of the outer i loop you’ll have correctly placed another element, but it runs slower than a true selection sort because you’re making many more swaps than are needed.