BubbleSort Implementation

问题:

I tried to make an implementation of bubble sort, but I am not sure whether it is correct or not. If you can give it a look and if it is a bubble sort and can be done in better way please don't be shy. Here is the code:

package Exercises;

import java.util.*;

public class BubbleSort_6_18 
{
    public static void main(String[] args) 
    {
        Random generator = new Random();

        int[] list = new int[11];
        for(int i=0; i<list.length; i++)
        {
            list[i] = generator.nextInt(10);
        }

        System.out.println("Original Random array: ");
        printArray(list);

        bubbleSort(list);

        System.out.println("\nAfter bubble sort: ");
        printArray(list);
    }

    public static void bubbleSort(int[] list)
    {
        for(int i=0; i<list.length; i++)
        {
            for(int j=i + 1; j<list.length; j++)
            {
                if(list[i] > list[j])
                {
                    int temp = list[i];
                    list[i] = list[j];
                    list[j] = temp;
                }
            }

        }
    }

    public static void printArray(int[] list)
    {
        for(int i=0; i<list.length; i++)
        {
            System.out.print(list[i] + ", ");
        }
    }
}

回答1:

This is the calssical implementation for bubble sort and it seems to be OK. There are several optimizations that can be done, but the overall idea is the same. Here are some ideas:

• If there is an iteration of the outer cycle when no swap is performed in the inner cycle, then break, no use to continue
• On each iteration of the outer cycle swap the direction of the inner one - do it once left to right and then do it once right to left(this helps avoid elements moving slowly towards the right end).

回答2:

private static int [] bublesort (int[] list , int length) {

    boolean swap = true;
    int temp;

    while(swap){

        swap = false;

        for(int i = 0;i < list.length-1; i++){              
            if(list[i] > list[i+1]){
                temp = list[i];
                list[i] = list[i+1];
                list[i+1] = temp;                   
                swap = true;
            }
        }
    }
    return list;
}

回答3:

Mohammod Hossain implementation is quite good but he does alot of unecessary iterations, sadly he didnt accept my edit and i can't comment due to reputations points so here is how it should look like:

public void sort(int[] array) {
        int temp = 0;
        boolean swap = true;
        int range = array.length - 1;
        while (swap) {
            swap = false;
            for (int i = 0; i < range; i++) {
                if (array[i] > array[i + 1]) {
                    temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                    swap = true;
                }
            }
            range--;
        }
    }

回答4:

{
    System.out.println("The Elments Before Sorting:");
    for(i=0;i<a.length;i++)
    {
        System.out.print(a[i]+"\t");
    }
    for(i=1;i<=a.length-1;i++)
    {
      for(j=0;j<=a.length-i-1;j++)
      {
          if((a[j])>(a[j+1]))
          {
              temp=a[j];
              a[j]=a[j+1];
              a[j+1]=temp;
            }
       }
      System.out.println("The Elements After Sorting:");
      for(i=0;i<a.length;i++)
      {
            System.out.println(a[i]+"\t");
      }
    }
}

回答5:

I think you got the idea of bubble sort by looking at your code:

Bubble sort usually works like the following: Assume aNumber is some random number:

for (int i = 0; i < aNumber; i++)
{
     for(int j = 0; j < aNumber; j++)

      //Doing something with i and j, usually running it as a loop for 2D array
      //array[i][j] will give you a complete sort.
}

How bubble sort is it iterates through every single possible spot of the array. i x j times The down side to this is, it will take square the number of times to sort something. Not very efficient, but it does get the work done in the most easiest way.

回答6:

Short Answer: This is definitely NOT Bubble sort. It is a variant of Selection sort (a less efficient variant than the commonly known one).

It might be helpful to see a visualization of how they work on VisuAlgo

Why this is not bubble sort?

Because you loop over the array and compare each element to each other element on its right. if the right element is smaller you swap. Thus, at the end of the first outer loop iteration you will have the smallest element on the left most position and you have done N swaps in the worst case (think of a reverse-ordered array).

If you think about it, you did not really need to do all these swaps, you could have searched for the minimum value on the right then after you find it you swap. This is simply the idea of Selection sort, you select the min of remaining unsorted elements and put it in its correct position.

How does bubble sort look like then?

In bubble sort you always compare two adjacent elements and bubble the larger one to the right. At the end of the first iteration of the outer loop, you would have the largest element on the right-most position. The swap flag stops the outer loop when the array is already sorted.

