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

прочитать массив из файла и отсортировать его по возрастанию - C++

Восстановить пароль Регистрация
 
_Tanechka_
0 / 0 / 0
Регистрация: 17.09.2012
Сообщений: 48
12.12.2012, 02:44     прочитать массив из файла и отсортировать его по возрастанию #1
Доброго времени суток! у меня такая задача... прочитать массив из файла и отсортировать его по возрастанию. Все значения целые и по модулю не превосходят 2147483647. Количество чисел в массиве не превышает 100000. время на тест 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <fstream>
using namespace std;
 
int mas[100000];
 
void quickSort(int l, int r)
{
    int x = mas[l+(r-l)/2];
    int i = l;
    int j = r;
    while(i<=j)
    {
        while(mas[i]<x) i++;
        while(mas[j]>x) j--;
        if(i<=j)
        {
            swap(mas[i],mas[j]);
            i++;
            j--;
        }
    }
    if(i<r)
        quickSort(i,r);
    if(l<j)
        quickSort(l,j);
}
 
int main()
{
    int n;
    int * array;
    array = new int[100000];
 
    fstream f;
    f.open("input.txt", ios::in);
    f>>n;
    for(int i = 0; i<n; i++)
    {
        f>>array[i];
    }
    f.close();
    
    quickSort(0,n-1);
 
    f.open("output.txt",ios::out);
    for(int i =0; i<n; i++)
    {
        f<<array[i]<<" ";
    }
    f.close();
 
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.12.2012, 02:44     прочитать массив из файла и отсортировать его по возрастанию
Посмотрите здесь:

Прочитать из файла массив, отсортировать, результат вывести на экран. C++
Cгенерировать одномерный массив из 10 чисел,отсортировать его по возрастанию или убыванию C++
Получить из исходного массив положительных чисел и отсортировать его по возрастанию методом пузырька C++
C++ Переписать все элементы з матрицы С в одномерный массив F, отсортировать его по возрастанию
C++ 2)Дан массив из N целых чисел. Получить из него массив отрицательных чисел и отсортировать его по возрастанию методом выбора
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
vua72
410 / 410 / 83
Регистрация: 28.11.2010
Сообщений: 1,158
12.12.2012, 02:54     прочитать массив из файла и отсортировать его по возрастанию #2
1. Вы не вводите размер массива, вернее у вас размер первое число из файла
C++
1
f>>n;
2. Вам нужен цикл while (!f.eof()) {тут читаем массив}, тут же можно посчитать количество чисел и потом создать массив.
3. Зачем 2 раза создавать массив на 100000 элементов?
4. Ну и файл input.txt создать не мешало б.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
12.12.2012, 02:59     прочитать массив из файла и отсортировать его по возрастанию #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iterator>
#include <set>
 
 
int main()
{
    std::ifstream ifs("input.txt");
    if(!ifs) return 1;
    std::multiset<int> s((std::istream_iterator<int>(ifs)), std::istream_iterator<int>());
    std::copy(s.begin(), s.end(), std::ostream_iterator<int> (std::cout, " "));
}
_Tanechka_
0 / 0 / 0
Регистрация: 17.09.2012
Сообщений: 48
12.12.2012, 03:32  [ТС]     прочитать массив из файла и отсортировать его по возрастанию #4
vua72, так у меня есть файл input.txt и из него все нормально читается, только при выводе в output.txt эти числа не сортируются

Добавлено через 3 минуты
MrGluck, спасибо большое)) эмм.. а это можно как-нибудь ускорить? просто элементы массива должны перебираться не более, чем за 1 сек
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
12.12.2012, 03:36     прочитать массив из файла и отсортировать его по возрастанию #5
_Tanechka_, это итак самый быстрый алгоритм, и у меня 10 чисел считывает и сортирует за 0.006 секунд.

Добавлено через 2 минуты
С выводом в файл:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <fstream>
#include <algorithm>
#include <iterator>
#include <set>
 
 
int main()
{
    std::ifstream ifs("input.txt");
    std::ofstream o("output.txt");
    if(!ifs) return 1;
    std::multiset<int> s((std::istream_iterator<int>(ifs)), std::istream_iterator<int>());
    std::copy(s.begin(), s.end(), std::ostream_iterator<int> (o, " "));
}
_Tanechka_
0 / 0 / 0
Регистрация: 17.09.2012
Сообщений: 48
12.12.2012, 03:38  [ТС]     прочитать массив из файла и отсортировать его по возрастанию #6
MrGluck, а можете исправить в моем коде ошибки? там что-то неправильно работает, а я не могу понять что именно
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
12.12.2012, 03:48     прочитать массив из файла и отсортировать его по возрастанию #7
_Tanechka_,
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
52
53
54
#include <fstream>
#include <algorithm>
using namespace std;
 
 
void quickSort(int *mas, int l, int r)
{
    int x = mas[l+(r-l)/2];
    int i = l;
    int j = r;
    while(i<=j)
    {
        while(mas[i]<x) i++;
        while(mas[j]>x) j--;
        if(i<=j)
        {
            swap(mas[i],mas[j]);
            i++;
            j--;
        }
    }
    if(i<r)
        quickSort(mas, i,r);
    if(l<j)
        quickSort(mas, l,j);
}
 
