3
\$\begingroup\$

Just to enjoy, I want to implement selection and bubble sorts algorithms without looking any implementation by my own efforts 💪💪. Is there any redundant/lack part(s)? After improved their implementations, I think to try to write them down as recursive, can I ?, any hint?

class Sorts {

    public static void main(String[] args) {
        int[] arrSelection = { 8, 6, 3, 1 };
        selectionSort(arrSelection);
        for (int i : arrSelection ) {
            System.out.print(i + "  ");
        }

        System.out.print("\n");

        int[] arrBubble = { 8, 6, 3, 1 };
        bubbleSort(arrBubble);
        for (int i : arrBubble ) {
            System.out.print(i + "  ");
        }

    }

    // swap helper for java
    private static int returnFirst(int x, int y) {
        return x;
    }

    public static void selectionSort(int[] arr) {
        int lengthOfInputArray = arr.length;
        int min;
        int min_index;

        for (int i = 0; i < lengthOfInputArray - 1; i++) {
            min = arr[i];
            min_index = i;
            for (int j = i+1; j < lengthOfInputArray; j++) {
                if (min > arr[j]) {
                    min = arr[j];
                    min_index = j;
                }
            }
            if (min_index != i) {
                // swap(arr[i], arr[min_index])
                arr[i] = returnFirst(arr[min_index], arr[min_index] = arr[i]);
            }
        }
    }

    public static void bubbleSort(int[] arr) {
        int lengthOfInputArray = arr.length;

        for (int i = 0; i < lengthOfInputArray; i++)
            for (int j = 0; j < lengthOfInputArray - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // swap(arr[j], arr[j + 1])
                    arr[j] = returnFirst(arr[j + 1], arr[j + 1] = arr[j]);
                }
            }
    }

}
\$\endgroup\$
  • \$\begingroup\$ sorting.at \$\endgroup\$ – snr Apr 29 '18 at 9:52
3
\$\begingroup\$

In addition to the other answers, there are a couple common bubble sort optimizations that you can employ.

First, your inner loop steps through the entire array each time. This is unnecessary because each pass through the array is guaranteed to sink the largest value to the bottom, so the tail of the array is always sorted. You can avoid processing the sorted bits of the array by using

for (int j = 0; j < lengthOfInputArray - (i + 1); j++) {
    ...
}

for the inner loop.

Second, you can shortcut processing by ending when the inner loop encounters no swaps.

public static void bubbleSort(int[] arr) {
    boolean swapped = false;

    for (int i = 0; i < arr.length; i++) {
        swapped = false;
        for (int j = 0; j < arr.length - (i + 1); j++) {
            if (arr[j] > arr[j + 1]) {
                if (swap(arr, j, j + 1)) {
                    swapped = true;
                }
            }
        }
        if (!swapped) {
            break;
        }
    }
}

This only happens when the array is fully sorted. So if you start out with a sorted array, then you only have to run through the array once.

Third, the outer loop does not have to be processed once for each element in the array. Take a five element array for example. It is iterated in the following manner:

value of i      max j required
----------      --------------
    0                 3
    1                 2
    2                 1
    3                 0

So the outer loop only needs to be processed arr.length - 1 times. The final optimized bubble sort would look something like this:

public static void bubbleSort(int[] arr) {
    boolean swapped = false;

    for (int i = 0; i < arr.length - 1; i++) {
        swapped = false;
        for (int j = 0; j < arr.length - (i + 1); j++) {
            if (arr[j] > arr[j + 1]) {
                if (swap(arr, j, j + 1)) {
                    swapped = true;
                }
            }
        }
        if (!swapped) {
            break;
        }
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This is unnecessary because each pass through the array is guaranteed to sink the largest value to the bottom, so the tail of the array is always sorted. +1 \$\endgroup\$ – snr Apr 25 '18 at 16:13
2
\$\begingroup\$

This returnFirst() helper doesn't really help you much in performing a swap. I can see from your pseudo-code, that you'd really like a helper like this:

swap(arr[i], arr[min_index])

Java doesn't allow you to implement it like that, but you could implement a swap function like that:

swap(arr, firstIndex, secondIndex)

Additionally:

  • There's no real need for the lengthOfInputArray variable. Using arr.length directly would make your code simpler.
  • In selection sort, you could extract the inner loop into a helper like findMinIndex().
  • Also in there, you don't need to avoid the swap operation when elements equal - it'll keep the code simpler when you just always swap them. When you're concerned with performance... you should not be implementing a selection/bubble sort to begin with.

Regarding a plan to implement them recursively, I would suggest you instead look into implementing an algorithm like merge sort or quick sort, which are recursive in nature.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

I prefer printing out arrays with the built in function: System.out.println(Arrays.toString(array));


Comments should tell us why some code is written as it is, not what it does. Just to be able to understand that arr[j] = returnFirst(arr[j + 1], arr[j + 1] = arr[j]); actually swaps the 2 elements correctly you need to have a decent understanding on how the java compiler handles assignments and that methods are called by value and hope that JIT compilers will never be smart enough to inline your method to return the first parameter. This isn't trivial at all. I would very much prefer to see a line like: swap(arr, j, j+1) instead. The implementation is trivial using a temp variable anyway.


Java convention says to use lowerCamelCasing for variables. Don't use _. Funny how you did it right for lengthOfInputArray.


lengthOfInputArray is redundant. arr.length is really obvious already on what it is. There's no need to create an extra variable with a "better" name.


ALWAYS put braces after each for/if/while/... statement. In your bubble sort, if someone is interested in printing out which item is currently being handled to see how slow it works they might just do this:

    for (int i = 0; i < lengthOfInputArray; i++)
        System.out.println("Currently handling index:"+i);
        for (int j = 0; j < lengthOfInputArray - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // swap(arr[j], arr[j + 1])
                arr[j] = returnFirst(arr[j + 1], arr[j + 1] = arr[j]);
            }
        }

and are in for a really annoying debug session on why the algorithm suddenly doesn't sort the array anymore.


I think to try to write them down as recursive, can I ?

Sure you can. But it'll be less readable, slower and can only handle a certain array length (depending on implementation and max heap size about 30k items big). So I would greatly advise you not to force recursion into the implementation of these 2 sorting algorithms.

Other algorithms that use a divide-and-conquer strategy are way better suited if you want to play around with recursion. Take for example merge sort. In pseudocode this becomes something like:

public mergeSort(int[] arr, int from, int to){
    if(to-from < 1) return;
    mergeSort(arr, from, (to-from)/2+from);
    mergeSort(arr, (to-from)/2+from, to);
    //merge 2 sorted halves together
}

If you really want to write your current 2 algorithms using recursion (despite being worse in every aspect) just because you can I suggest following approach:

public void someSort(int[] arr, int from){
    if(from >= arr.length) return; //stopping condition

    // do whatever is inside your outer for loop here, but without the actual outer loop.

    someSort(arr, from+1);
}

A final note: this is a tail recursive call, which isn't optimised at all in java. Each previous method in the recursion remains on the stack until you return from that method at the end.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.