I need to implement the bidirectional bubble sort in my code.
In other words in
will go from left to right first carrying the largest value.
But when it reaches out
, it should reverse and go from right to left carrying the smallest value.
I am advised to to implement another out
index in addition the current one.
This is what I have so far - just 2 loops. I am guessing I have to combine them somehow?
public void bubbleSort() {
int out, in; // nElems in my case is 4, because I have 4 elements in my array
for(out=nElems-1; out>1; out--) // outer loop backward
for(in=out; in>1; in--) // inner loop backward
if(a[in] < a[in-1])
swap(in, in-1);
for(out=0; o开发者_JS百科ut<nElems; out++) // outer loop forward
for(in=0; in<out; in++) // inner loop forward
if(a[in] > a[in+1])
swap(in, in+1);
public void bidirectionalBubbleSort()
{
int left = 0, right = a.length-1;
while (left < right)
{
for (int pos = left; pos < right; pos++)
{
if (a[pos] > a[pos+1])
swap(pos, pos+1);
}
right--;
for (int pos = right; pos > left; pos--)
{
if (a[pos] < a[pos-1])
swap(pos, pos-1);
}
left++;
}
}
I recommend you split the method up for chunks that you can comprehend, like:
public static boolean swap(int[] numbers, int i, int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
return true;
}
static boolean leftSide(int[] numbers, int i, int j) {
boolean swapped = false;
for (int k = i; k < j; k++)
if (numbers[k] > numbers[k + 1])
swapped = swap(numbers, k, k + 1);
return swapped;
}
static boolean rightSide(int[] numbers, int i, int j) {
boolean swapped = false;
for (int k = j; k > i; k--)
if (numbers[k] < numbers[k - 1])
swapped = swap(numbers, k, k - 1);
return swapped;
}
public static void cocktailSort(int[] numbers) {
boolean swapped = true;
int i = -1;
int j = numbers.length - 1;
while (i++ < j && swapped)
if (swapped = leftSide(numbers, i, j))
swapped = rightSide(numbers, i, j--);
}
And to test it:
public static void main(String[] args) {
int x[] = new int[] { 2, 6, 3, 7, 8, 3, 7, 5, 4 };
cocktailSort(x);
System.out.println(java.util.Arrays.toString(x));
}
Output:
[2, 3, 3, 4, 5, 6, 7, 7, 8]
boolean f1 = false, f2 = false;
outer:
for (int i=0; i < arr.length-1; i++)
for (int j=i; j< arr.length - i -1; j++) {
if(arr[j] >= arr[j+1]){
f1 = true;
int t = arr[j];
arr[j] = arr[j+1];
arr[j+1] = t;
}
if(arr[arr.length - j -1] <= arr[arr.length - j - 2]){
f2 = true;
int t = arr[arr.length - j -2];
arr[arr.length - j -2] = arr[arr.length - j -1];
arr[arr.length -j -1] = t;
}
/**
* @param k: iterator variable thats prints each pass..(optional)
*/
for (int k:arr)
System.out.print(" "+k);
System.out.println(" "+i);
//Ultimate break condition
if(j == arr.length - j -2 && (!f1 && !f2))
break outer;
}
Bidirectional Bubble Sort using only 2 loops & 2 index variables.
public void bubbleSort(){
for(int out=0;out<nElems/2;out++){
boolean forward = true;
for (int in = out;in !=(forward ? out-1 : out)
;in = forward ? in + 1 : in - 1)
{
if (in == nElems - (out + 1))
forward = false;
if (a[forward ? in + 1 : in] < a[forward?in:in-1])
swap(forward ? in + 1 : in - 1, in);
}
}
}
Bidirectional bubble sort, sorting variable: array[]
//-------------------------------------------//
//biderctioanal bubble sort - coctail sort
public void bidirBubbleSort(){
for(int i=1; i<length/2; i++){
for(int j=0; j<length-i; j++)
if(array[j]>array[j+1])
swap(j, j+1);
for(int j=length-i; j>=i; j--)
if(array[j]<array[j-1])
swap(j, j-1);
}
}
//-------------------------------------------//
//swap 2 elements
public void swap(int index1, int index2){
int temp=array[index1];
array[index1]=array[index2];
array[index2]=temp;
}
//-------------------------------------------//
On 10_000 randomly selected elements, standard bubble sorts completes in 410ms and bidirectional bubble sort in 319ms
精彩评论