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.