Лекции
Начать
Начать обучение
JavaRush /Курсы /Harvard CS50 /Алгоритмы сортировки. Сортировка слиянием

Алгоритмы сортировки. Сортировка слиянием

Harvard CS50
3 уровень , 11 лекция
Открыта

Внимание! Практически весь материал этой лекции был в видеолекции. Если вы всё хорошо усвоили, просто пробегитесь глазами и переходите дальше.



Этот алгоритм — рекурсивный, он разбивает одну большую задачу сортировки на подзадачи, выполнение которых делают его ближе к решению изначальной большой задачи. 

Frontend-университет

Основная идея — разделение неотсортированного массива на две части и сортировка отдельных половинок по рекурсивному принципу. 

Алгоритмы сортировки. Сортировка слиянием - 1

Допустим, у нас есть n элементов для сортировки. Если n < 2, заканчиваем сортировку, иначе — сортируем отдельно левую и правую части массива, и потом их объединяем. 

Давайте отсортируем массив 

Алгоритмы сортировки. Сортировка слиянием - 2

Делим его на две части, и продолжаем делить, пока не получим подмассивы величиной 1, которые заведомо отсортированы.

Алгоритмы сортировки. Сортировка слиянием - 3

Два отсортированных подмассива можно объединить за время O(n) с помощью простого алгоритма: удаляем меньшее из чисел в начале каждого подмассива и вставляем его в объединенный массив. Повторяем, пока не закончатся все элементы. 

Алгоритмы сортировки. Сортировка слиянием - 4
Алгоритмы сортировки. Сортировка слиянием - 5

Сортировка слиянием требует времени O(nlog n) для всех случаев. Пока мы делим массивы на половины, на каждом уровне рекурсии получаем log n. Затем, для слияния подмассивов нужно всего n сравнений. Следовательно, O(nlog n). Лучший и худший варианты для сортировки слиянием — одинаковы, ожидаемое время работы алгоритма = Θ(nlog n).

Этот алгоритм — самый эффективный среди рассмотренных.

Алгоритмы сортировки. Сортировка слиянием - 6

 

Алгоритмы сортировки. Сортировка слиянием - 7
Комментарии (27)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
Артем Уровень 15
22 декабря 2021
В видео не рассказан принцип слияния половинок. Например начиная с 9:54. Имеем 2 половинки: "2468" и "1357". Как он далее выполняет слияние до "12345678"? Ищет в массиве из 8 символов самое маленькое и собирает новый массив? Зачем тогда заранее отсортировывали половинки, если можно в изначальном массиве найти самое маленькое и собрать в новый массив? Сортировка выбором если не ошибаюсь.
Артем Уровень 15
22 декабря 2021
Я понял. В видео этот момент не объяснен. При слиянии сравниваются крайние левые элементы и самый маленький переносится в новый массив, а из старого подмассива удаляется. И потом опять сравниваются крайние левые элементы.
Рин Уровень 42
7 ноября 2023
он объяснен, но не для четырех элементов, а уже сразу для восьми
Рин Уровень 42
7 ноября 2023
А вот в данном материале этот момент, действительно, упущен
Эдуард Лоскутов Уровень 1
1 декабря 2021 

#include <stdio.h>
#include <string.h>
#include <cs50.h>

void sort (char s[], int start, int end);
void merge(char s[], int start, int startmidle, int midleend, int end);

int main(void){
    string line = get_string("Введите неотсортированный список символов: ");
    int n = strlen(line);
    sort(line, 0, n-1);
    printf("Результат: %s\n",line);
}
void sort (char s[], int start, int end){
    if (end > start){
        int midle = (start+end)/2;
        sort(s, start, midle);
        sort(s, midle+1,end);
        merge(s, start, midle, midle+1, end);
    }
}

