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

C++   27 Май 2012  Автор статьи:  

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <vector>
#include <iostream>
using namespace std;
vector <int> merge(vector <int> a, vector <int> b)
//функция сливает два вектора
{
    vector<int> 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<int> merge_sort(vector <int> a)
{
    //если размер вектора меньше 1,
    //то он отсортирован
    if(a.size()<=1)
        return a;
    vector<int> 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<int> 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<<a[i]<<" ";
    }
    return 0;
}

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

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

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

  • на Delphi

  • на Java

  • на C++