Should we start with one bubble sort?

Can you explain why

1. the usefulness of the boolean flag "change" ?

2. why the upper limit of the embedded loop ( “ for(j=0;j<i;++j) ” )is i rather than n?

## You may figure out the descending sort and other sorting methods, such as insertion and selection.

```
/* The following program is written to receive a size of an int array that
* assigned by random values varying between 0 to 255 [0-255].
* Then the array will be sorted in ascending order by the bubble method.
*/
import java.lang.*;
public class MainExample1 {
static void bubble_sort(int a[]){
int i,j,t, n=a.length;
boolean change;
for(i=n-1,change=true; i>0 && change ;--i)
{
change=false;
for(j=0;j<i;++j)
if(a[j]<a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
change=true;
}
}
}
public static void main(String args[]){
int n= Integer.parseInt(args[0]);
int d[] = new int[n];
for (int i=0; i<n; i++)
d[i] = (int)(Math.random()*256);
bubble_sort(d);
for (int i=0; i<d.length;i++)
System.out.print(d[i] + " ");
System.out.println();
}
}
```

Dear WargRider, NormR1, and jjhames,

I should thank very much indeed for your comments. I hope the following post, that is the answer to my first post, is helpful for jjhames.

1. How to create an int array with 10 random elements varying between 0 to 255, i.e. [0-255].

We have the static method random() of the class Math in the folder java.lang.

As shown in Java API 1.6

public static double random() which

returns a double value with a positive sign, greater than or equal to 0.0 and less than 1.0. Returned values are chosen pseudorandomly with (approximately) uniform distribution from that range.

Hence, using the following code we may have the above-mensioned int array.

```
int d[] = new int[n];
for (int i=0; i<n; i++)
d[i] = (int)(Math.random()*256);
```

It is pointed out that the compulsive conversion (coercion) into int type will produce 255 at most when the random double value is multiplied by 256. In other word, the highest int value obtained is 255 while the lowest int value 0.

2. How to sort this array in descending order via a primitive “bubble_sort”.

Table 1. The changes in the int array after each run.

The altered array after each run

Randomly created int array 129 198 149 232 94 33 199 137 94 95

The 1st run 198 149 232 129 94 199 137 94 95 **33**

The 2nd run 198 232 149 129 199 137 94 95 **94 33**

The 3rd run 232 198 149 199 137 129 95** 94 94 33**

The 4th run 232 198 199 149 137 129 **95 94 94 33**

The 5th run 232 199 198 149 137 **129 95 94 94 33**

The 6th run 232 199 198 149 **137 129 95 94 94 33**

The 7th run 232 199 198 **149 137 129 95 94 94 33**

The 8th run 232 199 **198 149 137 129 95 94 94 33**

The 9th run 232 **199 198 149 137 129 95 94 94 33**

The method static void bubble_sort(int a[]) produces the output (see table 1), showing how the bubble sort works.

```
static void bubble_sort(int a[]){
int i,j,t, n=a.length;
for(i=n-1; i>0;--i) {
for (j=0; j<n; j++)
System.out.print(a[j] + " ");
System.out.println();
for(j=0;j<n-1;++j)
if(a[j]<a[j+1]){
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
```

How does each run work?

The operation in each run is instructed by the embedded loop:

```
for(j=0;j<n-1;++j)
if(a[j]<a[j+1]){
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
```

As shown by the above code, we start at the left end of the array (a[0] and a[1], when j is 0), to check if the left end element a[0] is less than the second left one a[1]. If so, these two elements swap their values. If not, the two elements remain unchanged. Then we move one step (rightwards) to do the same operation, i.e. to make comparison between a[1] and a[2]. We move rightwards one step by one step until the last operation on a[n-2] and a[n-1], so that the minimum value in this array will be placed at the right end, i.e. at the right most location: a[n-1], as shown as 33 in Table 1.

It is noticed that:

the contribution made by the first run is to place the minimum value at the very right end.

The contribution made by the second run is to place the secondary minimum value at the location of the secondary right end.

……

In this way each run gradually creates a stable region towards the right end, as shown by the bold red numbers (the minums for each run). The fixed stable region has obviously no need to be resorted. In order to save workload, we have changed the upper limit of the embedded loop since the control variable i in the outer loop decreases one by one from n-1 to 1:

```
for(j=0;j<i;++j)
if(a[j]<a[j+1]){
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
```

If an int array has already been sorted, we have no need to redo (re-sort) it. If an array has become sorted on the half way of the sorting procedure, we have no deed to continue such a procedure. The boolean variable “change” plays a monitoring role. If after a given run the "change" is found as still false, it means that the array has become sorted. Hence we should terminate the sorting operation immediately to avoid further unnecessary work.