void merge(char s[], int start, int startmidle, int midleend, int end){
    char newS[end-start+1];
    for(int i = start, j = midleend, z = 0, n = end-start+1; z < n;){
        if(s[i] <= s[j] && i <= startmidle && j <= end){
            newS[z++] = s[i++];
            continue;
        }
        if(s[j] <= s[i] && i <= startmidle && j <= end){
            newS[z++] = s[j++];
            continue;
        }
        if(i > startmidle && j <= end){
            newS[z++] = s[j++];
            continue;
        }
        if(j > end && i <= startmidle){
            newS[z++] = s[i++];
            continue;
        }
    }
    for(int i = 0, j = start;j <= end;){
        s[j++] = newS[i++];
    }
}
Plumbum Уровень 2
8 августа 2021 

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

void sort(int array[],int start, int end);
void merge(int array[], int start, int end);

int main(int argc, string argv[])
{
    int m = argc-1;
    int array[m];
    for (int i=0; i<m; i++)
    {
        array[i]=atoi(argv[i+1]);
    }

    for (int i=0; i<m; i++)
    {
        sort(array, 0, m - 1);
        printf("%2d ", array[i]);
    }
    printf("\n");
}

void sort(int array[],int start, int end)
{
    int temp;
    if (end>start) // чтобы не сортировать одно число
    {
        if (end<2)
        {
            if (array[start]>array[end])
            {
                temp = array[start];
                array[start] = array[end];
                array[end] = temp;
            }
        }
        else
        {
            int middle = (start+end) / 2;
            sort(array, start, middle);
            sort(array, middle+1, end);
            merge(array, start, end);
        }
    }
}

void merge(int array[], int start, int end)
{
    int middle = (start + end) / 2;
    int box[end];
    int a = start;
    int b = middle + 1;
    int k = 0;

    while (a <= middle && b <= end) // сравнение чисел массивов и запись меньшего
    {
        if (array[a] <= array[b])
        {
            box[k] = array[a];
            a++;
        }
        else
        {
            box[k] = array[b];
            b++;
        }
        k++;
    }

    while (a <= middle) // на случай, если все числа из b-го массива окажутся меньше чем первое число a-го
    {
        box[k] = array[a];
        a++;
        k++;
    }

    while (b <= end)
    {
        box[k] = array[b];
        b++;
        k++;
    }

    for (int c = 0; c < k; c++)
    {
        array[start + c] = box[c];
    }
}
Тимур Шамилов Уровень 35
16 декабря 2020 


public class Solution2 {
    public static void main(String[] args) {
        int [] result = new int[]{4,3,1,4,5,7,8,9,0,11,22};

        int[] sort = sort(result);
        for (int i = 0; i < result.length; i++) {
            System.out.println(sort[i]);
        }
    }

    private static int[] sort(int[] result) {
        if (result.length < 2) {
            return result;
        } else {
          int[] left = sort(Arrays.copyOfRange(result,0, result.length/2));
          int[] right = sort(Arrays.copyOfRange(result,result.length / 2, result.length));
          return merge(left ,right);
        }
    }

    private static int[] merge(int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        int[] result = new int[left.length + right.length];
        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                result[k] = left[i];
                i++;
            } else {
                result[k] = right[j];
                j++;
            }
            k++;
        }
        if (i == left.length) {
            while (j < right.length) {
                result[k] = right[j];
                j++;k++;
            }
        }
        if (j == right.length) {
            while (i < left.length) {
                result[k] = left[i];
                i++;k++;
            }
        }
        return result;
    }
}
вроде работает, и покороче, и проверок поменьше. Мб я где-то накосячил, хз)
Серега Уровень 20
29 августа 2020
https://www.youtube.com/playlist?list=PLyApprAtr5yjywFgRkxhfGfesgYoIhU8U
Михаил Уровень 1
2 августа 2020
Этот код, если вы хотите сами ввести массив через строку. Его минус в том, что он сортирует только от 0 до 9 

#include <stdio.h>
#include <cs50.h>
#include <string.h> 

