JavaRush/Java Курсы/Harvard CS50/Алгоритмы сортировки. Сортировка слиянием

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

Открыта

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

class=»embed-responsive-item»

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

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

Алгоритмы сортировки. Сортировка слиянием - 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)

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

Артем Работает в IT Universe

22 декабря 2021, 06:03

В видео не рассказан принцип слияния половинок. Например начиная с 9:54. Имеем 2 половинки: "2468" и "1357". Как он далее выполняет слияние до "12345678"? Ищет в массиве из 8 символов самое маленькое и собирает новый массив? Зачем тогда заранее отсортировывали половинки, если можно в изначальном массиве найти самое маленькое и собрать в новый массив? Сортировка выбором если не ошибаюсь.

Артем Работает в IT Universe

22 декабря 2021, 06:17

Я понял. В видео этот момент не объяснен. При слиянии сравниваются крайние левые элементы и самый маленький переносится в новый массив, а из старого подмассива удаляется. И потом опять сравниваются крайние левые элементы.

Рин Java Developer

7 ноября 2023, 01:08

он объяснен, но не для четырех элементов, а уже сразу для восьми

Рин Java Developer

7 ноября 2023, 01:09

А вот в данном материале этот момент, действительно, упущен

Эдуард Лоскутов

Уровень 1

1 декабря 2021, 14:03

#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, 17:51

#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, 12:30

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;
    }
}

вроде работает, и покороче, и проверок поменьше. Мб я где-то накосячил, хз)

Серега Android Developer

29 августа 2020, 11:41

https://www.youtube.com/playlist?list=PLyApprAtr5yjywFgRkxhfGfesgYoIhU8U

Михаил

Уровень 1

2 августа 2020, 09:09

Этот код, если вы хотите сами ввести массив через строку. Его минус в том, что он сортирует только от 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, 18:53

/*
Комменты будут ниже
*/
#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, 19:06

Очень подробно, вдруг кому надо разжевать. 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, 11:20

Выполнять задачи с рекурсией до того как нам ее объяснили это вообще огнище. Гарвард, давай дасвиданья

Сиявуш Android Developer в Эсхата Банк. Таджики

Expert

19 декабря 2019, 14:21

ПОЖАЛУЙСТА объясните мне кто нибудь как функция или метод вызывает самого себя??? и что это значить? Если кто знает какие нибудь статьи на счет этого можете скинуть сюда

public void myMethod(){
    myMethod(); // ??????????????????
}

Don DinDon

Уровень 2

25 января 2020, 20:45

это рекурсия. Она была тут значительно ранее.

Илья

Уровень 0

21 мая 2020, 11:22

она "была" тут на следующей неделе курса

Danil Lomakin

Уровень 2

28 октября 2019, 16:03

Пусть, как оказалось, и мудрёно, зато сам)... 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++;
        }
    }
}