/* 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("
"); printf("%i ", a[i]); } printf("
"); }
int main() { int i; int r[SIZE];
int starttime = time(NULL); /* clock */
printf("Bubblesort, size = %i
", 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
",
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] + " "); } 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
|