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

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

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

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

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

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

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

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

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

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

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

Найти количество отрицательных чисел, количество нулевых и подсчитать сумму положительных чисел - C++
Т.к. я полный 0 в этом, вынужден обратиться к профи) надеюсь на вашу помощь. 1. Произвести следующую обработку 15 целых чисел: найти...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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
1140 / 857 / 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
1140 / 857 / 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
1140 / 857 / 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
1140 / 857 / 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
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
04.04.2012, 11:58 #12
А чем unsigned long long int плох?
Ну или std::uint64_t...
Правда оба с нового стандарта, но long long давно уже многими компиляторами поддерживается.
Toshkarik
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
04.04.2012, 15:08 #13
diagon, поддерживается как свое расширение а не как стандарт, при компиляции в последнем GCC например c вышеуказанными опциями, нужно указывать флаг -std=c++11 чтоб включить поддержку нового стандарта, которая еще находится на стадии разработки, иначе ошибка при компиляции. Так же вроде и в VS10, если в проекте отключить расширения компилятора не входящие в стандарт, то long long в С++ так же будет не доступным.
diagon
Higher
1929 / 1195 / 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
1140 / 857 / 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 был и в более ранних версиях, но, повторюсь, как свое расширения, а не из стандарта.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2012, 15:46
Привет! Вот еще темы с ответами:

Для чисел от -50 до 50 найти количество четных отрицательных и количество положительных нечетных чисел - C++
Ребят,всем привет! Помогите пожалуйста решить данную задачу.Ее нужно написать на я зыке C /C++,каждую из них с постусловием и...

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

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
04.04.2012, 15:46
Ответ Создать тему
Опции темы

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