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

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

13.09.2015, 23:02. Просмотров 929. Ответов 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)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.09.2015, 23:02
Ответы с готовыми решениями:

Замена сортировки массива с Sort на сортировку "пузырьком" (Не обязательно на этом коде)
int arr = new int; int k = 0, sum = 0; Random rnd = new Random(); ...

Выполнить сортировку методом естественного слияния
Пусть дан файл вещественных чисел.Выполнить сортировку методом естественного слияния. Окончательный...

Заменить сортировку в программе на сортировку методом Шелла
Добрый день Мне сказали заменить сортировку в моей программе на сортировку методом Шелла т.к. она...

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

10
6913 / 5978 / 2709
Регистрация: 14.04.2014
Сообщений: 25,504
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
0 / 0 / 0
Регистрация: 14.02.2014
Сообщений: 54
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
6913 / 5978 / 2709
Регистрация: 14.04.2014
Сообщений: 25,504
14.09.2015, 21:35 4
Это особенность Visual Studio. Отключи в настройках проекта, обрабатывать предупреждения как ошибки - Нет.
0
lss
935 / 863 / 356
Регистрация: 10.10.2012
Сообщений: 2,706
15.09.2015, 01:06 5
Цитата Сообщение от nmcf Посмотреть сообщение
Это особенность Visual Studio. Отключи в настройках проекта, обрабатывать предупреждения как ошибки - Нет.
Цитата Сообщение от Erbe Посмотреть сообщение
microsoft visual studio 14.0
Не поможет. Выше всех инклудов пропиши:
C++
1
#define _SCL_SECURE_NO_WARNINGS
0
6913 / 5978 / 2709
Регистрация: 14.04.2014
Сообщений: 25,504
15.09.2015, 07:00 6
Цитата Сообщение от lss Посмотреть сообщение
Не поможет
У меня же работает без #define.
0
Эксперт С++
3206 / 1733 / 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
935 / 863 / 356
Регистрация: 10.10.2012
Сообщений: 2,706
15.09.2015, 14:25 8
Цитата Сообщение от nmcf Посмотреть сообщение
У меня же работает без #define.
Студия какая?
0
6913 / 5978 / 2709
Регистрация: 14.04.2014
Сообщений: 25,504
15.09.2015, 18:15 9
2012. Просто я создал пустой проект без sdl. Выводится только предупреждение.
1
lss
935 / 863 / 356
Регистрация: 10.10.2012
Сообщений: 2,706
15.09.2015, 19:58 10
Цитата Сообщение от nmcf Посмотреть сообщение
без sdl
Вот SDL и нужно отключать в параметрах проекта, а если не оключить, то вот это не поможет(в 15-й студии, о чём я и написал):
Цитата Сообщение от nmcf Посмотреть сообщение
Отключи в настройках проекта, обрабатывать предупреждения как ошибки - Нет.
Если не отключать SDL, то #define поможет.
1
0 / 0 / 0
Регистрация: 14.02.2014
Сообщений: 54
28.09.2015, 16:46  [ТС] 11
помогло отключение.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.09.2015, 16:46

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Написать программу сортировки методом слияния
Даны две последовательности рассортированных чисел А(15) и В(10). Получить общую последовательность...

Визуализация сортировки массива методом слияния
Необходимо написать программу визуальной сортировки массива методом слияния.Возник вопрос ,как это...

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

Графическая иллюстрация сортировки массивов алгоритмом слияния
Напишите программу для графической иллюстрации сортировки массивов алгоритмом слияния. Массивы...

Чем записать видео - работы в обычной программе
Написана программа на C#. Нужно сделать демо версию работы в ней. Как это проще сделать? Скачал...

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


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

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

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