Bubble Sorting not working

Question

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);


}

}

Answer 1

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;
}