Сортировка слиянием (Merge Sort) (Реализация на C++)

C++   27 мая 2012  Автор статьи:  

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

#include
#include
using namespace std;
vector merge(vector a, vector b)
//функция сливает два вектора
{
vector c(a.size()+b.size());//результирующий вектор
//количество использованных вершин
int kol1 = 0;//в векторе а
int kol2 = 0;//в векторе b
//заполним массив c
for(int i = 0; i < c.size(); i++) { //если мы уже полностью использовали вектора а, //то нам осталось дописать элементы вектора b if(kol1==a.size()) { c[i] = b[kol2]; kol2++; continue; } //наоборот if(kol2==b.size()) { c[i] = a[kol1]; kol1++; continue; } //так как наши вектора еще не полностью //использованы, то нужно сравнить какое //значение ставить на следующее место if(a[kol1]<=b[kol2]) { c[i] = a[kol1]; kol1++; } else { c[i] = b[kol2]; kol2++; } } return c; } //функция сортирует вектор vector merge_sort(vector a)
{
//если размер вектора меньше 1,
//то он отсортирован
if(a.size()<=1) return a; vector b,c;
b.assign(a.begin(), a.end()-(a.size()/2));
c.assign(a.end()-(a.size()/2), a.end());
return merge(merge_sort(b),merge_sort(c));
}
int main()
{

vector a;
for(int i = 0; i < 10; i++) { a.push_back(rand()); } a = merge_sort(a); for(int i = 0;i < a.size();i++) { cout<

  • Ислам Умаров

    А можно как-то сократить код?

Научиться программировать

  • на Delphi

  • на Java

  • на C++