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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Plazma
5 / 5 / 0
Регистрация: 20.11.2010
Сообщений: 51
#1

сортировка большого количество чисел - C++

03.04.2012, 20:42. Просмотров 873. Ответов 16
Метки нет (Все метки)

Здравствуйте! Хотел посчитать количество перестановок при сортировке с слиянием, но не ожиданное столкнулся с такой проблемой, при сортировке 100000 и более чисел программа показывает что сделано отрицательное количество перестановок, помогите разобраться с этой проблемой,
например при сортировке 100000 чисел вышло что сделано -1797893816 перестановок.....
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.04.2012, 20:42     сортировка большого количество чисел
Посмотрите здесь:

В массиве найти количество нечетных чисел расположенных после второго самого большого числа - C++
Помогите пожалуйста составить программу и если не затруднит еще блок-схему В массиве A10 найти количество нечетных чисел расположенных...

Сортировка очень большого файла. - C++
вопрос таков: есть очень большой файл, его нужно отсортировать. Так как файл большой его нужно извлекать по частям. Как это можно...

Сортировка большого одномерного массива - C++
Вот что у меня получилось. Сортировка по возростанию массива со случайными элементами. Так работает нормально, но мне нужно чтобы массив...

Консольный вывод большого кол-ва чисел - C++
У меня задание написать программу, которая вычисляла бы простые числа до миллиона и выводила в консоль. Программа работает, но я не могу...

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

Вывести все одноразрядные натуральные делители произвольного большого числа (количество цифр меньше 15) - C++
Реализовать программу, которая выводит все одноразрядные натуральные делители произвольного большого числа (количество цифр которого меньше...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
antoha398
155 / 155 / 3
Регистрация: 29.03.2012
Сообщений: 418
03.04.2012, 20:46     сортировка большого количество чисел #2
код программы дайте!
Какой используете тип для переменной подсчета перестановок ?
Plazma
5 / 5 / 0
Регистрация: 20.11.2010
Сообщений: 51
03.04.2012, 20:51  [ТС]     сортировка большого количество чисел #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
26
27
28
29
30
31
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <fstream>
 
using namespace std;
 
int main()
{
    ifstream f("100000_v1_notsorted.txt", std::ios_base::in);
    vector<int> arr;
 
    istream_iterator<int> begin(f);
    istream_iterator<int> end;
 
    copy (begin, end, back_inserter(arr));
     int tmp;
    int count=0;
    for (int i = 1, j; i < 100000; ++i) // цикл проходов, i - номер прохода
    {
        tmp = arr[i];
          for (j = i - 1; j >= 0 && arr[j] > tmp; --j){ // поиск места элемента в готовой последовательности
           count++; 
              arr[j + 1] = arr[j];}    // сдвигаем элемент направо, пока не дошли
              arr[j + 1] = tmp; // место найдено, вставить элемент    
    }
    cout<<count<<"\n"<<endl;
         
system("pause");
return 0;}
Добавлено через 2 минуты
Ой извините, не сортировка с слиянием, а со вставками(insertion).
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
03.04.2012, 20:53     сортировка большого количество чисел #4
Попробуйте объявить count как unsigned long int, скорей всего просто число перестановок не помещается в знаковую целочисленную переменную, и происходит переполнение. Возможно даже не поместится и в беззнаковую.
Plazma
5 / 5 / 0
Регистрация: 20.11.2010
Сообщений: 51
03.04.2012, 21:00  [ТС]     сортировка большого количество чисел #5
Спасибо, попробую, но о результате сообщу только через 2 часа, аж очень долго над ждать пока прога отсортирует все числа..
antoha398
155 / 155 / 3
Регистрация: 29.03.2012
Сообщений: 418
03.04.2012, 21:01     сортировка большого количество чисел #6
Цитата Сообщение от Toshkarik Посмотреть сообщение
Попробуйте объявить count как unsigned long int, скорей всего просто число перестановок не помещается в знаковую целочисленную переменную, и происходит переполнение. Возможно даже не поместится и в беззнаковую.
или size_t можно попробовать.
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
03.04.2012, 21:20     сортировка большого количество чисел #7
size_t на большинстве 32 битных системах эквивалентен unsigned long int ( то есть 4 байтам ).
Plazma
5 / 5 / 0
Регистрация: 20.11.2010
Сообщений: 51
03.04.2012, 21:36  [ТС]     сортировка большого количество чисел #8
Получилось, что касается типа, то лучше использовать size_t, потому что у меня 64 битная система и я собираюсь отсортировать еще больше чисел
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
03.04.2012, 21:42     сортировка большого количество чисел #9
И компилируется программа как 64 битная? Тогда да, size_t в этом случае будет равен 8 байтам.
antoha398
155 / 155 / 3
Регистрация: 29.03.2012
Сообщений: 418
03.04.2012, 21:58     сортировка большого количество чисел #10
Цитата Сообщение от Toshkarik Посмотреть сообщение
size_t на большинстве 32 битных системах эквивалентен unsigned long int ( то есть 4 байтам ).
попробовал собрать под 64 битную. У меня получилось, что они тоже равны)
Вот:
toha@tux ~ $ g++ -m32 ./sizeof.cpp
toha@tux ~ $ ./a.out
sizeof(int) = 4
sizeof(unsigned losg int) = 4
sizeof(size_t) = 4
toha@tux ~ $ g++ -m64 ./sizeof.cpp
toha@tux ~ $ ./a.out
sizeof(int) = 4
sizeof(unsigned losg int) = 8
sizeof(size_t) = 8

