Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.82/11: Рейтинг темы: голосов - 11, средняя оценка - 4.82
5 / 5 / 0
Регистрация: 20.11.2010
Сообщений: 51
1

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

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

Author24 — интернет-сервис помощи студентам
Здравствуйте! Хотел посчитать количество перестановок при сортировке с слиянием, но не ожиданное столкнулся с такой проблемой, при сортировке 100000 и более чисел программа показывает что сделано отрицательное количество перестановок, помогите разобраться с этой проблемой,
например при сортировке 100000 чисел вышло что сделано -1797893816 перестановок.....
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.04.2012, 20:42
Ответы с готовыми решениями:

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

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

Сортировка очень большого файла.
вопрос таков: есть очень большой файл, его нужно отсортировать. Так как файл большой его нужно...

Сортировка включением. Найдите количество чисел равных К
Дан целочисленный массив C(L). Добавить массив X(N). Выполнить сортировку включением. Найдите...

16
157 / 157 / 27
Регистрация: 29.03.2012
Сообщений: 418
03.04.2012, 20:46 2
код программы дайте!
Какой используете тип для переменной подсчета перестановок ?
0
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).
0
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
03.04.2012, 20:53 4
Попробуйте объявить count как unsigned long int, скорей всего просто число перестановок не помещается в знаковую целочисленную переменную, и происходит переполнение. Возможно даже не поместится и в беззнаковую.
1
5 / 5 / 0
Регистрация: 20.11.2010
Сообщений: 51
03.04.2012, 21:00  [ТС] 5
Спасибо, попробую, но о результате сообщу только через 2 часа, аж очень долго над ждать пока прога отсортирует все числа..
0
157 / 157 / 27
Регистрация: 29.03.2012
Сообщений: 418
03.04.2012, 21:01 6
Цитата Сообщение от Toshkarik Посмотреть сообщение
Попробуйте объявить count как unsigned long int, скорей всего просто число перестановок не помещается в знаковую целочисленную переменную, и происходит переполнение. Возможно даже не поместится и в беззнаковую.
или size_t можно попробовать.
1
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
03.04.2012, 21:20 7
size_t на большинстве 32 битных системах эквивалентен unsigned long int ( то есть 4 байтам ).
0
5 / 5 / 0
Регистрация: 20.11.2010
Сообщений: 51
03.04.2012, 21:36  [ТС] 8
Получилось, что касается типа, то лучше использовать size_t, потому что у меня 64 битная система и я собираюсь отсортировать еще больше чисел
0
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
03.04.2012, 21:42 9
И компилируется программа как 64 битная? Тогда да, size_t в этом случае будет равен 8 байтам.
0
157 / 157 / 27
Регистрация: 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 короче выглядит.
0
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
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:
Миниатюры
сортировка большого количество чисел  
0
Higher
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
04.04.2012, 11:58 12
А чем unsigned long long int плох?
Ну или std::uint64_t...
Правда оба с нового стандарта, но long long давно уже многими компиляторами поддерживается.
0
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
04.04.2012, 15:08 13
diagon, поддерживается как свое расширение а не как стандарт, при компиляции в последнем GCC например c вышеуказанными опциями, нужно указывать флаг -std=c++11 чтоб включить поддержку нового стандарта, которая еще находится на стадии разработки, иначе ошибка при компиляции. Так же вроде и в VS10, если в проекте отключить расширения компилятора не входящие в стандарт, то long long в С++ так же будет не доступным.
0
Higher
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
04.04.2012, 15:27 14
Цитата Сообщение от Toshkarik Посмотреть сообщение
diagon, поддерживается как свое расширение а не как стандарт
Ну да, можно просто не писать -pedantic-errors, вы не задумывались о таком решении?

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

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

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

Цитата Сообщение от Toshkarik Посмотреть сообщение
ong long был и в более ранних версиях, но, повторюсь, как свое расширения, а не из стандарта.
А я про новый стандарт говорил, поддержка long long в нем достаточно стабильно реализована, бояться нечего.
0
1181 / 894 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
04.04.2012, 16:03 17
Цитата Сообщение от diagon Посмотреть сообщение
В августе еще.

Не по теме:

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


Цитата Сообщение от diagon Посмотреть сообщение
поддержка long long в нем достаточно стабильно реализована
В том то и дело, что даже если без pedantic-errors не указать -std=c++11, то поддержки нового стандарта не будет, и long long будет в данном случае как расширение
0
04.04.2012, 16:03
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
04.04.2012, 16:03
Помогаю со студенческими работами здесь

Сортировка большого объёма данных
Ребята, очень нужна ваша помощь! Как можно отсортировать большое количество слов в файле (около ~...

Сортировка очень большого текстового файла
Всем привет! Перейду сразу к вопросу. Есть очень большой текстовый файл с какими-то данными,...

Сортировка по размерам от Большого-Малому не работает
&lt;? function SubNavItem($id,$section) { $z=$id; $sql=&quot;SELECT * FROM `catalogLes` WHERE...

Количество итераций, за которое будет выполнена сортировка в заданной последовательности чисел
Требуется написать программу которая будет определять количество итераций за которое будет...


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

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru