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

algorithm: insertion-sort

АЛГОРИТМ: сортировка вставками (Insertion Sort)
import java.util.Arrays;
public class InsertionSort {
    public static void sort(int[] arr) {
        for (int k = 1; k < arr.length; k++) {
            int newElement = arr[k];
            int location = k - 1;
            while (location >= 0 && arr[location] > newElement) {
                arr[location + 1] = arr[location];
                location--;
            }
            arr[location + 1] = newElement;
        }
    }
}
Тестирующий класс 
class TestInsertionSort {
    public static void main(String[] args) {
        int[][] data = {
                {},
                {1},
                {0, 3, 2, 1},
                {6, 8, 3, 123, 5, 4, 1, 2, 0, 9, 7},
        };
        for (int[] arr : data) {
            System.out.print(Arrays.toString(arr) + " -> ");
            InsertionSort.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]



АЛГОРИТМ: бинарный поиск, поиск делением пополам (Binary Search)
import java.util.Arrays;

public class BinarySearchTest {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        System.out.println(Arrays.binarySearch(arr, 5));
        System.out.println(Arrays.binarySearch(arr, 10));
        System.out.println(Arrays.binarySearch(arr, 15));
        System.out.println(Arrays.binarySearch(arr, 20));

        System.out.println(Arrays.binarySearch(arr, 50));
        System.out.println(Arrays.binarySearch(arr, 55));
    }
}
>> -1
>> 0
>> -2
>> 1
>> 4
>> -6
ИДИОМА: копирование массива
import java.util.Arrays;

public class SystemArrayCopyTest {
    public static void main(String[] args) {
        int[] arr0 = {1, 2, 3, 4, 5, 6};
        int[] arr1 = {0, 0, 0, 0, 0, 0, 0, 0};

        System.out.println(Arrays.toString(arr0));
        System.out.println(Arrays.toString(arr1));

        System.arraycopy(arr0, 1, arr1, 2, 3);
        System.out.println(Arrays.toString(arr1));

        System.arraycopy(arr0, 1, arr0, 2, 3);
        System.out.println(Arrays.toString(arr0));
    }
}
>> [1, 2, 3, 4, 5, 6]
>> [0, 0, 0, 0, 0, 0, 0, 0]
>> [0, 0, 2, 3, 4, 0, 0, 0]
>> [1, 2, 2, 3, 4, 6]


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