2

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?

3
  • 1
    That does look like bubble sort. If you want selection sort, the j loop should find where the minimum is and after the j loop ends, you do one swap to bring that element to the bottom. Commented Nov 18, 2021 at 20:23
  • If you are sorting in ascending you can simply use Arrays.sort(arr), import java.util.Arrays Commented Nov 18, 2021 at 20:23
  • @snd Thank you, but I already know that. My main objective is to make methods of all the sorting algorithms on my own. Commented Nov 18, 2021 at 21:00

4 Answers 4

3

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.

Sign up to request clarification or add additional context in comments.

Comments

2

Your implementation is definitely similar to the selection sort, but the swap should happen outside the nested loop. Within the innermost loop you should only save the index of the smallest element among the ones left to sort (I've misread you if placement during my first editing of the answer).

The main difference between selection sort and bubble sort is mainly, but not entirely, in their nested loop. In fact, the selection sort tries in its nested loop to find the smallest element after i and then places it at the i-th position. In this way, at each iteration of the outer loop it is guaranteed that the i-th element corresponds to the smallest among the ones left to sort (from i to n-1).

public void selectionSort(int[] arr){
    int temp, min;
    
    // At every iteration, the outer loop checks whether the i-th element is already at the right place,
    // i.e. being the smallest value among the ones that follow it
    for (int i = 0; i < arr.length-1; i++) {

        //Assuming that the element in position i is the smallest among the ones left to sort
        min = i;

        //At every iteration of the outer loop, the innermost loop checks if there's a smaller value than the one in position i
        for (int j = i + 1; j < arr.length; j++) {

            //If a smaller value than the min-th element is found then j is stored as the current smallest index
            if (arr[min] > arr[j]) {
                min = j;
            }
        }

        //Swapping the smallest element found with the one in position i.
        //If min is still equal to i then no actual swap happens
        temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

On the other hand, the bubble sort algorithm achieves the same thing but instead of traversing from left to right, it iterates from right to left carrying with it the new smallest element it encounters.

public void bubbleSort(int[] vet) {
    int temp;

    //At every iteration, the outermost loop checks if there are any elements after i which are smaller than it
    for (int i = 0; i < vet.length - 1; i++) {
        // The innermost loop starts from the right bound 'till the i index.
        // Every time this loop finds in [j-1] a bigger element than the one in [j], 
        // then these two are swapped to carry along the smaller element in position j during the traverse.
        // Instead if the element in [j-1] is smaller than the one in [j], 
        // then it leaves them like that and keeps carrying [j-1] along instead of [j].
        for (int j = vet.length - 1; j >= i + 1; j--) {
            if (vet[j] < (vet[j - 1])) {
                temp = vet[j];
                vet[j] = vet[j - 1];
                vet[j - 1] = temp;
            }
        }
    }
}

Comments

0
public final class SelectionSort {

    public static void sortAsc(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++)
            swap(arr, i, getMinIndex(arr, i));
    }

    private static int getMinIndex(int[] arr, int i) {
        int minIndex = i;

        for (; i < arr.length; i++)
            if (arr[i] < arr[minIndex])
                minIndex = i;

        return minIndex;
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}

Comments

-2

Since your initial approach switches elements everytime a smaller one is found, it is similar to bubble sort. When using selection sort, you should first identify the array's minimal element in the unsorted portion and then replace it with the portion's first element.

Here's the corrected version:

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

This version adheres to the selection sort procedure correctly, identifying the minimal part in this process and switching it just once each iteration.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.