Search code examples
javaarraysbubble-sortselection-sort

Will this code be considered bubble or selection sort?


Could you please help identify what sorting method is this?

public static int[] sort(int arr[]) {
    int temp1 = 0;
    for (int i = 0; i < arr.length; i++) {
        System.out.println(Arrays.toString(arr));
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[i]) {
                temp1 = arr[i];
                arr[i] = arr[j];
                arr[j] = temp1;
            }
        }
    }
    return arr;
}

Solution

  • Neither. It is close to selection sort, but makes unnecessary swaps.

    Bubble sort makes pair-wise swaps on subsequent elements, until the "lightest" element is at top, like a bubble goes up in fluid.

    int unorderedLen = arr.length;
    do {
      int newUnorderedLen = 0;
      // after a cycle, largest element will be at top
      for (int i = 1; i < unorderedLen; j++) {
        if (arr[i-1] > arr[i]) {
          newUnorderedLen = i;
          swap(arr, i, i-1);
        }
      }
      unorderedLen = newUnorderedLen;
    } while (unorderedLen > 0);
    

    Selection sort searches and selects the place where an element should fit and makes a single swap after.

    // at i. cycle, we select i. least element and place at i.
    for (int i = 0; i < arr.length-1; i++) {
      int minIndex = i;
      // search for least element in the remaining unsorted
      for (int j = i+1; j < arr.length; j++) {
        if (arr[j] < arr[minIndex]) {
          minIndex = j;
        }
      }
      if (minIndex != i) {
        swap(arr, minIndex, i);
      }
    }