/* bubblesort.c: bubblesort program */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 100000

void swap(int a[], int i, int j);
void bubbleSort(int a[]);
void printArray(int a[]);

/* swap: interchange inside array */
void swap(int a[], int i, int j) {
   int t = a[i];
   a[i] = a[j];
   a[j] = t;
}

/* bubbleSort: short code, ineffient */
void bubbleSort(int a[]) {
   int sorted, i;
   for (;;) {
      sorted = 1;
      for (i = 0; i < SIZE -1; i++)
         if (a[i] > a[i+1]) {
            sorted = 0;
            swap(a, i, i + 1);
         }
      if (sorted) break;
   }
}

void printArray(int a[]) {
   int i;
   for (i = 0; i < SIZE; i++) {
      if (i%4 == 0) printf("\n");
         printf("%i\t", a[i]);
   }
   printf("\n");
}

int main() {
   int i;
   int r[SIZE];
   int starttime = time(NULL); /* clock */
   printf("Bubblesort, size = %i\n", SIZE);
   srand((long)starttime);
   for (i = 0; i < SIZE; i++)
      r[i] = (int)((rand() /
         (double)RAND_MAX)*SIZE*10 + 1);
   bubbleSort(r);
   printf("Elapsed time: %ld seconds\n",
      time(NULL) - starttime);
   printArray(r);
}

// BubbleSort.java: simple, inefficient sort
public class BubbleSort {


   
   

   
   

   // swap: interchange inside array
   static void swap(int[] a, int i, int j) {
      int t = a[i];
      a[i] = a[j];
      a[j] = t;
   }

   // bubbleSort: very short code, but ineffient
   static void bubbleSort(int[] a) {

      for (;;) {
         boolean sorted = true;
         for (int i = 0; i < a.length - 1; i++)
            if (a[i] > a[i+1]) {
               sorted = false;
               swap(a, i, i + 1);
            }
         if (sorted) break;
      }
   }

   static void printArray(int[] a) {

      for (int i = 0; i < a.length; i++) {
         if (i%4 == 0) System.out.println();
         System.out.print(a[i] + " \t");
      }
      System.out.println();
   }

   public static void main(String[] args) {
      int size = Integer.parseInt(args[0]);
      int[] r = new int[size];
      long startTime = System.currentTimeMillis();
      System.out.println("Bubblesort size: " + size);
      
      for (int i = 0; i < size; i++)
         r[i] = (int)(Math.random()*size*10.0 + 1.0);

      bubbleSort(r);
      System.out.println("Elapsed time (millis) " +
         (System.currentTimeMillis() - startTime));
      printArray(r);
   }
}

% cc -o bubblesort bubblesort.c
% bubblesort
Bubblesort, size: 10000
Elapsed time: 3 seconds
% bubblesort
Bubblesort, size: 100000
Elapsed time: 463 seconds

% javac BubbleSort.java
% java BubbleSort 60
Bubblesort, size = 60
Elapsed time (millis) 1
% java BubbleSort 100
Bubblesort, size = 100
Elapsed time (millis) 3
% java BubbleSort 1000
Bubblesort, size = 1000
Elapsed time (millis) 394
% java BubbleSort 10000
Bubblesort, size = 10000
Elapsed time (millis) 39518
% java BubbleSort 20000
Bubblesort, size = 20000
Elapsed time (millis) 158317
% java BubbleSort 40000
Bubblesort, size = 40000
Elapsed time (millis) 646717