Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
Erbe
0 / 0 / 0
Регистрация: 14.02.2014
Сообщений: 54
Завершенные тесты: 2
1

Замена обычной сортировки на сортировку слияния в программе

13.09.2015, 23:02. Просмотров 826. Ответов 10
Метки нет (Все метки)

У меня тут есть моя программа которая сортирует данные с одного файла в другой обычной сортировкой. Можете помочь с заменой обычной сортировки на сортировку слиянием. Я сам пытался, искал в нете, но там везде по разному, изменял этот участок
C++
1
2
3
4
5
6
7
8
9
10
11
12
    for (int i = 0;i<n - 1;i++)
    {
        for (int j = i + 1;j<n;j++)
        {
            if (a[i].kvartira>a[j].kvartira)
            {
                temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
        }
    }
много раз, но так ничего и не вышло.

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
#include "stdafx.h"
#include <string> 
#include <fstream>
#include <iomanip>
#include <iostream>
using namespace std;
unsigned int start_time = clock();
ifstream in("D:\\1.txt");
ofstream out("D:\\2.txt");
struct group
{
    string kvartira;
    int stoimost;
    void print();
};
void group::print()
{
    out << kvartira << " " << "которая стоит:"<< stoimost << " "  << "гривны" <<endl;
}
void sort(group*a, int n)
{
    group temp;
    for (int i = 0;i<n - 1;i++)
    {
        for (int j = i + 1;j<n;j++)
        {
            if (a[i].kvartira>a[j].kvartira)
            {
                temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
        }
    }
}
int main()
{
    setlocale(LC_ALL, "Russian");
    int n = 0;
    group a[10];
    while (in.peek() != EOF)
    {
        in >> a[n].kvartira;
        in >> a[n].stoimost;
        n++;
    }
    sort(a, n);
    for (int i = 0;i<n;i++)
    {
        a[i].print();
    }
    out.close();
    in.close();
    unsigned int end_time = clock(); // конечное время
    unsigned int search_time = end_time - start_time; // искомое время
    cout << "\n runtime = " << search_time / 1000.0 << endl; // время работы программы
    system("pause");
    return 0;
}
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.09.2015, 23:02
Ответы с готовыми решениями:

Алгоритм сортировки методом слияния
Напишите программу, реализующую алгоритм сортировки методом слияния и получите...

Реализовать шаблон сортировки массива методом слияния
Реализовать шаблон сортировки массива методом слияния.

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

Написать программу для сортировки массива способами шелла вставки слияния и пузырьком
Написать программу для сортировки массива способами шелла вставки слияния и...

Выполнить сортировку массива с помощью стандартной функции быстрой сортировки qsort
2. Выполнить сортировку массива с помощью стандартной функции быстрой...

10
nmcf
6398 / 5661 / 2580
Регистрация: 14.04.2014
Сообщений: 23,942
14.09.2015, 16:32 2
Лучший ответ Сообщение было отмечено Erbe как решение

Решение

В Википедию заглядывай иногда.
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
#include <algorithm>
#include <cstddef>
#include <iterator>
 
struct group
{
    string kvartira;
    int stoimost;
    bool operator < (const group &g)
    {
        return kvartira < g.kvartira;
    }
    void print();
};
 
void merge_sort(group array[], std::size_t size)
{
    if (size > 1)
    {
        std::size_t const left_size = size / 2;
        std::size_t const right_size = size - left_size;
 
        merge_sort(&array[0], left_size);
        merge_sort(&array[left_size], right_size);
 
        std::size_t lidx = 0, ridx = left_size, idx = 0;
        group *tmp_array = new group[size];
 
        while (lidx < left_size || ridx < size)
        {
            if (array[lidx] < array[ridx])
            {
                tmp_array[idx++] = std::move(array[lidx]);
                lidx++;
            }
            else
            {
                tmp_array[idx++] = std::move(array[ridx]);
                ridx++;
            }
 
            if (lidx == left_size)
            {
                std::copy(std::make_move_iterator(&array[ridx]),
                          std::make_move_iterator(&array[size]),
                          &tmp_array[idx]);
                break;
            }
            if (ridx == size)
            {
                std::copy(std::make_move_iterator(&array[lidx]),
                          std::make_move_iterator(&array[left_size]),
                          &tmp_array[idx]);
                break;
            }
        }
 
        std::copy(std::make_move_iterator(tmp_array),
                  std::make_move_iterator(&tmp_array[size]),
                  array);
 
        delete []tmp_array;
    }
}
0
Erbe
0 / 0 / 0
Регистрация: 14.02.2014
Сообщений: 54
Завершенные тесты: 2
14.09.2015, 21:11  [ТС] 3
У меня вот такая ошибка выскакивает
1>------ Сборка начата: проект: 244, Конфигурация: Debug Win32 ------
1> 244.cpp
1>c:\program files (x86)\microsoft visual studio 14.0\vc\include\xutility(2230): error C4996: 'std::_Copy_impl': Function call with parameters that may be unsafe - this call relies on the caller to check that the passed values are correct. To disable this warning, use -D_SCL_SECURE_NO_WARNINGS. See documentation on how to use Visual C++ 'Checked Iterators'
1> c:\program files (x86)\microsoft visual studio 14.0\vc\include\xutility(2216): note: см. объявление "std::_Copy_impl"
1> c:\users\влад\documents\visual studio 2015\projects\244\244\244.cpp(57): note: см. ссылку на создание экземпляров функции шаблон при компиляции "_OutIt std::copy<std::move_iterator<group *>,group*>(_InIt,_InIt,_OutIt)"
1> with
1> [
1> _OutIt=group *,
1> _InIt=std::move_iterator<group *>
1> ]
========== Сборка: успешно: 0, с ошибками: 1, без изменений: 0, пропущено: 0 ==========
Вот код :
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include "stdafx.h"
#include <string> 
#include <fstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <cstddef>
#include <iterator>
using namespace std;
unsigned int start_time = clock();
ifstream in("D:\\1.txt");
ofstream out("D:\\2.txt");
struct group
{
    string kvartira;
    int stoimost;
    bool operator < (const group &g)
    {
        return kvartira < g.kvartira;
    }
    void print();
};
void group::print()
{
    out << kvartira << " " << "которая стоит:" << stoimost << " " << "гривны" << endl;
}
void merge_sort(group array[], std::size_t size)
{
    if (size > 1)
    {
        std::size_t const left_size = size / 2;
        std::size_t const right_size = size - left_size;
 
        merge_sort(&array[0], left_size);
        merge_sort(&array[left_size], right_size);
 
        std::size_t lidx = 0, ridx = left_size, idx = 0;
        group *tmp_array = new group[size];
 
        while (lidx < left_size || ridx < size)
        {
            if (array[lidx] < array[ridx])
            {
                tmp_array[idx++] = std::move(array[lidx]);
                lidx++;
            }
            else
            {
                tmp_array[idx++] = std::move(array[ridx]);
                ridx++;
            }
 
            if (lidx == left_size)
            {
                std::copy(std::make_move_iterator(&array[ridx]),
                    std::make_move_iterator(&array[size]),
                    &tmp_array[idx]);  // ВОТ ТУТ ОШИБКА!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                break;
            }
            if (ridx == size)
            {
                std::copy(std::make_move_iterator(&array[lidx]),
                    std::make_move_iterator(&array[left_size]),
                    &tmp_array[idx]);
                break;
            }
        }
 
        std::copy(std::make_move_iterator(tmp_array),
            std::make_move_iterator(&tmp_array[size]),
            array);
 
        delete[]tmp_array;
    }
}
int main()
{
    setlocale(LC_ALL, "Russian");
    int n = 0;
    group a[10];
    while (in.peek() != EOF)
    {
        in >> a[n].kvartira;
        in >> a[n].stoimost;
        n++;
    }
    merge_sort(a, n);
    for (int i = 0;i<n;i++)
    out.close();
    in.close();
    unsigned int end_time = clock(); // конечное время
    unsigned int search_time = end_time - start_time; // искомое время
    cout << "\n runtime = " << search_time / 1000.0 << endl; // время работы программы
    system("pause");
    return 0;
}
0
nmcf
6398 / 5661 / 2580
Регистрация: 14.04.2014
Сообщений: 23,942
14.09.2015, 21:35 4
Это особенность Visual Studio. Отключи в настройках проекта, обрабатывать предупреждения как ошибки - Нет.
0
lss
930 / 859 / 355
Регистрация: 10.10.2012
Сообщений: 2,705
15.09.2015, 01:06 5
Цитата Сообщение от nmcf Посмотреть сообщение
Это особенность Visual Studio. Отключи в настройках проекта, обрабатывать предупреждения как ошибки - Нет.
Цитата Сообщение от Erbe Посмотреть сообщение
microsoft visual studio 14.0
Не поможет. Выше всех инклудов пропиши:
C++
1
#define _SCL_SECURE_NO_WARNINGS
0
nmcf
6398 / 5661 / 2580
Регистрация: 14.04.2014
Сообщений: 23,942
15.09.2015, 07:00 6
Цитата Сообщение от lss Посмотреть сообщение
Не поможет
У меня же работает без #define.
0
Mr.X
Эксперт С++
3182 / 1709 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
15.09.2015, 10:00 7
Цитата Сообщение от nmcf Посмотреть сообщение
В Википедию заглядывай иногда
Ну и в STL можно.
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string     T_str;
/////////////////////////////////////////////////////////////////////////////////////////
struct T_apartment
{
    //-----------------------------------------------------------------------------------
    T_str   name_;
    int     cost_;
    //-----------------------------------------------------------------------------------
    T_apartment
        (
            T_str   name    =   "",
            int     cost    =   0
        )
        :
        name_   ( name ),
        cost_   ( cost )
    {}
    //-----------------------------------------------------------------------------------
    bool operator < ( const     T_apartment     &   apartment )                     const
    {
        return name_ < apartment.name_;
    }
    //-----------------------------------------------------------------------------------
    friend
    std::ostream    &   operator<<
        (
            std::ostream            &   ostr,
            T_apartment     const   &   apartment
        )
    {
        ostr    <<  "Квартира "
                <<  apartment.name_
                <<  " стоимостью $"
                <<  apartment.cost_;
 
        return  ostr;
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector     < T_apartment   >   T_apartments;
/////////////////////////////////////////////////////////////////////////////////////////
template< typename  TT_it >
void merge_sort
    (
        TT_it   begin,
        TT_it   end
    )
{
    auto    size    =   end - begin;
 
    if( size > 1 )
    {
        auto    middle  =   begin + size / 2;
 
        merge_sort
            (
                begin,
                middle
            );
 
        merge_sort
            (
                middle,
                end
            );
 
        std::inplace_merge
            (
                begin,
                middle,
                end
            );
    }//if
}
/////////////////////////////////////////////////////////////////////////////////////////
template< typename  T_cont >
void    print( T_cont   &   cont )
{
    std::copy
        (
            cont.begin                                      (),
            cont.end                                        (),
            std::ostream_iterator< T_cont::value_type >     ( std::cout, "\n" )
        );
}
/////////////////////////////////////////////////////////////////////////////////////////
T_apartment     get_apartment()
{
    static  char    letter  =   'a';
    static  int     cost    =   1;
 
    return  T_apartment
                (
                    T_str( 3, letter++ ),
                    cost++
                );
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    srand(unsigned(time(0)));
    const   int     APARTMENTS_SIZE     =   10;
    T_apartments    apartments( APARTMENTS_SIZE );
 
    std::generate
        (
            apartments.begin    (),
            apartments.end      (),
            get_apartment
        );
 
    std::random_shuffle
        (
            apartments.begin    (),
            apartments.end      ()
        );
 
    std::cout   <<  "Исходный массив:"
                <<  std::endl;
 
    print( apartments );
 
    merge_sort
        (
            apartments.begin    (),
            apartments.end      ()
        );
 
    std::cout   <<  std::endl
                <<  "Отсортированный массив:"
                <<  std::endl;
 
    print       ( apartments    );
    system      ("pause"        );
}
0
lss
930 / 859 / 355
Регистрация: 10.10.2012
Сообщений: 2,705
15.09.2015, 14:25 8
Цитата Сообщение от nmcf Посмотреть сообщение
У меня же работает без #define.
Студия какая?
0
nmcf
6398 / 5661 / 2580
Регистрация: 14.04.2014
Сообщений: 23,942
15.09.2015, 18:15 9
2012. Просто я создал пустой проект без sdl. Выводится только предупреждение.
1
lss
930 / 859 / 355
Регистрация: 10.10.2012
Сообщений: 2,705
15.09.2015, 19:58 10
Цитата Сообщение от nmcf Посмотреть сообщение
без sdl
Вот SDL и нужно отключать в параметрах проекта, а если не оключить, то вот это не поможет(в 15-й студии, о чём я и написал):
Цитата Сообщение от nmcf Посмотреть сообщение
Отключи в настройках проекта, обрабатывать предупреждения как ошибки - Нет.
Если не отключать SDL, то #define поможет.
1
Erbe
0 / 0 / 0
Регистрация: 14.02.2014
Сообщений: 54
Завершенные тесты: 2
28.09.2015, 16:46  [ТС] 11
помогло отключение.
0
28.09.2015, 16:46
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.09.2015, 16:46

Выполнить сортировку массива с помощью стандартной функции быстрой сортировки qsort
Здравствуйте! прошу вас о помощи! помогите пожалуйста с программой! &quot;Выполнить...

Допишите сортировку слияниями к программе банковских счетов
Напишите программу ведения банковских счетов. Ежемесячная ставка по банковским...

Сортировку вставками меняем на Пирамидальную сортировку и на Сортировку подсчётом
Здравствуйте. Я не как не могу разобраться.Помогите. У меня есть листинг...


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

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

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