Problem Solutions: Problem 27 Bubble Sort help

leapingmanx 2015-11-13 18:42:56

I've been attempting the last few days to figure out a way to make my code efficient enough to match the example's number. So far however I've only managed to get my code to properly sort the numbers, while leaving the number of passes too high to match. Any suggestions or ideas of how to tackle this are much appreciated.

package solution;

import java.util.*;

public class Solution {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        int length = input.nextInt();
        int[] toSort = new int[length];
        int pass = 0;
        int changes = 0;

        for(int i = 0; i < toSort.length; i++){
            toSort[i] = input.nextInt();
        }

        for(int i = 1; i < toSort.length - 1; i++){
            int a;
            if(toSort[i] > toSort[i+1]){
                a = toSort[i];
                toSort[i] = toSort[i + 1];
                toSort[i + 1] = a;
                changes++;
            }
            if(toSort[i] < toSort[i-1]){
                a = toSort[i];
                toSort[i] = toSort[i-1];
                toSort[i-1] = a;
                i = 1;
                changes++;
            }
            pass++;
        }

        System.out.println(Arrays.toString(toSort));
        System.out.print(" " + pass + " " + changes);

        input.close();
    }
}

Rodion (admin) 2015-11-13 19:17:45

Hi! Thanks for your message!

Let us see. At first, the Bubble Sort anyway consists of two loops, one nested inside the other, like this:

for ....
    for ....
        if numbers-are-swapped
            swap them
            changes++
        end-if
    end-for
    passes++
end-for

The internal one performs a single pass. During this pass the largest element is pushed to the end.

The outer loop makes passes repeat until all array is sorted.

Your code has only one loop so it do not perform BubbleSort. Moreover I'm not sure it performs complete sorting - it looks like for some inputs the result is not perfectly sorted.

Another thing is that the two "ifs" inside are unnecessary - normally one will left no job for the other...

Try to implement the algorithm as it is described in the problem statement. Implement the internal loop (performing pass) first, make sure it works. Then wrap it into outer loop.

Alternatively it is, of course, safe to switch to other problems temporarily - they may help to get used to nested loops etc.

developer10 2016-04-24 20:08:08

@Admin, doesn't your pseudo-code imply that the number of passes should be equal to the array size? If so, then the Problem Statement for this problem seems to be incorrect:

input data:
8
3 1 4 1 5 9 2 6

answer:
5 8

Is there something I'm missing here?

Quandray 2016-04-25 11:50:20

When you do a pass and find nothing needs to be swapped, the array is sorted and no further passes are needed.