void bubbleSort(int[] arr) {
    boolean swap = true;       
    for(int i = arr.length - 1; i > 0 && swap; i--) {
        swap = false;
        // for the unsorted part of the array, bubble the largest element to the right.
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j+1]) {
                // swap
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swap = true;
            }
        }
    }
}

回答7:

• You can loop over the array until no more elements are swapped
• When you put the element at the last position you know it's the largest, so you can recuce the inner loop by 1

回答8:

A bubblesort version with while loops from my first undergraduate year ("the BlueJ era").

public static void bubbleSort()
    {
        int[] r = randomArrayDisplayer();
        int i = r.length;
        while(i!=0){
            int j = 0;
            while(j!=i-1){
                if(r[j+1]<r[j]){
                    swap(r,j,j+1);
                }
                j++;
            }
            i--;
        }
    }

private static void swap(int[] r, int u, int v)
    {
       int value = r[u];
       r[u] = r[v];
       r[v] = value;
       arrayDisplayer(r);
    }

My advice is to display every step in order to be sure of the correct behaviour.

回答9:

public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {64, 34, 25, 12, 22, 11, 90};
        BubbleSort client=new BubbleSort();
        int[] result=client.bubbleSort(arr);
        for(int i:result)
        {
            System.out.println(i);
        }
    }
    public int[] bubbleSort(int[] arr)
    {
        int n=arr.length;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n-i-1;j++) 
                if(arr[j]>arr[j+1])
             swap(arr,j,j+1);   
        }
        return arr;
    }
    private int[] swap(int[] arr, int i, int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
        return arr;
    }


}

回答10:

Above code is looks like implementation Selection sort , it's not a bubble sort.

Please find below code for bubble sort.

Class BubbleSort {
public static void main(String []args) {
int n, c, d, swap;
Scanner in = new Scanner(System.in); 
System.out.println("Input number of integers to sort");
n = in.nextInt();

int array[] = new int[n]; 
System.out.println("Enter " + n + " integers");

for (c = 0; c < n; c++) 
  array[c] = in.nextInt();

for (c = 0; c < ( n - 1 ); c++) {
  for (d = 0; d < n - c - 1; d++) {
    if (array[d] > array[d+1]) /* For descending order use < */
    {
      swap       = array[d];
      array[d]   = array[d+1];
      array[d+1] = swap;
    }
  }
}

System.out.println("Sorted list of numbers");

for (c = 0; c < n; c++) 
  System.out.println(array[c]);
}
}

回答11:

/*
Implementation of Bubble sort using Java
*/

import java.util.Arrays;
import java.util.Scanner;


public class BubbleSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            System.out.println("Enter the number of elements of array");
            int n = in.nextInt();
            int []a = new int[n];
            System.out.println("Enter the integer array");
            for(int i=0; i<a.length; i++)
            {
                a[i]=in.nextInt();
            }
            System.out.println("UnSorted array: "+ Arrays.toString(a));         
            for(int i=0; i<n; i++)
            {
                for(int j=1; j<n; j++)
                {
                    if(a[j-1]>a[j])
                    {
                        int temp = a[j-1];
                        a[j-1]=a[j];
                        a[j]=temp;
                    }
                }
            }
            System.out.println("Sorted array: "+ Arrays.toString(a));           
    }
}


/*
****************************************
Time Complexity: O(n*n)
Space Complexity: O(1)
****************************************
*/

回答12:

class BubbleSort {

public static void main(String[] args) {

    int a[] = {5,4,3,2,1};
    int length = a.length - 1;

    for (int i = 0 ; i < length ; i++) {
        for (int j = 0 ; j < length-i ; j++) {
            if (a[j] > a[j+1]) {
                int swap = a[j];
                a[j] = a[j+1];
                a[j+1] = swap;
            }
        }
    }

    for (int x : a) {
        System.out.println(x);
    }
}

}

回答13:

Yes it seems to be Bubble sort swapping the elements

Bubble sort

void bubbleSort(int arr[])
{
    int n = arr.length;
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1])
            {
                // swap temp and arr[i]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
}

It will give in worst case O(n^2) and even if array is sorted.

回答14:

    int[] nums = new int[] { 6, 3, 2, 1, 7, 10, 9 };

        for(int i = nums.Length-1; i>=0; i--)
            for(int j = 0; j<i; j++)
            {
                int temp = 0;
                if( nums[j] < nums[j + 1])
                {
                    temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }