Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
3 / 3 / 2
Регистрация: 18.05.2014
Сообщений: 203
1

Сортировка слиянием не проходит тесты массива 10^5

01.03.2015, 20:38. Показов 715. Ответов 1
Метки нет (Все метки)

C++
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
#include <iostream>
#include <vector>
using namespace std;
 
int N;
void Merge(vector <int> &intVector,int first,int last)
{
    vector <int> helpVector(N);
 
    int middle=(first+last)/2;
    int first1=first;
    int first2=middle+1;
 
    for(int k=first;k<=last;k++)
    {
        if((first1<=middle) && ((first2>last) || (intVector[first1]<intVector[first2])))
           {
               helpVector[k]=intVector[first1];
               first1++;
           }
        else
            {
                helpVector[k]=intVector[first2];
                first2++;
            }
    }
  copy(helpVector.begin()+first,helpVector.begin()+last+1,intVector.begin()+first);
 
}
 
void Sort(vector <int> &intVector,int first,int last)
{
    if(first<last){
    Sort(intVector,first,(first+last)/2);
    Sort(intVector,(first+last)/2+1,last);
 
    Merge(intVector,first,last);
    }
}
int main()
{
    cin >> N;
 
    vector <int> intVector;
    int help;
    for(int i=0;i<N;i++)
    {
       cin >> help;
       intVector.push_back(help);
    }
 
    Sort(intVector,0,N-1);
 
    for(int i:intVector)
        cout << i << " ";
 
}
Вот код сортировки ,по идее оно должна за N log N работать. Подкорректируйте ,пожалуйста, что не так
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.03.2015, 20:38
Ответы с готовыми решениями:

Сортировка массива слиянием
Здравствуйте, помогите написать программу которая сортирует одномерный массив слиянием. Заранее...

Сортировка слиянием одного массива
доброго времени суток. у меня очередная задача, с которой я не могу справиться самостоятельно. а...

Сортировка слиянием одномерного массива
Windows Form Application

Сортировка массива методом слиянием в Java
Суть метода понятна, но не могу реализовать его в Java, очень нужна помощь.Заранее спасибо.

1
2228 / 1731 / 865
Регистрация: 21.12.2010
Сообщений: 3,074
Записей в блоге: 11
01.03.2015, 22:39 2
Ускорить можно если досортировывать оставшийся маленький массив простыми вставками (у Кормена так и рекомендуется, на мелком массиве простые вставки работают за линейное время)
C++
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
72
73
74
75
76
77
78
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
 
int N;
 
void Merge(vector <int> &intVector,int first,int last)
{
    vector <int> helpVector(N);
    int middle=(first+last)/2;
    int first1=first;
    int first2=middle+1;
 
    for(int k = first; k <= last; k++)
    {
        if((first1<=middle) && ((first2>last) || (intVector[first1]<intVector[first2])))
           {
               helpVector[k]=intVector[first1];
               first1++;
           }
        else
            {
                helpVector[k]=intVector[first2];
                first2++;
            }
    }
  copy(helpVector.begin()+first,helpVector.begin()+last+1,intVector.begin()+first);
}
 
void InsertionSort(std::vector<int>& vec, int const f, int const l)
{
    int i, j, tmp, siz = vec.size();
    for(i = f; i <= l; ++i)
    {
        tmp = vec[i];
        for(j = i - 1; j >= f && vec[j] > tmp; --j)
        {
            vec[j+1] = vec[j];
        }
        vec[j+1] = tmp;
    }
}
 
void Sort(vector <int> &intVector, int first, int last)
{
    if(first < last)
    {
        if(last - first > 20)
        {
            Sort(intVector, first, (first+last)/2);
            Sort(intVector, (first+last)/2 + 1, last);
            Merge(intVector,first,last);
        }
        else
        {
            InsertionSort(intVector, first, last);
        }
    }
}
 
int main()
{
    cin >> N;
    vector <int> vec;
    int help;
    srand(time(0));
    for(int i = 0 ; i < N; ++i)
    {
       vec.emplace_back(rand() % 100 - 50);
    }
    Sort(vec, 0, N-1);
 
    //for(int i : vec)
        //cout << i << "  ";
    std::cout << "OK";
}
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.03.2015, 22:39

Сортировка слиянием массива из вещественных псевдослучайных чисел
Подскажите, пожалуйста, почему при запуске такой программы (она сортирует слиянием массив из...

Сортировка слиянием для массива состоящего из букв
Всем привет, помогите пожалуйста с задачкой: с помощью сортировки слиянием нужно отсортировать...

Не проходит тесты
Программа не проходит почему-то тесты, хотя вроде работает, подскажите пожалуйста на счёт EOF, мне...

Программа не проходит тесты
Здравствуйте, решаю задачу: Имеется список людей с указанием их фамилии, имени и даты рождения....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.