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

Harvard CS50

3 уровень , 11 лекция

Открыта

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

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)

ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ

Артем Уровень 15

22 декабря 2021

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

Эдуард Лоскутов Уровень 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);
                }
            }



  Илья
      Уровень 0

      

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



  Сиявуш
      Уровень 41

      Expert

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

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



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