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



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

Кухня ПРАВИЛА

3 комментария

iZulrad
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;
            }
        }
    }
terranum
Мой вариант без магии 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
System.arraycopy(arr, j, arr, j + 1, i - j);

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