undefined

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

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
Комментарии (23)
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION
Тимур Шамилов Уровень 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;
    }
}
вроде работает, и покороче, и проверок поменьше. Мб я где-то накосячил, хз)
Серега Уровень 19 Кривой Рог Украина
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++;
        }
    }
}
Юрий Уровень 0
9 августа 2019
На полное авторство не претендую, однако, хоть и по примеру, писал сам, местами со своими изменениями. Вроде работает:

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

//прототипы
void Sort(int a[], int first, int last);
void Merge(int a[], int first, int last);

int main(void)
{
    printf("Please enter number of elements to sort: ");
    int n = get_int("");
    int a[n], i;
    printf("Enter your elements: \n");
    for (i = 0; i < n; i++)
    {
        printf("a[%i]= ", i);
        a[i] = get_int("");
    }
    Sort(a, 0, n - 1);
    printf("Your sorted elements are: ");
    for (i = 0; i < n; i++)
    {
        printf("%i ",a[i]);
    }
    printf("\n");
}

void Sort(int a[], int first, int last)
{
    if (first < last)
    {
        Sort(a, first, (first + last) / 2); //делим левую часть
        Sort(a, (first + last) / 2 + 1, last); //делим правую часть
        Merge(a, first, last); //собираем то, что получилось в функции объединения (см. ниже)
    }
}

void Merge(int a[], int first, int last)
{
    int middle, left, right, j; //по очереди: номер среднего элемента; начало левой половины; начало второй; счетчик
    int temp[last + 1];
    middle = (first + last) / 2;
    left = first;
    right = middle + 1;
    for (j = first; j <= last; j++)
    {
//Далее определяем какой из элементов меньше, записываем в временный массив и смещаем счетчик на следующий элемент
//Также учтены ситуации, когда в половинах заканчиваются элементы: в таком случае меньшим окажется элемент из соседней половины
        if ((left <= middle) && ((right > last) || (a[left] < a[right])))
        {
            temp[j] = a[left];
            left++;
        }
        else
        {
            temp[j] = a[right];
            right++;
        }
    }
    for (j = first; j <= last; j++)
    {
        a[j] = temp[j];
    }
}
Владимир Казак Уровень 0
6 августа 2019
я уже недели 2 сижу а слияние никак не выходит
FireGames Уровень 15 Львов Украина
4 июля 2019
Если я сижу уже 2 часа и не могу понять как это записать в код, значил ли что я тупой и мне не стоит программировать?