int main()
{
    int n;
    int *array;
 
    fstream f;
    f.open("input.txt", ios::in);
    f>>n;
    array = new int[n];
    for(int i = 0; i<n; i++)
    {
        f>>array[i];
    }
    f.close();
 
    quickSort(array, 0, n-1);
 
    f.open("output.txt",ios::out);
    for(int i =0; i<n; i++)
    {
        f<<array[i]<<" ";
    }
    f.close();
    delete []array;
 
    return 0;
}
_Tanechka_
0 / 0 / 0
Регистрация: 17.09.2012
Сообщений: 48
12.12.2012, 03:55  [ТС]     прочитать массив из файла и отсортировать его по возрастанию #8
MrGluck, огромное спасибо!! Вы мне очень помогли)))
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.12.2012, 04:07     прочитать массив из файла и отсортировать его по возрастанию
Еще ссылки по теме:

C++ 2)Дан массив из N целых чисел. Получить из него массив отрицательных чисел и отсортировать его по возрастанию методом выбора
C++ С++ Отсортировать целочисленный массив по возрастанию суммы двух последних цифр в записи его элементов
C++ Заполнить массив размером 10 случайными числами от 0 до 10, отсортировать его по возрастанию

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

Или воспользуйтесь поиском по форуму:
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
12.12.2012, 04:07     прочитать массив из файла и отсортировать его по возрастанию #9
Сейчас сравнил по времени алгоритмы на 100000 элементах с максимальным разбросом значений:
1) с set
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <fstream>
#include <algorithm>
#include <iterator>
#include <set>
 
 
int main()
{
    std::ifstream ifs("input.txt");
    std::ofstream o("output.txt");
    if(!ifs) return 1;
    std::multiset<int> s((std::istream_iterator<int>(ifs)), std::istream_iterator<int>());
    std::copy(s.begin(), s.end(), std::ostream_iterator<int> (o, " "));
}

2) с vector и std::sort
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <fstream>
#include <algorithm>
#include <iterator>
#include <vector>
 
int main()
{
    std::ifstream ifs("input.txt");
    std::ofstream o("output.txt");
    int x, tmp;
    if(!ifs) return 1;
    ifs >> x;
    std::vector<int> v(x);
    for (int i=0; i < x && ifs >> tmp; i++)
        v.push_back(tmp);
    std::sort(v.begin(), v.begin() + x);
    std::copy(v.begin(), v.begin() + x, std::ostream_iterator<int> (o, " "));
}

3) ваш вариант с массивами
Кликните здесь для просмотра всего текста
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
52
53
54
#include <fstream>
#include <algorithm>
using namespace std;
 
 
void quickSort(int *mas, int l, int r)
{
    int x = mas[l+(r-l)/2];
    int i = l;
    int j = r;
    while(i<=j)
    {
        while(mas[i]<x) i++;
        while(mas[j]>x) j--;
        if(i<=j)
        {
            swap(mas[i],mas[j]);
            i++;
            j--;
        }
    }
    if(i<r)
        quickSort(mas, i,r);
    if(l<j)
        quickSort(mas, l,j);
}
 
int main()
{
    int n;
    int *array;
 
    fstream f;
    f.open("input.txt", ios::in);
    f>>n;
    array = new int[n];
    for(int i = 0; i<n; i++)
    {
        f>>array[i];
    }
    f.close();
 
    quickSort(array, 0, n-1);
 
    f.open("output.txt",ios::out);
    for(int i =0; i<n; i++)
    {
        f<<array[i]<<" ";
    }
    f.close();
    delete []array;
 
    return 0;
}

по времени с std::set 0.2 секунды, с std::vector 0.12, с массивом 0.122 секунды
Yandex
Объявления
12.12.2012, 04:07     прочитать массив из файла и отсортировать его по возрастанию
Ответ Создать тему
Опции темы

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