Кухня(); Второй сезон - 75/79

участников

75. Сортировка вставками. Дана последовательность чисел а1, а2, ..., аn. Требуется переставить числа в порядке возрастания. Делается это следующим образом. Пусть а1, а2, ..., аi – упорядоченная последовательность, т.е. a1 ≤ a2 ≤ ... ≤ аi. Берется следующее число ai+1 и вставляется в последовательность так, чтобы новая последовательность была также возрастающей. Процесс производится до тех пор, пока все элементы от i+1 до n не будут перебраны. Кухня ПРАВИЛА

Комментарии (3)

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

terranum

Уровень 28

29 января 2015, 18:30

Мой вариант без магии binarySearch. Кстати круто, на больших массивах разница ощутима!

public static void insertionSort(@NotNull int[] arr) { int tmp; int j; for (int i = 1; i < arr.length; i++) // бежим пока не нарушится последовательнось if (arr[i - 1] > arr[i]) { j = i - 1; tmp = arr[i]; // запоминаем наш элемент while (j > 0 && arr[j] > arr[i]) // ищем индекс элемета не больше нашего числа j--; System.arraycopy(arr, j, arr, j + 1, i - j); // сдвигаем найденый блок массива вправо на одну ячейку if (arr[j] <= tmp) // вставляем на свое законное место arr[j + 1] = tmp; else // костыль на тот случай когда вставляем в начало массива arr[j] = tmp; } }

iZulrad

Уровень 34

30 января 2015, 18:55

System.arraycopy(arr, j, arr, j + 1, i - j);

Мееееееедленно если элементов мало, проще перекопировать в цикле.
Тут первый вариант много медленнее второго.
Это на случай если у нас есть громадный отсортированный массив и мы хотим вставить туда элемент.
И для этого нам придется перекопировать аж половину массива. Наверянка можно вычислить это магическое число, на котором быстрее искользовать System.arraycopy нежели копирование в цикле. Но для каждой машины оно свое, т.ч. =)

iZulrad

Уровень 34

29 января 2015, 11:06

public static void insertionSort(@NotNull int arr[]) {
        int current, dex, r;
        for (int i = 1; i < arr.length; i++) {
            current = arr[i];
            if ((dex = Arrays.binarySearch(arr, 0, i, current)) < 0) dex = -(dex + 1);

            if (dex != i) {
                if (i - dex > 9_999) {
                    System.arraycopy(arr, dex, arr, dex + 1, i - dex);
                } else {
                    r = i;
                    while (r != dex) arr[r] = arr[--r];
                }
                arr[dex] = current;
            }
        }
    }