Форум программистов, компьютерный форум CyberForum.ru

Предусмотреть подсчет общего количества перестановок и вывод промежуточного массива после каждого цикла сортировки - C++

Восстановить пароль Регистрация
 
GODofART
2 / 2 / 0
Регистрация: 19.11.2011
Сообщений: 52
16.01.2014, 02:37     Предусмотреть подсчет общего количества перестановок и вывод промежуточного массива после каждого цикла сортировки #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
#include "iostream"
 
using namespace std;
 
void insertSort();   // объявление функции сортировки
template< class T >
void insertSort(T* a, int size) 
{
    T tmp;
    for (int i = 1, j; i < size; ++i) // цикл проходов, i - номер прохода
    {
        tmp = a[i]; 
        for (j = i - 1; j >= 0 && a[j] > tmp; --j) // поиск места элемента в готовой последовательности 
            a[j + 1] = a[j];    // сдвигаем элемент направо, пока не дошли
        a[j + 1] = tmp; // место найдено, вставить элемент    
    }
}
int main()
{
setlocale(LC_ALL, "Russian");
int n=10;   // Количество элементов массива
cout << endl;
cout << "Массив: " << endl;
int *mas = new int [n];
srand(NULL);
for (int i = 0; i < n; i++)
{
mas[i] = rand() % 20 - 10;   // заполняем массив случайными числами
cout << mas[i] << " ";   // выводим массив на экран
}
cout << "\n\n";
 
insertSort(mas, n);   // вызываем функцию сортировки Выбором
cout << "Отсортированный массив: " << endl;
for (int i = 0; i < n; i++)
{
cout << mas[i] << " ";   // Вывод на экран отсортированного массива
}
cout << "\n";
system("PAUSE");
return 0;
}
Добавлено через 9 часов 19 минут
Всё еще актуально.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2014, 02:37     Предусмотреть подсчет общего количества перестановок и вывод промежуточного массива после каждого цикла сортировки
Посмотрите здесь:

вывод массива после сортировки C++
Подсчет количества обменов и сравнений в алгоритмах сортировки C++
C++ График зависимость количества перестановок и сравнений от размерности массива для алгоритмов сортировки
график зависимостей количества перестановок от размерности массива C++
C++ Выполнить сортировку массива по убыванию и проконтролировать ее результат. Произвести подсчет перестановок при сортировке
Выполнить сортировку массива по убыванию и проконтролировать ее результат. Произвести подсчет перестановок при сортировке C++
Очистка экрана после каждого выполнения цикла! C++
Быстрая сортировка, неправильный подсчет количества сравнений и перестановок C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
volvo
Супер-модератор
 Аватар для volvo
21815 / 14178 / 3949
Регистрация: 22.10.2011
Сообщений: 25,055
Записей в блоге: 2
16.01.2014, 02:47     Предусмотреть подсчет общего количества перестановок и вывод промежуточного массива после каждого цикла сортировки #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
#include <iostream>
#include <cstdlib>
 
using namespace std;
 
template< class T >
void Print(T* a, int size)
{
    for (int i = 0; i < size; i++)
    {
        cout << a[i] << " ";   // Вывод на экран массива
    }
    cout << "\n";
 
}
 
template< class T >
void insertSort(T* a, int size, int& counter)
{
    T tmp;
    for (int i = 1, j; i < size; ++i) // цикл проходов, i - номер прохода
    {
        tmp = a[i];
        for (j = i - 1; j >= 0 && a[j] > tmp; --j) // поиск места элемента в готовой последовательности
        {
            a[j + 1] = a[j];    // сдвигаем элемент направо, пока не дошли
            counter += 1;
        }
        a[j + 1] = tmp; // место найдено, вставить элемент
        counter += 2;
        Print(a, size);
    }
}
int main()
{
    setlocale(LC_ALL, "Russian");
    int n=10;   // Количество элементов массива
    cout << endl;
    cout << "Массив: " << endl;
    int *mas = new int [n];
    srand(0);
    for (int i = 0; i < n; i++)
        mas[i] = rand() % 20 - 10;   // заполняем массив случайными числами
    Print(mas, n);
    cout << "\n";
 
    int counter = 0;
    insertSort(mas, n, counter);   // вызываем функцию сортировки Выбором
    cout << "Отсортированный массив: " << endl;
    Print(mas, n);
    cout << "Число перестановок: " << counter << endl;
    system("PAUSE");
    return 0;
}
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4924 / 2667 / 243
Регистрация: 29.11.2010
Сообщений: 7,421
16.01.2014, 05:27     Предусмотреть подсчет общего количества перестановок и вывод промежуточного массива после каждого цикла сортировки #3
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
#include <iostream>
#include <clocale>
#include <algorithm>
 
using namespace std;
 
int main()
{
    setlocale(LC_ALL, "");
    const int N = 4;
    int A[N]; // имеем множество A {1, ... N}
    int counter = 0; // счетчик числа перестановок
    for (int i = 0; i < N; i++) // заполняем множество
        A[i] = i + 1;
    // sort(A, A + N); // необходимо при вводе произвольных элементов
    do
    {
        for (int i=0; i < N; i++)
            cout << A[i] << ' ';
        cout << endl;
        counter++;
    } while (next_permutation(A, A + N));
    cout << "Всего перестановок: " << counter << endl;
    return 0;
}
2 вариант (велосипед mode on):
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 <clocale>
 
using namespace std;
 
// вывод множества на экран
void print(const int *A, const int size);
// функция перестановки двух чисел
void swap(int &, int &);
// функция генерации следующей перестановки
void next_perm(int k, int *A, const int size, int &counter);
 
 
int main()
{
    setlocale(LC_ALL, "");
    const int N = 4;
    int A[N]; // имеем множество A {1, ... N}
    int counter = 0; // счетчик числа перестановок
    for (int i = 0; i < N; i++) // заполняем множество
        A[i] = i + 1;
    next_perm(0, A, N, counter);
    cout << "Всего перестановок: " << counter << endl;
    return 0;
}
 
void print(const int *A, const int size)
{
    for (int i=0; i < size; i++)
        cout << A[i] << ' ';
    cout << endl;
}
 
void swap(int &x, int &y)
{
    int tmp = x;
    x = y;
    y = tmp;
}
 
void next_perm(int k, int *A, const int size, int &counter)
{
    // если заполнилось
    if (k == size)
    {
        print(A, size);
        counter++;
        return;
    }
 
    for(int i = k; i < size; i++)
    {
        swap(A[k], A[i]);
        next_perm(k + 1, A, size, counter); // следующая перестановка
        swap(A[k], A[i]);
    }
}
Yandex
Объявления
16.01.2014, 05:27     Предусмотреть подсчет общего количества перестановок и вывод промежуточного массива после каждого цикла сортировки
Ответ Создать тему
Опции темы

Текущее время: 12:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru