Privacy policyContactsAbout siteOpinionsGitHubDonate
© EVILEG 2015-2018
Recommend hosting
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] сортируется.

Virtual hosting with 10 percent discount
Virtual hosting with 10 percent discount
EVILEG offers reliable hosting with a 10% discount for virtual hosting and 5% for VPS

Comments

Only authorized users can post comments.
Please, Log in or Sign up
IT
March 25, 2019, 5:32 p.m.
Ilya The Engineer

Qt - Test 001. Signals and slots

  • Result:5points,
  • Rating points-10
G
March 25, 2019, 8:34 a.m.
GAG

C++ - Test 002. Constants

  • Result:41points,
  • Rating points-8
G
March 25, 2019, 8:25 a.m.
GAG

C++ - Test 001. The first program and data types

  • Result:66points,
  • Rating points-1
Last comments
March 26, 2019, 8:49 a.m.
Евгений Легоцкой

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

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

По моему, только эта директория /path/to/target/dir и получит эти права, а все остальные вложенные остануться с тем, с чем были. UPD: Или я что-то жёстко путаю? ))) Надо переп...
March 26, 2019, 8:18 a.m.
Ruslan Polupan

А если так chmod -R 755 /path/to/target/dir
March 22, 2019, 12:32 p.m.
Евгений Легоцкой

Ну может бибилотеки не те положили? У вас сборка для MinGW, а либы для MSVC.
Now discuss on the forum
March 26, 2019, 12:07 p.m.
Евгений Легоцкой

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

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

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

Да, мьютекс добавил, но в том потоке, где сигнал вызывается.
Join us in social networks

For registered users on the site there is a minimum amount of advertising