среда, 1 августа 2012 г.

algorithm: bubble-sort

ИДИОМА: обмен значениями с использованием временной переменной
                int tmp = a;
                a = b;
                b = tmp;
ИДИОМА: обмен значениями без использования временной переменной
                a = a + b;
                b = a - b;
                a = a - b;

    Безусловное "всплытие" элемента. "Всплывает" один и тот же элемент. 
import java.util.Arrays;
class X {
    public static void main(String[] args) {
        int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        System.out.print(Arrays.toString(arr) + " -> ");
        for (int k = 0; k < arr.length - 1; k++) {
            int tmp = arr[k];
            arr[k] = arr[k + 1];
            arr[k + 1] = tmp;
        }
        System.out.println(Arrays.toString(arr));
    }
}
>> [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]

    "Всплытие" элемента с условием. "Всплывающий" элемент может меняться.
import java.util.Arrays;

class Y {
    public static void main(String[] args) {
        int[] arr = {0, 10, 20, 3, 4, 5, 600, 700, 8, 9};
        System.out.print(Arrays.toString(arr) + " -> ");
        for (int k = 0; k < arr.length - 1; k++) {
            if (arr[k] > arr[k + 1]) {
                int tmp = arr[k];
                arr[k] = arr[k + 1];
                arr[k + 1] = tmp;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
>> [0, 10, 3, 4, 5, 20, 600, 8, 9, 700]



АЛГОРИТМ: сортировка "пузырьком" (Bubble Sort)
    Объединяя "пирамидальный for" и условное всплытие элемента, получаем готовый алгоритм
import java.util.Arrays;
public class BubbleSort {
    public static void sort(int[] arr) {
        for (int barrier = arr.length - 1; barrier >= 0; barrier--) {
            for (int index = 0; index < barrier; index++) {
                if (arr[index] > arr[index + 1]) {
                    int tmp = arr[index];
                    arr[index] = arr[index + 1];
                    arr[index + 1] = tmp;
                }
            }
        }
    }
}


Тестирующий класс

class TestBubbleSort {
    public static void main(String[] args) {
        int[][] data = {
                {},
                {1},
                {0, 3, 2, 1},
                {6, 8, 3, 5, 4, 1, 2, 0, 9, 7},
        };
        for (int[] arr : data) {
            System.out.print(Arrays.toString(arr) + " -> ");
            BubbleSort.sort(arr);
            System.out.println(Arrays.toString(arr));
        }
    }
}


>> [] -> []
>> [1] -> [1]>> [0, 3, 2, 1] -> [0, 1, 2, 3]>> [6, 8, 3, 123, 5, 4, 1, 2, 0, 9, 7] -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 123]


    Лабораторные
    Задания лабораторных можно прочитать на этой странице.
    К этой странице относится лабораторная proc.loop.bubble_sort_inverted.