0

Attempting to implement a recursive method to sort an array of integers:

    public static void bubbleSort(int[] arr, int n){

      int index = n-1;

      System.out.println("Round number: " + n);
      System.out.println(Arrays.toString(arr));

      while(index>=1)
      {
          if(arr[index] <  arr[index-1])
              swap(arr, index, index-1);


          index--;
      }
      if(n>1)
          bubbleSort(arr, n-1);
  }

}

It seems to work fine for the first few rounds, moving the smallest integer in the set to the front, but it just stops working around midway. Any idea why? Thanks!

Improve this question
2
  • Stops working,meaning?does the program crash,output incorrect values or throws exceptions? stop working is to generic Commented Aug 6, 2013 at 1:13
  • @Sello it means that he tried it on a small test-set and it worked and when he tried it on a bigger/more complex test-set it didn't complete the sorting (the output was an un-sorted array) Commented Aug 6, 2013 at 2:01

3 Answers 3

Reset to default
3

Your algorithm moves the smallest value to the start of the array each time, then ignores the last element on subsequent calls. Unfortunately the last element isn't guaranteed to be the largest.

One way to fix it might be to initialise index to arr.length - 1, and continue the loop while index > arr.length - n.

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

12 Comments

@alfasin - I posted the required changes. I tested by taking the code from the question, making the changes and only the changes given in my answer, and running it. What else do you need to know?
I tested your answer (with the code in the question) and it didn't work for me. maybe it's my bad for not implementing it properly - but then again - if I could be mistaken - so could anyone... why don't you post your code so there could be no confusions ?
@sje397 if I explicitly asked for it it's obviously neither redundant nor useless to me. I still think that your answer is wrong, but I'd be happy if you'll prove me wrong (and of course that I'll cancel the downvote + upvote your answer).
@alfasin That's not at all obvious. People think they need things when they don't all the time. You can think what you like.
"People think they need things" - are you pulling philosophy BS on me now ? :))) If you were right you would update your answer with 4-5 lines of code that would prove me wrong, so either you're too lazy to do that or you're just wrong and not admitting it - both options are not very dignifying but like you implied - you don't owe me nothing. Good luck with that approach!
|
1

Try this:

import java.util.*;

public class Test{
    public static void main(String[] args){
        int[] ttt = {9,8,7,6,5,4,3,2,1};

        bubbleSort(ttt, ttt.length);
    }

    public static void bubbleSort(int[] arr, int n){
        int index = 0;

        System.out.println("Round number: " + n);
        System.out.println(Arrays.toString(arr));

        while(index < n - 1){
            if(arr[index] >  arr[index + 1]){
                swap(arr, index, index + 1);
            }
            index++;
        }

        if(n > 1){
            bubbleSort(arr, n-1);
        }
    }

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

In your case on every round you guarantee that by the end of every round you will have the smallest number pushed to its place, but then leave out the last element of an array, which is not necessarily the largest number. You should do it in reverse order, push the largest number to its place and then leave it out in the next round.

http://en.wikipedia.org/wiki/File:Bubble-sort-example-300px.gif

FYI: Bubble sort's worst case performance is O(n^2), maybe you'd want to implement better sort algorithms like quicksort or merge sort?

Improve this answer

2 Comments

I think your answer is better than mine, and extra points for pointing out the inefficiency of bubble sorting.
Thank you! I got it working after that. I understand the inefficiency of bubble sorting, but it's for practice! Attempting quick/merge sort right now.
1

Change the if condition to:

...
if(arr[index] <  arr[index-1]){
   swap(arr, index, index-1);
   index = n;
}
index--;
...

The problem is that after you find an array member to "delegate" across the array - you need to "restart" cause there could be other members that needs to be "reconsidered". Run with a debugger and see what I mean if I'm not clear enough with my description.

Full solution:

import java.util.Arrays;

/**
 * User: alfasin
 * Date: 8/5/13
 */
public class BubbleSort {

    public static void bubbleSort(int[] arr, int n){

        int index = n-1;

        System.out.println("Round number: " + n);
        System.out.println(Arrays.toString(arr));

        while(index>=1)
        {
            if(arr[index] <  arr[index-1]){
                swap(arr, index, index-1);
                index = n;
            }
            index--;
        }
        if(n>1)
            bubbleSort(arr, n-1);
    }

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

    public static void main(String...args){
        int[] arr = {4,2,9,6,2,8,1};
        bubbleSort(arr, arr.length);
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i]+" ");
        }
    }

}

Like sjee397 suggested - this is more of a "version" of bubble sort...

A more "conservative" version of bubble sort:

public static void bubbleSort(int[] arr, int n){
        boolean swapped= true;
        while (swapped){
            swapped = false;
            for(int i=0; i<arr.length-1; i++){
                if(arr[i]>arr[i+1]){
                    swap(arr,i,i+1);
                    swapped = true;
                }
            }
        }
    }
Improve this answer

8 Comments

You're still doing too much. In a normal bubble sort, every iteration puts one element in the correct place (in the OP, it's the first element, and in your 'conservative' version, it's the last). So, each iteration of the sort, you can reduce the number of items you look at in the list by one. You're still iterating the entire array every time. In your version, you could add a counter for the number of times the while loop is called, say n, and change your for loop condition to i < arr.length - n - 1.
@sje397 now, if I understood you correctly - that would be an optimized version of bubble sort - not the "conservative" one - at least according to wiki: en.wikipedia.org/wiki/Bubble_sort#Pseudocode_implementation
BTW, I think that you need to do i < arr.length - n + 1 - cause you have to repeat till the place of the last "swapped" item inclusive - cause it that same spot there could be now another item that should be swapped.
You're right, they're both bubble sorts. I didn't recognise your first snippet as the less optimal bubble sort at first, and I should have, but I didn't mean to imply that the non-optimal version was not a bubble sort.
You don't want +1 - that will take your index out of range when n = 0.
|

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.