получается нет разницы чем пользовать, если только size_t короче выглядит.
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
03.04.2012, 22:26     сортировка большого количество чисел #11
64 битные целые в С++ появились только в новом стандарте, который еще не все компиляторы поддерживают. Даже в последнем gcc 4.7.0 его поддержку нужно указывать в ручную в качестве параметра. Возможно ваш gcc использует свое расширение для представления 64 битных целых, которое не входит в стандарт. Вот что я получаю с кодом
C++
1
2
3
4
5
6
7
8
9
10
#include <iostream>
 
/*
 *
 */
int main() {
    std::cout << sizeof( unsigned long int ) << '\n' << sizeof( std::size_t ) << std::endl;
 
    return 0;
}
и параметрами компиляции -m64 -Wall -Wextra -Werror -ansi -pedantic-errors на GCC 4.7.0:
Миниатюры
сортировка большого количество чисел  
diagon
Higher
1926 / 1192 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
04.04.2012, 11:58     сортировка большого количество чисел #12
А чем unsigned long long int плох?
Ну или std::uint64_t...
Правда оба с нового стандарта, но long long давно уже многими компиляторами поддерживается.
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
04.04.2012, 15:08     сортировка большого количество чисел #13
diagon, поддерживается как свое расширение а не как стандарт, при компиляции в последнем GCC например c вышеуказанными опциями, нужно указывать флаг -std=c++11 чтоб включить поддержку нового стандарта, которая еще находится на стадии разработки, иначе ошибка при компиляции. Так же вроде и в VS10, если в проекте отключить расширения компилятора не входящие в стандарт, то long long в С++ так же будет не доступным.
diagon
Higher
1926 / 1192 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
04.04.2012, 15:27     сортировка большого количество чисел #14
Цитата Сообщение от Toshkarik Посмотреть сообщение
diagon, поддерживается как свое расширение а не как стандарт
Ну да, можно просто не писать -pedantic-errors, вы не задумывались о таком решении?

Цитата Сообщение от Toshkarik Посмотреть сообщение
поддержку нового стандарта, которая еще находится на стадии разработки
В каком смысле? Сам стандарт уже давно есть. Поддержка в gcc пока не полная, но пробелы, в основном, с многопоточностью связаны. А long long есть даже в моей версии gcc(4.6.1), которой уже более полугода.
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
04.04.2012, 15:46     сортировка большого количество чисел #15
Цитата Сообщение от diagon Посмотреть сообщение
Ну да, можно просто не писать -pedantic-errors, вы не задумывались о таком решении?
Нет не задумывался, потому что мне не нужны нестандартные расширения.
Цитата Сообщение от diagon Посмотреть сообщение
Сам стандарт уже давно есть.
Его утвердили относительно недавно.

Цитата Сообщение от diagon Посмотреть сообщение
А long long есть даже в моей версии gcc(4.6.1),
long long был и в более ранних версиях, но, повторюсь, как свое расширения, а не из стандарта.
diagon
Higher
1926 / 1192 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
04.04.2012, 15:56     сортировка большого количество чисел #16
Цитата Сообщение от Toshkarik Посмотреть сообщение
Нет не задумывался, потому что мне не нужны нестандартные расширения.
В случае c long long на это можно закрыть глаза, но это ваше право.

Цитата Сообщение от Toshkarik Посмотреть сообщение
Его утвердили относительно недавно.
В августе еще.

Цитата Сообщение от Toshkarik Посмотреть сообщение
ong long был и в более ранних версиях, но, повторюсь, как свое расширения, а не из стандарта.
А я про новый стандарт говорил, поддержка long long в нем достаточно стабильно реализована, бояться нечего.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2012, 16:03     сортировка большого количество чисел
Еще ссылки по теме:

Определить в последовательности количество чисел кратных трем, и количество чисел, кратных семи - C++
Дано натуральное число n и целые числа x1 ,x2, … xn. Определить количество чисел xi кратных трем, и количество чисел xi кратных семи.

Найти количество двух- и количество трехразрядных чисел в заданной последовательности - C++
Помогите,пожалуйста, написать программу. Вводится последовательность из Nцелых чисел. Найти количество двух-и количество трехразрядных...

Найти количество двух- и количество трехразрядных чисел в последовательности - C++
Вводится последовательность из N целых чисел. Найти количество двух и количество трех разрядных чисел в последовательности (функцией...

Написать функцию, которая возвращает количество нечётных чисел и чисел, делящихся на 5 - C++
Задание 1:Написать функцию, которая принимает массив чисел, а возвращает количество нечётных чисел и чисел, делящихся на 5. Объявить...


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

Или воспользуйтесь поиском по форуму:
Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
04.04.2012, 16:03     сортировка большого количество чисел #17
Цитата Сообщение от diagon Посмотреть сообщение
В августе еще.

Не по теме:

Ну я думаю это относительно не так давно, если учитывать, что предыдущий был утвержден аж 13 лет назад


Цитата Сообщение от diagon Посмотреть сообщение
поддержка long long в нем достаточно стабильно реализована
В том то и дело, что даже если без pedantic-errors не указать -std=c++11, то поддержки нового стандарта не будет, и long long будет в данном случае как расширение
Yandex
Объявления
04.04.2012, 16:03     сортировка большого количество чисел
Ответ Создать тему
Опции темы

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