Введение:
В этой статье я попытаюсь объяснить вам алгоритм сортировки слиянием, известный как merge_sort, простым языком. Если
Ты ранее не мог понять, как он работает, то эта статья для тебя. Здесь не будет обсуждаться сложность асимптотики или
математическое доказательство, так как они усложняют все, и в интернете уже много написано и доказано на эту тему.
Что от вас требуется:
- Знать функциональное программирование и основы языка C++
- Хотя бы раз в жизни слышать, что такое рекурсия и как она работает
Начало:
Есть много видов сортировки, такие как quick_sort, bubble_sort, shell_sort и многие другие.
Но самый простой из них - это bubble_sort, то есть вложенный цикл и обмен элементов. Но на практике он очень
медленный.
Поверьте, когда ты будешь решать задачи, тебе обязательно пригодится сортировка слиянием.
Вот как сортировка слиянием разделяет и собирает массив: (моя таблица тебе вряд-ли понравится можещь поискать другое)
Массив и вектор имеется ввиду массив
Исходный массив:
| 1 | 5 | 8 | 9 | 6 |
|---|---|---|---|---|
| arr[0] | arr[1] | arr[2] | arr[3] | arr[4] |
Разделение на подмассивы:
| 1 | 5 | 8 | 9 | 6 |
|---|---|---|---|---|
| 1 | 5 | 8 | - | - |
| 9 | 6 | - | - | - |
| 1 | 5 | - | - | - |
| 9 | - | - | - | - |
| 6 | - | - | - | - |
| 1 | - | - | - | - |
| 5 | - | - | - | - |
Слияние подмассивов:
| 1 | 5 | - | - | - |
|---|---|---|---|---|
| 5 | 1 | - | - | - |
| 9 | 6 | - | - | - |
| 6 | 9 | - | - | - |
| 1 | 5 | 6 | 9 | - |
| 1 | 5 | 6 | 8 | 9 |
Итоговый отсортированный массив:
| 1 | 5 | 6 | 8 | 9 |
|---|---|---|---|---|
| arr[0] | arr[1] | arr[2] | arr[3] | arr[4] |
1
std::vector<int> arr {1,5,8,9,6}; // массив будет в std векторе
1
void merge_sort(std::vector<int>& arr, int start, int end);
Ты видел, функция будет принимать сам массив (важно! массив нужно передать через ссылку)
и два типа целых чисел start и end
1
2
3
4
5
6
7
int main() {
std::vector<int> arr {1,5,8,9,6};
merge_sort(arr, 0, arr.size()); // здесь 0 - это начало массива, то есть это start
// arr.size() - это конец массива, то есть end == 5
std::cout << "Вывод на косноль отсортированный массив\n";
for(auto i : arr) std::cout << i " ";
}
Как показано выше на схеме, массив должен разделиться на две части, а затем еще на две части, пока размер массива больше ‘1’
1
2
3
void merge_sort(std::vector<int>& arr, int start, int end) { // дальше код не будет дублироваться, так что читай внимательно :)
if(end - start < 2) return; // вот это и есть условие рекурсии. Если не поставить эту строку, то скорее всего
// рекурсия будет выполняться до тех пор, пока не переполнится стек
Ты должен разделить массив на две части. Но до этого надо найти центр массива.
1
2
3
4
5
6
7
8
const std::size_t mid = (start + end) / 2 // в первой рекурсии массив просто разделится на две части, вот и все
// теперь надо разделить массив (на самом деле сам массив не будет разделен, а только индексы будут разделены)
merge_sort(arr, start, mid) // передать самой рекурсии часть диапазона массива
// то есть выше будут переданы индексы для (1,5,8)
merge_sort(arr, mid, end) // а вот здесь передается остальная часть
// вот выше будет разделено, пока вот это условие верно if(end - start < 2)
В этом участке кода будет выполнен после того, как массив раздроблен до мелочей. Теперь обратно надо собрать все, то есть в стиле “раскатай язык обратно” (шутка). Но прежде всего нужен временный буфер.
1
2
3
4
5
6
std::vector<int> buff;
buff.reserve(end - start); // будет лучше, если сразу зарезервировать память ( рекомендасион почитать про std vector capacity)
std::size_t left = start; // это типа arr[i], то есть arr[left]. Диапазон его всегда до mid, так как массив разделен на две части
// и у левой части последний индекс всегда до mid
std::size_t right = mid; // а это точно такой же, как left, только у него диапазон с mid до end
Теперь надо заполнить временный вектор, ой, то есть буфер (buff).
1
2
3
4
5
6
7
8
9
10
11
while((left < mid) && (right < end)) { // обрати внимание здесь
// условие поставлено очень странно. Здесь условие говорит, что цикл будет выполняться до тех пор, пока start меньше чем mid, а right меньше end
if(arr[left] < arr[right]) { // здесь на самом деле можно ставить какой-нибудь предикат. Я решил специально не ставить его, так как он усложняет код
buff.push_back(arr[left]); // Если условие выполняется, добавляем элемент из левой части массива в буфер
++left; // условие сработало, значит, индекс надо увеличить на один, то есть i++
} else {
buff.push_back(arr[right]);
++right;
}
} // выше в условии if говорится так: если левая часть удовлетворяет условию, то добавить в буфер элемент из левой части массива, а иначе - из правой части
В буфер добавились элементы, то скорее всего некоторые элементы останутся из левой или правой части. Здесь у
тебя должен быть вопрос: а как может остаться элемент, если в начале массив разделен на две части? Это очень просто. Как
заметил, размер массива нечетный, а это arr.size()%2 != 0 приводит к остатку, а это и есть оставшийся элемент.
1
2
3
4
5
6
7
8
9
while(left < mid) {
buff.push_back(arr[left]);
++left; // здесь как в вышестоящем цикле
}
while(right < end) {
buff.push_back(arr[right]);
++right;
}
Ой, все, наконец-то написал почти все. Теперь самый последний штрих. Ранее я напомнил, чтобы массив обязательно передали через ссылку. Вот это сейчас пригодится. Теперь просто в массив вставь данные из буфера и все. Не будем выпендриваться, просто будем использовать std::copy.
1
2
3
4
5
std::copy(buff.begin(), buff.end(), arr.begin() + start);
// обрати внимание на условие копирования
// весь буфер копируется в массив, начиная с индекса start. Это сделано из-за т
}
Исходный код здесь
Если ты понял все, попробуй реализовать merge_sort с функцией merge
Если получилось все, попробуй merge_sort сделать для single_linked_list
