CODEWITHSUNDEEP
javaarraysalgorithmsortingbubble-sort
Zarar Mahmud
Zarar Mahmud

Reputation: 197

Bubble Sorting not working

I was working with the Bubble sorting algorithm and implemented it on code. The objective is to sort an integer array of size N using bubble sorting , count the number of data comparisons and the number of data movements , where data comparisons are the amount of times the integer are compared and data movements are the amount of the integers swap places . Finally we only calculate the time taken to execute the sorting. Now, the issue is when the value of N is a large number say 1000 / 10000 /20000 etc. for the first 30-50 test cases the bubble sorting works but after that , it is seen that a many smaller numbers have not been sorted. One more thing to keep in mind is that I assigned the values of the elements of the array to random numbers.

import java.util.Random;
import java.util.Scanner;

public class Bubblesort {
public static long DC;
public static long DM;

public static int[] BBSort(int arr[],int n) {
    int K,t,tmp;

    long Data_comp=0,Data_move=0;

    K = n;
    while(K!=0)
    {
        t = 0;
        for (int i = 0; i < K-1; i++) {

            if(arr[i]>arr[i+1])
            {
               tmp = arr[i];
               arr[i] = arr[i+1];
               arr[i+1] = tmp;
               t = i;
               Data_move++;
            }
            Data_comp++;
        }

        K = t;
    }
    DC = Data_comp;
    DM = Data_move;
  return arr;
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    Random r = new Random();
    int N;
    N = sc.nextInt();
    int a[];
    a = new int[N];
    for (int i = 0; i < N; i++) {
          a[i]=r.nextInt(10000);
    }
    long StartTime,EndTime;
    long Totaltime;
    StartTime = System.currentTimeMillis();
    BBSort(a, N);
    EndTime = System.currentTimeMillis();
    Totaltime = EndTime - StartTime;

    for (int j = 0; j < N; j++) {
        System.out.println(a[j]);
    }
    System.out.println("Time taken for sorting = "+Totaltime);
    System.out.println("Number of data comparisons = "+DC );
    System.out.println("Number of data movement = "+3*DM);


}

}

Upvotes: 0

Views: 930

Answers (2)

UncleBen
UncleBen

Reputation: 82

Your problem is in the way you use the variable t. Just remove it and use K-- at the end of each run and it will solve your issue.

public static int[] BBSort(int arr[],int n) {
    int K,tmp;

    long Data_comp=0,Data_move=0;

    K = n;
    while(K!=0)
    {
        for (int i = 0; i < K-1; i++) {

            if(arr[i]>arr[i+1])
            {
               tmp = arr[i];
               arr[i] = arr[i+1];
               arr[i+1] = tmp;
               Data_move++;
            }
            Data_comp++;
        }

        K--;
    }
    DC = Data_comp;
    DM = Data_move;
  return arr;
}

Upvotes: 1

Josh Heaps
Josh Heaps

Reputation: 345

Okay, I believe I have found your problem.

So, in a bubble sort, the program needs to run through every number, every time. If the program doesn't do this, you create opportunities for numbers to find their way into the wrong spot, and be trapped there.

In your function BBSort Your program is setting the amount of times run the for loop runs to the last index there was a swap. In that situation, you may have two numbers that are in the right order, by themselves, at the end. I.E. Take this list: {1, 2, 9, 5, 6, 10} On this array, the code would recognize wherever the two numbers were properly sorted. This means, when it gets to 6 and 10, it says, "Okay, those two are sorted" and doesn't touch the 6 ever again. Here is some pseudocode for a bubble sort that I've made and works:

for i = 0 ; i < number of items in array; i++{
    for j = 0; j < number of items in array; j++{
        if (list[j] < list[j+1])
            swap list[j] with list[j+1];
    }
}

I hope that you've found this helpful and that everything works out!

Upvotes: 1

Related Questions