Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.89/18: Рейтинг темы: голосов - 18, средняя оценка - 4.89
0 / 0 / 0
Регистрация: 17.09.2012
Сообщений: 48
1

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

12.12.2012, 02:44. Показов 3365. Ответов 8
Метки нет (Все метки)

Доброго времени суток! у меня такая задача... прочитать массив из файла и отсортировать его по возрастанию. Все значения целые и по модулю не превосходят 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;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.12.2012, 02:44
Ответы с готовыми решениями:

Прочитать массив из файла, отсортировать по возрастанию чётные элементы
Записать в один файл массив, содержащий 20 случайных чисел от -10 до 10. Прочитать массив из файла,...

Прочитать из файла массив отсортировать его и записать в другой
Добрый вечер:) Уважаемые форумчане, помогите новичку. Задание: Прочитать из файла массив...

Прочитать из файла « File 1. dat » данные в массив символов, отсортировать данный массив по возрастанию и записать результат в « File 2. dat »
Напишите программы на Паскале! 1. Используя ввод с клавиатуры создать файл « File 1. dat » ,...

Прочитать из текстового файла слова, отсортировать буквы по возрастанию
Ребят не могу понять в чем ошибка..... Суть задачи: Нужно прочитать из текстового файла слова,...

8
419 / 418 / 167
Регистрация: 28.11.2010
Сообщений: 1,183
12.12.2012, 02:54 2
1. Вы не вводите размер массива, вернее у вас размер первое число из файла
C++
1
f>>n;
2. Вам нужен цикл while (!f.eof()) {тут читаем массив}, тут же можно посчитать количество чисел и потом создать массив.
3. Зачем 2 раза создавать массив на 100000 элементов?
4. Ну и файл input.txt создать не мешало б.
1
Форумчанин
Эксперт CЭксперт С++
8165 / 5013 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
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, " "));
}
1
0 / 0 / 0
Регистрация: 17.09.2012
Сообщений: 48
12.12.2012, 03:32  [ТС] 4
vua72, так у меня есть файл input.txt и из него все нормально читается, только при выводе в output.txt эти числа не сортируются

Добавлено через 3 минуты
MrGluck, спасибо большое)) эмм.. а это можно как-нибудь ускорить? просто элементы массива должны перебираться не более, чем за 1 сек
0
Форумчанин
Эксперт CЭксперт С++
8165 / 5013 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
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, " "));
}
1
0 / 0 / 0
Регистрация: 17.09.2012
Сообщений: 48
12.12.2012, 03:38  [ТС] 6
MrGluck, а можете исправить в моем коде ошибки? там что-то неправильно работает, а я не могу понять что именно
0
Форумчанин
Эксперт CЭксперт С++
8165 / 5013 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
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;
}
1
0 / 0 / 0
Регистрация: 17.09.2012
Сообщений: 48
12.12.2012, 03:55  [ТС] 8
MrGluck, огромное спасибо!! Вы мне очень помогли)))
0
Форумчанин
Эксперт CЭксперт С++
8165 / 5013 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
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 секунды
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.12.2012, 04:07

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Прочитать матрицу из файла, отсортировать по возрастанию элементов строк и вывести
Записать в файл произвольную матрицу, прочитать полученный файл и вывести матрицу, отсортированную...

Прочитать из файла числа, отсортировать их по возрастанию, результат записать в другой файл
Прочитать из файла числа, отсортировать их по возрастанию, результат записать в другой файл.

Дан массив.Отсортировать его по возрастанию
Помогите решить эту задачку

Прочитать из файла массив, отсортировать, результат вывести на экран.
Разработать приложение, выполняющее следующие функции. Прочитать из файла массив строк символов....


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

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