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

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

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

C++ В массиве найти количество нечетных чисел расположенных после второго самого большого числа
Генерация большого количества случайных чисел C++
C++ Дано целое число N и набор из N целых чисел. Определить номера тех чисел наборе, которые меньше своего правого соседа, и количество К таких чисел.
C++ Сортировка очень большого файла.
Двумерный массив рациональных чисел + среднее арифметическое чисел массива + сортировка методом вставки 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
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 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
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 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
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 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
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 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
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
04.04.2012, 11:58     сортировка большого количество чисел #12
А чем unsigned long long int плох?
Ну или std::uint64_t...
Правда оба с нового стандарта, но long long давно уже многими компиляторами поддерживается.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
04.04.2012, 15:08     сортировка большого количество чисел #13
diagon, поддерживается как свое расширение а не как стандарт, при компиляции в последнем GCC например c вышеуказанными опциями, нужно указывать флаг -std=c++11 чтоб включить поддержку нового стандарта, которая еще находится на стадии разработки, иначе ошибка при компиляции. Так же вроде и в VS10, если в проекте отключить расширения компилятора не входящие в стандарт, то long long в С++ так же будет не доступным.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
04.04.2012, 15:46     сортировка большого количество чисел #15
Цитата Сообщение от diagon Посмотреть сообщение
Ну да, можно просто не писать -pedantic-errors, вы не задумывались о таком решении?
Нет не задумывался, потому что мне не нужны нестандартные расширения.
Цитата Сообщение от diagon Посмотреть сообщение
Сам стандарт уже давно есть.
Его утвердили относительно недавно.

Цитата Сообщение от diagon Посмотреть сообщение
А long long есть даже в моей версии gcc(4.6.1),
long long был и в более ранних версиях, но, повторюсь, как свое расширения, а не из стандарта.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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++ Консольный вывод большого кол-ва чисел
C++ Сортировка большого одномерного массива
Определить в последовательности количество чисел кратных трем, и количество чисел, кратных семи C++

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

Или воспользуйтесь поиском по форуму:
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 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     сортировка большого количество чисел
Ответ Создать тему
Опции темы

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