Политика конфиденциальностиКонтактыО сайтеОтзывыGitHubDonate
© EVILEG 2015-2018
Рекомендует хостинг
TIMEWEB

Алгоритм сортировки слиянием

алгоритм, сортировка слиянием, Merge Sort Algorithm, сортировка

Сортировка слиянием - это своего рода алгоритм «разделяй и властвуй» в компьютерном программировании. Это один из самых популярных алгоритмов сортировки и отличный способ развить уверенность в построении рекурсивных алгоритмов.

Стратегия "Разделяй и влавствуй"

Используя технику «Разделяй и властвуй», мы делим проблему на подзадачи. Когда решение для каждой подзадачи готово, мы «объединяем» результаты из подзадач, чтобы решить основную проблему.

Предположим, нам нужно было отсортировать массив A. Подзадача состояла бы в том, чтобы отсортировать подраздел этого массива, начиная с индекса p и заканчивая индексом r, обозначенным как A [p..r].

Разделяй

Если q является промежуточной точкой между p и r, то мы можем разбить подмассив A [p..r] на два массива A [p..q] и A [q + 1, r].

Влавствуй

На этапе завоевания мы пытаемся отсортировать оба подмассива A [p..q] и A [q + 1, r]. Если мы еще не достигли базового варианта, мы снова разделяем оба этих подмассива и пытаемся отсортировать их.

Комбинируем

Когда шаг завоевателя достигает базового шага, и мы получаем два отсортированных подмассива A [p..q] и A [q + 1, r] для массива A [p..r], мы объединяем результаты, создавая отсортированный массив A [p..r] из двух отсортированных подмассивов A [p..q] и A [q + 1, r]

Алгоритм сортировки слиянием

Функция MergeSort многократно делит массив на две половины, пока мы не достигнем стадии, когда мы пытаемся выполнить MergeSort для подмассива размером 1, т.е. p == r. После этого в игру вступает функция слияния, которая объединяет отсортированные массивы в большие массивы, пока весь массив не будет объединен.

MergeSort(A, p, r)
    If p > r 
        return;
    q = (p+r)/2;
    mergeSort(A, p, q)
    mergeSort(A, q+1, r)
    merge(A, p, q, r)

Чтобы отсортировать весь массив, нам нужно вызвать MergeSort (A, 0, length (A) -1). Как показано на рисунке ниже, алгоритм сортировки слиянием рекурсивно делит массив на две половины, пока мы не достигнем базового случая массива с 1 элементом. После этого функция слияния выбирает отсортированные подмассивы и объединяет их для постепенной сортировки всего массива.

Шаг слияния сортировки слиянием

Каждый рекурсивный алгоритм зависит от базового случая и способности комбинировать результаты из базовых случаев. не является исключением и сортировка слиянием. Самая важная часть алгоритма - шаг «слияния».

Шаг объединения - это решение простой проблемы объединения двух отсортированных списков (массивов) для создания одного большого отсортированного списка (массива).

Алгоритм поддерживает три указателя, по одному для каждого из двух массивов и один для поддержания текущего индекса окончательного отсортированного массива.

Достигли ли мы конца какого-либо из массивов?
    Нет:
        Сравните текущие элементы обоих массивов
        Скопируйте меньший элемент в отсортированный массив
        Переместить указатель на элемент, содержащий меньший элемент
    Да:
        Скопировать все оставшиеся элементы непустого массива

Поскольку во втором массиве больше не осталось элементов, и мы знаем, что оба массива были отсортированы при запуске, мы можем скопировать оставшиеся элементы из первого массива напрямую

Написание кода для алгоритма слияния

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

Вот почему нам нужны только массив, первая позиция, последний индекс первого подмассива (мы можем вычислить первый индекс второго подмассива) и последний индекс второго подмассива.

Наша задача - объединить два подмассива A [p..q] и A [q + 1..r], чтобы создать отсортированный массив A [p..r]. Таким образом, входные данные для функции A, p, q и r

Функция слияния работает следующим образом:

  1. Создайте копии подмассивов L ← A [p..q] и M ← A [q + 1..r].
  2. Создайте три указателя i, j и k
    1. i поддерживает текущий индекс L, начиная с 1
    2. j поддерживает текущий индекс М, начиная с 1
    3. k поддерживает текущий индекс A [p..q], начиная с p
  3. Пока мы не достигнем конца L или M, выберите больший из элементов из L и M и поместите их в правильное положение в A [p..q]
  4. Когда у нас кончаются элементы в L или M, возьмите оставшиеся элементы и поместите в A [p..q]

В коде это будет выглядеть так:

