Алгоритмы сортировки со списками массивов

Question

В настоящее время я работаю над алгоритмами сортировки со списками массивов. Я видел проект на GitHub для перезаписи первого (самого маленького) элемента в маленьком массиве новым (большим) элементом из большего массива, а затем для сортировки маленького массива.

Это решение, предоставленное:

public int findLarger() throws IndexingError {
    int[] array = getArray();
    int k = getIndex();
    if (k <= 0 || k > array.length) {
        throw new IndexingError();
    }
    int[] smallArray = new int[k];
    for (int index = k; index < array.length; index++){
         if (array[index] > smallArray[0]){
             smallArray[0] = array[index];
             Arrays.sort(smallArray);
         }
    }
    return smallArray[0];
}

Но я изо всех сил пытаюсь понять, является ли этот метод, который я создал, более «эффективным», используя другую переменную вместо другого массива?

public int findLarger() throws IndexingError {
    int[] array = getArray();
    int max = array[0];
    for (int i = 0; i < k; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    } 
    return max;
}


public abstract class Search {
private int[] array; 
private int k; 

Search(int[] array, int k) {
    this.array = array;
    this.k = k;
}

public int[] getArray() {
    return array;
}
int getIndex() { return k; }

abstract public int findElement() throws IndexingError;
}

редактировать:

if (array.length == 0 )
            throw new RuntimeException("Array can't be empty");

        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        } // end of obvious solution method
        return max;
    }

Answer 1

Первая реализация действительно плохая, почему одна сортировка (O n log n) даже наихудшая несколько array.length-k раз, чтобы найти минимум (O (n)) набора, просто ужасна.

Так что да, верный путь - версия с одной переменной, хранящая текущий минимум. (Просто позаботьтесь о том, чтобы инициализация вашего максимума с array[0] не была устойчивой к пустым входам)

С другой стороны, как уже отмечали другие, оба алгоритма не используют одни и те же ячейки и, следовательно, в настоящее время несопоставимы,Если в вашей второй реализации вы итерируете от k до array.length, как и в первой, вы делаете получаете намного лучшую реализацию, чем первая.

Answer 2

На этот вопрос сложно ответить по двум причинам:

• Во-первых, метод № 1 и метод № 2 не делают одно и то же, поэтому сравнение их эффективности на самом деле не имеет смысла.
• Во-вторых, метод # 1 на самом деле немного сложно точно определить, и не ясно, что он делает так же, как и должен. То есть метод # 1 - это не просто решение другой проблемы;Я подозреваю, что это неверное решение другой проблемы .

Позвольте мне объяснить. Метод № 2 довольно прост: он находит максимальный элемент из подмассива array[0..k]. Метод № 1 явно не делает этого: он только читает данные из подмассива array[k..n].

Он также явно не находит максимум из этого массива, потому что он помещает данные в smallArray, сортирует ихи возвращает значение из индекса 0;максимум будет по индексу k - 1. Но значение в индексе 0 также не является минимальным, поскольку данные помещаются в smallArray, только если они на больше , чем то, что уже есть.

Фактическое поведение метода # 1 может бытьисследовано на примерах. Для удобства я изменил сигнатуру на значения array и k в качестве параметров:

• findLarger(new int[] { 1, 2, 3, 4, 5, 6, 7 }, 3) равно 5: третий по величине из 4, 5, 6,7.

• findLarger(new int[] { 1, 2, 3, 7, 6, 5, 4 }, 3) также 5: третий по величине из 7, 6, 5, 4.

• findLarger(new int[] { 7, 6, 5, 4, 3, 2, 1 }, 3) -2: третий по величине из 4, 3, 2, 1.

• findLarger(new int[] { 1, 2, 3, 7, 6, 5, 4 }, 1) равен 7: первый по величине из 2, 3, 7, 6, 5, 4.

Для этих примеров последовательно возвращается k-й по величине элемент в подмассиве array[k..n]. Однако в других случаях это не так:

• findLarger(new int[] { -1, -2, -3, -4, -5, -6 }, 2) равно 0, а не -3, -4, -5, -6.
• findLarger(new int[] { 1, 2, 3, 4, 5, 6, 7 }, 5)равно 0, а не одному из 6, 7.

Таким образом, полное утверждение метода # 1: возвращает k -й по величине положительный элемент из подмассива array[k..n]или 0, если этот подмассив содержит меньше k положительных чисел . Особый случай возврата 0 и использование k для двух не связанных целей предполагает, что этот метод предполагался для решения более простой задачи возврата k -го наибольшего элемента, но что онбыл написан неправильно.

Еще одно доказательство этого состоит в том, что очень простое изменение в алгоритме заставляет его безоговорочно возвращать k-й по величине элемент: вместо инициализации smallArray нулями, скопируйте первый kэлементы из array и сортируйте их.

    // changed: copy first k elements from array, and sort
    int[] smallArray = Arrays.copyOfRange(array, 0, k);
    Arrays.sort(smallArray);

    for (int index = k; index < array.length; index++){
         if (array[index] > smallArray[0]){
             smallArray[0] = array[index];
             Arrays.sort(smallArray);
         }
    }
    return smallArray[0];

Еще одним доказательством является сходство с кодом в этом другом вопросе переполнения стека , который предназначен для поиска k thсамый большой элемент, и который делает copyOfRange и sort вместо просто new int[k].

---

Так что теперь мы можем говорить об эффективности альтернатив версии fixed метода № 1.

• Временная сложность метода № 1 равна O ( nk log k ).

• Метод № 1 может бытьулучшено до O ( nk ) путем изменения Arrays.sort во внутреннем цикле, чтобы сдвинуть первый элемент в правильное положение за время O ( k );это работает, потому что только первый элемент будет не в порядке, поэтому полная сортировка не нужна.

• Очевидный способ найти k -й по величине элемент - это отсортировать массив ивернуть значение по индексу n - k. Это занимает O ( n log n ) время;метод № 1 лучше только тогда, когда k log k n , т.е. когда k мало по сравнению с n .

• Вы можете сделать лучше - алгоритм quickselect в среднем занимает всего O ( n ), что явно оптимально дляЭта проблема. Тем не менее, он имеет редкую сложность O в худшем случае ( n ²).