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

Подсчитать Количество перестановок при сортировке массива по возрастанию - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
24.05.2014, 21:35     Подсчитать Количество перестановок при сортировке массива по возрастанию #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
#include <stdio.h>
#include <conio.h>
 
int main()
{
    int n,s=0,i,k,j;
    scanf("%d",&n);
 
    int *a = new int[n];
    for(i = 0;i < n;i++)
        scanf("%d",a[i]);
 
    for(i = 0;i < n - 1;i++){
        for(j = i + 1; j < n;j++){
        if(a[i] > a[j+1]){
            k = a[i];
            a[i] = a[j+1];
            a[j+1] = k;
            s++;
        }
        }
    }
    printf("%d", s);
 
    getch();
 
    return 0;
}
Но когда я ввожу первый элемент массива, выдает ошибку "Необработанное исключение". Где я ошибся?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.05.2014, 21:35     Подсчитать Количество перестановок при сортировке массива по возрастанию
Посмотрите здесь:

C++ Использование массива индексов при сортировке
В упорядоченном по возрастанию массиве подсчитать количество элементов C++
C++ Выполнить сортировку массива по убыванию и проконтролировать ее результат. Произвести подсчет перестановок при сортировке
Выполнить сортировку массива по убыванию и проконтролировать ее результат. Произвести подсчет перестановок при сортировке C++
C++ Сортировка слиянием: подсчитать количество перестановок
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zss
Модератор
Эксперт С++
 Аватар для zss
5942 / 5547 / 1783
Регистрация: 18.12.2011
Сообщений: 14,164
Завершенные тесты: 1
24.05.2014, 21:55     Подсчитать Количество перестановок при сортировке массива по возрастанию #2
Цитата Сообщение от Sh@dow777 Посмотреть сообщение
scanf("%d",a[i])
Надо передавать адрес переменной a[i]
C++
1
scanf("%d",&a[i]);
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
24.05.2014, 22:01  [ТС]     Подсчитать Количество перестановок при сортировке массива по возрастанию #3
zss, Спасибо. Буду знать.
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
24.05.2014, 22:17  [ТС]     Подсчитать Количество перестановок при сортировке массива по возрастанию #4
zss, Теперь я проверяю результат. Вроде все верно. Но система проверки выдает ошибку на тесте 1. В чем проблема?
Вот сама задача.
Миниатюры
Подсчитать Количество перестановок при сортировке массива по возрастанию  
Genn55
341 / 188 / 37
Регистрация: 26.12.2012
Сообщений: 658
24.05.2014, 23:03     Подсчитать Количество перестановок при сортировке массива по возрастанию #5
C++
1
2
3
4
5
6
7
8
9
10
11
for(i = 1;i < n;i++)
    {
        for(j = 0; j < n - 1;j++){
        if(a[j] > a[j+1]){
            k = a[j];
            a[j] = a[j+1];
            a[j+1] = k;
            s++;
        }
        }
    }
Сортировка пузырьком.
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
24.05.2014, 23:13  [ТС]     Подсчитать Количество перестановок при сортировке массива по возрастанию #6
Genn55, теперь на 21 тесте выдает "Превышено максимальное время работы".
Genn55
341 / 188 / 37
Регистрация: 26.12.2012
Сообщений: 658
24.05.2014, 23:33     Подсчитать Количество перестановок при сортировке массива по возрастанию #7
Я указал ошибку в вашем коде.И у вас не освобождается память.
C++
1
delete [] a;
Добавлено через 10 минут
Вот похожее делал.Код рабочий.Возможно вам поможет.
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
//подсчет перестановок
#include <iostream>
 
 
void printArray(int*, int); //прототип функции для вывода массива на печать
void bubbleSort(int*, int); //прототип
using namespace std;
int main()
{
const int size = 25;
int array[size] = {10,56,15,100,78,
45,91,12,1,4,
7,8,533,47,2,
21,3,67,68,79,
73,27,93,22,0};
 
cout << " No sorted a array" << "\n\n";
printArray(array, size);
bubbleSort (array, size);
cout << " The sorted a array" <<"\n\n";
printArray(array, size);
return 0;
}
void printArray(int *arr, int sizeOfArray) //печать массива
{
for (int k = 0; k < sizeOfArray; k++)
 
cout << arr[k]<<" ";
 
cout <<"\n\n";
}
void bubbleSort(int* arr, int sizeOfArray)
{
    int countswap=0; //счетчик обменов
    int countcompare=0; //счетчик сравнений
for(int i = 1; i < sizeOfArray; i++) // i - номер прохода
for(int j = 0; j < sizeOfArray - 1;j++) // внутренний цикл прохода
{
countcompare++;
if (arr[j ] < arr[j +1])
{
 int tmp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tmp;
countswap++;
}
}
cout<<"countcompare:  "<<countcompare <<"\n";
cout<<"countswap:  "<<countswap <<"\n";
cout <<"\n\n";
}
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
25.05.2014, 12:52  [ТС]     Подсчитать Количество перестановок при сортировке массива по возрастанию #8
Genn55, Если я вас правильно понял, то нужно сделать так?
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
#include <stdio.h>
 
int main()
{
    int n,i,k,j;
    int s = 0;
 
    scanf("%d",&n);
 
    int *a = new int[n];
    for(i = 0;i < n;i++)
        scanf("%d", &a[i]);
 
    for(i = 1;i < n;i++){
        for(j = 0; j < n - 1;j++){
        if(a[j] > a[j+1]){
            k = a[j];
            a[j] = a[j+1];
            a[j+1] = k;
            s++;
        }
        }
    }
    printf("%d", s);
 
    delete[] a;
 
    return 0;
}
Но все равно выдает "Превышено максимальное время работы" на 21 тесте.

Добавлено через 1 час 54 минуты
Может быть мне стоит попробовать другой алгоритм? Но в условии задачи четко написано, что при сортировке меняются местами соседние элементы.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.05.2014, 16:43     Подсчитать Количество перестановок при сортировке массива по возрастанию
Еще ссылки по теме:

Как подсчитать произведенное количество перестановок при быстрой сортировке? C++
Как найти в этой сортировке количество перестановок и сравнений? C++
Как найти в данной сортировке количество перестановок и сравнений? C++

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

Или воспользуйтесь поиском по форуму:
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
27.05.2014, 16:43  [ТС]     Подсчитать Количество перестановок при сортировке массива по возрастанию #9
Подниму тему. Скажите, в чем проблема? Программа работает, но выдает ошибку на 21 тесте "Превышено максимальное время работы".
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
#include <stdio.h>
 
int main()
{
    int n,i,k,j;
    int s = 0;
 
    scanf("%d",&n);
 
    int *a = new int[n];
    for(i = 0;i < n;i++)
        scanf("%d", &a[i]);
 
    for(i = 1;i < n;i++){
        for(j = 0; j < n - 1;j++){
        if(a[j] > a[j+1]){
            k = a[j];
            a[j] = a[j+1];
            a[j+1] = k;
            s++;
        }
        }
    }
    printf("%d", s);
 
    return 0;
}
Yandex
Объявления
27.05.2014, 16:43     Подсчитать Количество перестановок при сортировке массива по возрастанию
Ответ Создать тему
Опции темы

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