void sort(string array, int start, int end);
void merge(string array, int start, int end);

int main(void)
{
    int i, n;
    string array = get_string("Введите позитивный ряд чисел:\n");
    for (i = 0, n = strlen(array); i < n; i++)
    {
        sort(array, 0, n - 1);   //вызывает функцию sort и передает ей значения, где array - наш массив, 0 - начало массива, (n - 1) - конец массива
    }
    printf("%s", array);
    printf("\n");
    return 0;
}

void merge(string array, int start, int end)
{
    int middle = (start + end) / 2; 
    int i = start,j = middle + 1, k = 0;
    char d[1000];

    while(i <= middle && j <= end)
    { 
        if(array[i] <= array[j])
        {
            d[k] = array[i];
            i++;
        }
        else
        {
            d[k] = array[j];
            j++;
        }
        k++;
    }
    while(i <= middle)
    {
        d[k] = array[i];
        i++;
        k++;
    }

    while(j <= end)
    {
        d[k] = array[j];
        j++;
        k++;
    }

    for(i = 0; i < k; i++)
    {
        array[start + i] = d[i];
    }
}


void sort(string array, int start, int end)
{
    int temp;
            if (end > start)
            {
                if(end < 2)
                {
                    if(array[start] > array[end])
                    {
                        temp = array[start];
                        array[start] = array[end];
                        array[end] = temp;
                    }
                }
                else
                {
                    int middle = (start + end) / 2;
                    sort(array, start, middle);
                    sort(array, middle+1, end);
                    merge(array, start, end);
Михаил Уровень 1
1 августа 2020 

/*
Комменты будут ниже
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 9


void sort(int array[], int start, int end);
void merge(int array[], int start, int end);

int main(void)
{
    srand(time(NULL));
    
    int array[SIZE];
    int i;
    for(i = 0; i < SIZE; i++)
    {
        array[i] = rand() % 10;
    }
    for(i = 0; i < SIZE; i++)
    {

       printf("%2d", array[i]);
    }
    printf("\n");
    for(i = 0; i < SIZE; i++)
    {
        sort(array, 0, SIZE - 1);
        printf("%2d", array[i]);
    }
    printf("\n");
    return 0;
}

void merge(int array[], int start, int end)
{
    int middle = (start + end) / 2;
    int i = start,j = middle + 1, k = 0, d[SIZE];

    while(i <= middle && j <= end)
    {
        if(array[i] <= array[j])
        {
            d[k] = array[i];
            i++;
        }
        else
        {
            d[k] = array[j];
            j++;
        }
        k++;
    }

    while(i <= middle)
    {
        d[k] = array[i];
        i++;
        k++;
    }

    while(j <= end)
    {
        d[k] = array[j];
        j++;
        k++;
    }

    for(i = 0; i < k; i++)
    {
        array[start + i] = d[i];
    }
}



void sort(int array[], int start, int end)
{
    int temp;
            if (end > start)
            {

                if(end < 2)
                {
                    if(array[start] > array[end])
                    {
                        temp = array[start];         //...меняем их местами
                        array[start] = array[end];
                        array[end] = temp;
                    }
                }

                else
                {
                    int middle = (start + end) / 2;
                    sort(array, start, middle);
                    sort(array, middle+1, end);
                    merge(array, start, end);
                }
            }
Михаил Уровень 1
1 августа 2020
Очень подробно, вдруг кому надо разжевать. 5. //rand() 6. //srand(time(NULL)) 8. /*константная переменная размера массива, чтобы не менять везде это знчение, можно поменять только здесь*/ 11. //прототип для функции sort 12. //прототип для функции merge 16. /*устанавливает в качесте базы данных текущее время чтобы значение рандомных чисел менялось, иначе оно будет одинаковым*/ 22. //подбирает случайное число от 0 до 9 и формирует наш массив из случайных чисел 27. //выводит массив, который сформировался до сортировки 32. //вызывает функцию sort и передает ей значения, где array - наш массив, 0 - начало массива, (SIZE - 1) - конец массива 33. //выводит массив, после сортировки 39. //функция merge 41. //определяем середину массива 42. //наши временные переменные и временный массив, чтобы сохранить в него соединенные части массива 44. //пока левая часть <= середины и следующее число после середины <= правой части, то выполняем условие 46. //если левая часть меньше или равна правой, то 48. //записываем левую часть в временный массив 49. //и переходим к следующему числу слева 51. //если правая часть меньше левой, то 53. //записываем правую часть в временный массив 54. //и переходим к следующему числу справа 56. //увеличиваем временный массив на 1, чтобы записать туда следующее число 59. //если вдруг выполняется только 1е условие, то 66. //если вдруг выполняется только 2е условие, то 75. //сохраняем наш временный массив в отсортированный постоянный 81. //функция sort 83. //временная переменная 87. //проверяем значение, чтобы выйти из рекурсии, выходим когда end будет 1 89. //если наше значение больше следующего, то 91, 92, 93. //эти 3 строки меняют местами наши числа в массиве 99. //определяем середину массива 100. //вызываем функицю sort и передаем значения для левой половины 101. //вызываем функцию sort и передаем значения для правой половины 102. //вызываем функцию merge для слияния правой и левой части в массив
Илья Уровень 0
21 мая 2020
Выполнять задачи с рекурсией до того как нам ее объяснили это вообще огнище. Гарвард, давай дасвиданья
Сиявуш Уровень 41 Expert
19 декабря 2019
ПОЖАЛУЙСТА объясните мне кто нибудь как функция или метод вызывает самого себя??? и что это значить? Если кто знает какие нибудь статьи на счет этого можете скинуть сюда 

public void myMethod(){
    myMethod(); // ??????????????????
}
Don DinDon Уровень 2
25 января 2020
это рекурсия. Она была тут значительно ранее.
Илья Уровень 0
21 мая 2020
она "была" тут на следующей неделе курса
Danil Lomakin Уровень 2
28 октября 2019
Пусть, как оказалось, и мудрёно, зато сам)... 3 чёртовых полных дня... 

#include <stdio.h>
#include <math.h>

void printArr(int array[], int n);
void sortArr(int old_array[], int new_array[], int start, int end, int n);
void merge(int new_array[], int n, int left_array[], int n_l, int right_array[], int n_r);

int main(void) {
    const int n = 9;
    int array[9] = {4, 8, 6, 2, 1, 7, 5, 3, 9};
    int new_array[9];

    printArr(array, n);
    sortArr(array, new_array, 0, n - 1, n);
    printArr(new_array, n);
}

void printArr(int array[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%i ", array[i]);
    }
    printf("\n");
}

void sortArr(int old_array[], int new_array[], int start, int end, int n) {
    if (n < 2)
        new_array[0] =  old_array[end];
    else {
        int l_arr[(int) round((float)n / 2)], r_arr[n / 2];

        sortArr(old_array, l_arr, start, (int) round((float)n / 2) - 1 + start, (int) round((float)n / 2));
        sortArr(old_array, r_arr, (int) round((float)n / 2) + start, n - 1 + start, n / 2);
        merge(new_array, n, l_arr, (int) round((float)n / 2), r_arr, n / 2);
    }
}

void merge(int new_array[], int n, int left_array[], int n_l, int right_array[], int n_r) {
    int l = 0, r = 0;

    while (l + r < n) {
        if ((left_array[l] <= right_array[r] && l <= n_l - 1) || r > n_r - 1) {
            new_array[l + r] = left_array[l];
            l++;
        }
        else if ((right_array[r] < left_array[l] && r <= n_r - 1) || l > n_l - 1) {
            new_array[l + r] = right_array[r];
            r++;
        }
    }
}