14 / 10 / 4
Регистрация: 10.09.2018
Сообщений: 373
1

Доработать код. Найти количество обменов в сортировке методом Вставки

05.12.2018, 20:29. Показов 992. Ответов 7
Метки нет (Все метки)

Здравствуйте пишу сортировку методом вставки. В ней нужно найти количество сравнений и количество обменов. Количество сравнений я нашел (вроде бы). А вот с количеством обменов возникла проблема. Помогите вычислить?
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 "pch.h"
#include <iostream>
#include <ctime>
using namespace std;
 
 
 
int main()
{
    setlocale(0, "");
 
    const int size1 = 1000;
    const int size2 = 10000;
    const int size3 = 10000;
    int array1[size1]{};
    int sravnenie = 0;
    int obmen = 0;
 
    //////Сортировка по возрастанию/////
 
    {
        for (int i = 0; i < size1; i++)
        {
            array1[i] = rand() % 1000;
 
        }
 
 
        int i, j;
        for (i = 0; i < size1; i++) {  // цикл проходов, i - номер прохода
            
                int x = array1[i];
            
            // поиск места элемента в готовой последовательности 
            for (j = i - 1; j >= 0 && array1[j] > x; j--)
            {
                array1[j + 1] = array1[j];      // сдвигаем элемент направо, пока не дошли
                sravnenie++;
            }
              // место найдено, вставить элемент
            array1[j + 1] = x;
            obmen++;
        }
 
        /*for (int i = 0; i < size1; i++)
        {
            cout << array1[i] << " ";
 
        }*/
        cout << "Количество сравнений (1000 элементов): " << sravnenie << endl;
        cout << "Количество обменов (1000 элементов): " << obmen << endl;
        cout << endl;
    }
 
 
 
 
    system("pause");
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.12.2018, 20:29
Ответы с готовыми решениями:

Количество обменов при сортировке пузырьком
Проблема с выводом. Помогите найти, где напортачил. public static void main(String args) {...

Количество обменов при сортировке пузырьком
Как определить количество обменов сортировки пузырьком по возрастанию? Входные данные На первой...

Доработать код, нужно посчитать объем конуса и найти ошибку в сортировке
Здравствуйте. Помогите дописать код, нужно посчитать объем конуса и найти ошибку в сортировке. Буду...

Как посчитать количество обменов и сравнений при сортировке слиянием?
Дан массив: 33 66 82 85 15 17 74 слияние происходит насколько я погимаю так: 66 33 85 82 17 15 74...

7
7167 / 6142 / 2802
Регистрация: 14.04.2014
Сообщений: 26,462
05.12.2018, 21:07 2
Это же уже есть.
0
14 / 10 / 4
Регистрация: 10.09.2018
Сообщений: 373
05.12.2018, 21:24  [ТС] 3
Цитата Сообщение от nmcf Посмотреть сообщение
Это же уже есть.
Оно выводит количество элемент в массиве. Я решил что это не правильно
0
7167 / 6142 / 2802
Регистрация: 14.04.2014
Сообщений: 26,462
05.12.2018, 22:29 4
Может, надо ещё и сдвиги учитывать?
0
14 / 10 / 4
Регистрация: 10.09.2018
Сообщений: 373
05.12.2018, 22:39  [ТС] 5
Цитата Сообщение от nmcf Посмотреть сообщение
Может, надо ещё и сдвиги учитывать?
Думаю нет, потому что будет очень большое число. Вы хотите сказать что всё работает правильно?
0
7167 / 6142 / 2802
Регистрация: 14.04.2014
Сообщений: 26,462
05.12.2018, 23:10 6
Обычно учитывают сравнения и перестановки.
Ну если тебе не надо, оставь так.
0
14 / 10 / 4
Регистрация: 10.09.2018
Сообщений: 373
05.12.2018, 23:13  [ТС] 7
Цитата Сообщение от nmcf Посмотреть сообщение
Обычно учитывают сравнения и перестановки.
Как подсчитать перестановку? Может это и имеется в веду.
0
1886 / 873 / 412
Регистрация: 17.11.2018
Сообщений: 2,271
05.12.2018, 23:47 8
Лучший ответ Сообщение было отмечено DragonBorn88 как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
        // поиск места элемента в готовой последовательности 
        int i , j ;
        for ( i = 1 ; i < size1 ; i ++ )           // цикл проходов, i - номер прохода
        {           
            int x     = array1 [ i ] ;
            int flag  = false ;
 
            // поиск места элемента в готовой последовательности            
            for ( j = i - 1 ; j >= 0 && array1 [ j ] > x ; j-- )
            {
                array1 [ j + 1 ] = array1 [ j ] ; // сдвигаем элемент направо, пока не дошли
                sravnenie ++ ;                  
                obmen  ++ ;
                flag  = true ;
            }
 
            if ( !flag )
                sravnenie ++ ;
            array1 [j + 1] = x ;                  // место найдено, вставить элемент
        }
вроде бы так должно быть. Ты возьми маленький массив из двух, потом из трёх , четырёх чисел, выводи на экран и ты увидишь. Только меняй значения в массиве, запусти рандомайзер...
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.12.2018, 23:47
Помогаю со студенческими работами здесь

Количество сравнений и обменов при сортировке матрицы разными способами
Необходимо создать однородную таблицу. Затем применить три метода сортировки: Бинарным включением,...

Как теоретически (не программно) посчитать количество сравнений и обменов в пузырьковой сортировке?
как теоретически посчитать количество сравнений и обменов в пузырьковой сортировке?не программно

Вставить счётчик обменов при сортировке массива
Программа для сортировки массива методом простого включения, нужно вставить счётчики для подсчёта...

Сортировке Шейкера (подсчет количества сравнений и обменов)
Здравствуйте, пожалуйста, помогите исправить ошибку в сортировке Шейкера (подсчет количества...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru