Краткое изложение информатики: Алгоритмы, теория и машины Лекция 11-1 (Сортировка и поиск)

Черный список - это список прав доступа, которые должны быть отклонены для обслуживания.
Белый список - это список прав, которые должны быть приняты на обслуживание.
Итак, что мы хотим сделать, это составить белый список более эффективно!

Чтобы найти принятого человека в списке, существует множество способов поиска по списку

1. Мы можем использовать последовательный поиск с помощью цикла for

//'key' will be the accepted account
public static int search(String key, String[] a)
{
  for(int i = 0; i < a.length; i++)
    // if you write like that below line, you will compare the 'references'
    // not the value of strings!
    //if (a[i]==key) return i;
    
    //if the 'value' of a[i] is equal to key, it returns 0
    if (a[i].compareTo(key) == 0) return i;
  return -1;
}

Представим, что если строковый массив 'a' состоит из {"alice", "bob", "carlos", "carol", "craig",} и ключом является "craig", то нужно выполнить цикл 5 раз. но если существует 10 миллионов человек и человек, которого мы ищем, находится на 10,000,000-ом индексе, то нужно выполнить цикл 10 миллионов раз, и это займет много времени! поэтому мы должны найти более эффективный способ найти ключ.

2. Бинарный поиск

Чтобы использовать бинарный поиск, необходимо хранить массив в отсортированном порядке

public class Binary_Search {
    public static int search(String key, String[] a) {
        return search(key, a, 0, a.length);
    }

    public static int search(String key, String[] a, int lo, int hi) {
        if (hi <= lo) return -1;
        int mid = lo + (hi - lo) / 2;
        int cmp = a[mid].compareTo(key);
        //compareTo : 1 means :
        // a[mid] is greater than key,search the half with upper indices
        if (cmp > 0) return search(key, a, lo, mid);
            //compareTo : -1 means :
            // a[mid] is smaller than key,search the half with lower indices
            // mid + 1 means that you will also remove the 'mid' and search
            // the mid+1 with lower indicies.
        else if (cmp < 0) return search(key, a, mid+1, hi);
        //if cmp == 0,return mid
        else return mid;
    }

    public static void main(String[] args) {
        String key = "dave";
        String[] a = new String[]{"alice","bob","carlos","carol","craig","dave"};
        //not 0 like the first index of an array, we have to add 1.
        int lo = 1;
        int hi = 6;
        //find the array where "dave" is in
        System.out.println(search(key,a,lo,hi));
    }
}

(* я написал cmp == 0 return mid и a[mid] == key, а не cmp = 0 return mid и a[mid = key])

Таким образом, если мы используем бинарный поиск, мы можем выполнить цикл только 2 раза, в отличие от последовательного поиска, при котором мы должны выполнить цикл 6 раз, чтобы найти Дэйва. Таким образом, мы можем также обнаружить, что временная сложность бинарного поиска будет O(log N).

Но, как я уже говорил, чтобы использовать двоичный поиск, мы должны отсортировать массив до этого. тогда как мы можем отсортировать массив? один из ответов - "сортировка вставкой".

3. Сортировка вставкой

Допустим, если изменить порядок массива, то он будет выглядеть следующим образом

{"craig", "dave", "alice", "bob", "carol", "carlos"}

Но если мы используем сортировку вставкой, мы можем отсортировать массив, чтобы иметь возможность использовать бинарный поиск!

public class Insertion_Sort {
    public static void sort(String[] a) {
        int N = a.length;
    //sort process
        for(int i = 1; i < N; i++)
            for(int j = i; j > 0; j--)
                if (a[j-1].compareTo(a[j])>0)
                    exch(a, j-1, j);
                else break;
    }
    // exchange a[i] and a[j]
    private static void exch(String[] a, int i, int j) {
        String t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void main(String[] args) {
        String[] a = new String[]{"craig","dave","alice","bob","carol","carlos"};
        sort(a);
        // print the elements
        for (int i = 0; i < a.length; i++)
            StdOut.println(a[i]);
    }
}

Я описываю ход сортировки вставкой, остальные циклы вы можете попробовать сами :)

Но временная сложность сортировки вставками составляет O(N) для лучшего, и O(N²) для среднего и худшего, так что если вы попробуете это, вы можете обнаружить, что это должно зацикливаться много раз.

Существует закон Мура, который означает, что "количество транзисторов в интегральной схеме удваивается примерно каждые 2 года". Но если мы используем квадратичный алгоритм, это "удвоение" не означает, что компьютер работает в два раза быстрее.

4. Сортировка слиянием

Джон фон Нейман нашел более эффективный алгоритм сортировки под названием "Merge Sort".

Сортировка слиянием является рекурсивной процедурой, а также процедурой "разделяй и властвуй". это означает, что если проблема большая, то нужно разбить проблему на подпроблемы, а если проблема становится меньше, то решить ее. и объединить решения маленьких проблем, чтобы получить решение основной проблемы.

Если мы видим вышеприведенные строки, то, наверное, трудно понять, давайте приведем пример ниже.

Поэтому мы можем применить сортировку слиянием к {"craig", "dave", "alice", "bob", "carol", "carlos"}, что мы ищем.

public class Merge_Sort {
    public static void main(String[] args) {

        //alice : 1, bob = 2, carlos = 3, carol = 4, craig = 5, dave = 6
        int numbers[] = { 5, 6, 1, 2, 4, 3};

        System.out.println("Before:");
        printArray(numbers);

        mergeSort(numbers);

        System.out.println("\nAfter:");
        printArray(numbers);
    }


    private static void mergeSort(int[] inputArray) {
        int inputLength = inputArray.length;

        //if there is only one element in divided array, then return.
        if (inputLength < 2) {
            return;
        }

        //we will 'divide' the inputLength
        int midIndex = inputLength / 2;
        int[] leftHalf = new int[midIndex];
        int[] rightHalf = new int[inputLength - midIndex];

        //copy the elements from our original input array into leftHalf array
        for(int i = 0; i < midIndex; i++) {
            leftHalf[i] = inputArray[i];
        }

        //copy the elements from our original input array into rightHalf array
        for(int i = midIndex; i < inputLength; i++) {
            //we should fill the rightHalf from the 0th index!
            rightHalf[i - midIndex] = inputArray[i];
        }

        //recursively divide till return!
        mergeSort(leftHalf);
        mergeSort(rightHalf);

        merge(inputArray, leftHalf, rightHalf);
    }

    //int[] inputArray : later we can merge it sorted with leftHalf and rightHalf
    //
    private static void merge(int[] inputArray, int[] leftHalf, int[] rightHalf){
        int leftSize = leftHalf.length;
        int rightSize = rightHalf.length;

        //keep comparing the lowest element of each array
        //i will be the iterator for the leftHalf
        //j will be the iterator for the rightHalf
        //k will be the iterator for the inputArray
        int i = 0, j = 0 ,k = 0;

        //looping until we run out of elements in the left array or we run out of elements on the right array
        while(i < leftSize && j < rightSize) {
            //compare the ith element of the leftHalf and the jth element of the rightHalf
            if (leftHalf[i] <= rightHalf[j]) {
                //if leftHalf[i] is equal or smaller than rightHalf[j], put leftHalf[i] element into inputArray[k] index
                inputArray[k] = leftHalf[i];
                //move the leftHalf array's pointer and then compare incremented leftHalf[i] to rightHalf[j]
                i++;
            }
            else {
                inputArray[k] = rightHalf[j];
                j++;
            }
            // move the inputArray's pointer not to duplicate.
            k++;
        }

        // put the elements that remain of the array to the inputArray[k]
        //if the array is leftHalf
        while(i < leftSize) {
            inputArray[k] = leftHalf[i];
            i++;
            k++;
        }
        //if the array is rightHalf
        while(j < rightSize) {
            inputArray[k] = rightHalf[j];
            j++;
            k++;
        }
    }
    private static void printArray(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            System.out.println(numbers[i]);
        }
    }
}

Временная сложность сортировки слиянием составляет O(n log n), что более эффективно, чем сортировка вставкой, временная сложность которой составляет O(n) для лучшего случая и O(n²) для среднего и худшего.

Я очень хотел написать о LCP(Longest common prefix) и LRS(Longest repeated substring), но думаю, что мне нужно больше практиковаться, потому что я не могу понять это четко из-за недостатка знаний. но я надеюсь, что этот конспект поможет вам!

Ссылки:

Открыть Github Gist

Computer Science: Алгоритмы, теория и машины