void merge(int A[], int p, int q, int r)
{
    /* Создание L ← A[p..q] и M ← A[q+1..r] */
    int n1 = q - p + 1;
    int n2 =  r - q;

    int L[n1], M[n2];

    for (i = 0; i < n1; i++)
        L[i] = A[p + i];
    for (j = 0; j < n2; j++)
        M[j] = A[q + 1 + j];

    /* Поддержание текущего индекса вложенных массивов и основного массива */
    int i, j, k;
    i = 0; 
    j = 0; 
    k = p; 


    /* Пока мы не достигнем конца L или M, выбираем большее из элементов L и M и помещаем их в правильное положение в точке A [p..r]*/
    while (i < n1 && j < n2)
    {
        if (L[i] <= M[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = M[j];
            j++;
        }
        k++;
    }

    /* Когда у нас кончаются элементы в L или M, возьмите оставшиеся элементы и поместите в A [p..r]*/
    while (i < n1)
    {
        A[k] = L[i];
        i++;
        k++;
    }

    while (j < n2)
    {
        A[k] = M[j];
        j++;
        k++;
    }
}
Функция слияния пошагово

В этой функции много действий, поэтому давайте рассмотрим пример, чтобы увидеть, как это будет работать.

Массив A [0..8] содержит два отсортированных подмассива A [1..5] и A [6..7]. Давайте посмотрим, как функция слияния объединит два массива.

void merge(int A[], int p = 1, int q = 4, int 6)
{
Шаг 1. Создайте дубликаты копий подмассивов для сортировки
 /* Создание L ← A[p..q] и M ← A[q+1..r] */
    n1 = 4 - 1 + 1 = 4;
    n2 =  6 - 4 = 2;

    int L[4], M[2];

    for (i = 0; i < 4; i++)
        L[i] = A[p + i];
    /* L[0,1,2,3] = A[1,2,3,4] = [1,5,10,12] */

    for (j = 0; j < 2; j++)
        M[j] = A[q + 1 + j];
    /* M[0,1,2,3] = A[5,6] = [6,9]

Шаг 2: Поддержание текущего индекса подмассивов и основного массива
 int i, j, k;
    i = 0; 
    j = 0; 
    k = p; 

Шаг 3: Пока мы не достигут конец L или M, выбирается большее среди элементов L и M и помещается в правильное положение в точке A [p..r]
 while (i < n1 && j < n2) { 
        if (L[i] <= M[j]) { 
            A[k] = L[i]; i++; 
        } 
        else { 
            A[k] = M[j]; 
            j++; 
        } 
        k++; 
    }

Шаг 4: Когда заканчиваются элементы в L или M, оставшиеся элементы необходимо поместить в A [p..r]
/* Мы вышли из предыдущего цикла, потому что j <n2 не выполняется */  
    while (i < n1)
    {
        A[k] = L[i];
        i++;
        k++;
    }

/* Мы вышли из предыдущего цикла, потому что i <n1 не выполняется */  

    while (j < n2)
    {
        A[k] = M[j];
        j++;
        k++;
    }
}

Этот шаг был бы необходим, если бы размер М был больше, чем L. В конце функции слияния подмассив A [p..r] сортируется.

Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
IT
25 марта 2019 г. 17:32
Ilya The Engineer

Qt - Тест 001. Сигналы и слоты

  • Результат:5баллов,
  • Очки рейтинга-10
G
25 марта 2019 г. 8:34
GAG

C++ - Тест 002. Константы

  • Результат:41баллов,
  • Очки рейтинга-8
G
25 марта 2019 г. 8:25
GAG

C++ - Тест 001. Первая программа и типы данных

  • Результат:66баллов,
  • Очки рейтинга-1
Последние комментарии
26 марта 2019 г. 8:49
Евгений Легоцкой

Да Да Да. Я тоже сейчас вспомнил, что проблема -R в том, что права и для файлов и для каталогов устанавливаются. А для веб-серверов нужно, чтобы права на каталоги были 755, а на файлы 64...
26 марта 2019 г. 8:47
Ruslan Polupan

Был не прав....Почитал маны, флаг «выполнения» по-разному действует на файлы и каталоги.Правильно так chmod -R go=rX,u=rwX /path/to/target/dir
26 марта 2019 г. 8:35
Евгений Легоцкой

По моему, только эта директория /path/to/target/dir и получит эти права, а все остальные вложенные остануться с тем, с чем были. UPD: Или я что-то жёстко путаю? ))) Надо переп...
22 марта 2019 г. 12:32
Евгений Легоцкой

Ну может бибилотеки не те положили? У вас сборка для MinGW, а либы для MSVC.
Сейчас обсуждают на форуме
26 марта 2019 г. 12:07
Евгений Легоцкой

Пожалуйста, не загружайте сейчас никакие изображения, это сейчас не работает. Вечером исправлю, остались ошибки на сервере после его переезда.
U
25 марта 2019 г. 12:43
Unreal_man

Как сделать чтоб при клике на ячейку(ос андроид) ее сразу можно было редактировать?QGuiApplication::inputMethod()->show(); показывает клавиатуру, а вот что до этого прописать чтоб текст в ...
m
24 марта 2019 г. 10:36
monevich

Отвечу на свой же вопрос, может кому то это пригодится. Да, можно в функции main использовать такую конструкцию. При запуске программы из Qt передаю свой аргумент в параметрах командной строк...
22 марта 2019 г. 12:29
Дмитрий

Да, мьютекс добавил, но в том потоке, где сигнал вызывается.
Присоединяйтесь к нам в социальных сетях

Для зарегистрированных пользователей на сайте присутствует минимальное количество рекламы