Задача по быстрой сортировке

@ОчереднойДжедай · Регистрация: 18.10.2015

Студворк — интернет-сервис помощи студентам

Здравствуйте, товарищи-программисты. Недавно столкнулся с задачей:

Сортировка подсчетом

(Время: 2 сек. Память: 16 Мб Сложность: 29%)
На планете «Аурон» атмосфера практически отсутствует, поэтому она известна своими перепадами температур в различных точках. Известно, что эти перепады колеблются от -100 до 100 градусов. Нашим специалистам удалось выяснить значения температур в N точках этой планеты. К сожалению, эти значения вычислены с большими погрешностями, поэтому их решили округлить до целых чисел. Хотелось бы наглядно видеть участки с повышенной и пониженной температурой. Вам требуется помочь. Вы должны упорядочить температуры участков по неубыванию.

Входные данные

В первой строке входного файла INPUT.TXT задано натуральное число N - количество участков (N ≤ 1000000). Во второй строке через пробел записаны целые значения температур этих участков, не превосходящие 100 по абсолютной величине.

Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести разделенные пробелом значения температур всех известных участков, которые должны следовать друг за другом в порядке неубывания.

Сразу понял, что задача решается обычной быстрой сортировкой. Мое решение этой задачи на Pascal:

Pascal
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
var arr:array [1..1000000] of longint;
    n,i,j,buf,x,m:longint;
procedure QuickSort(m,t:integer);
Begin
 
 i:=m; j:=t; x:=Arr[(m+t) div 2];
  repeat
   while Arr[i]<x do inc(i);
   While Arr[j]>x do Dec(j);
   if i<=j then
    begin
 
     buf:=Arr[i]; Arr[i]:=Arr[j]; Arr[j]:=buf;
     Inc(i); Dec(j);
 
    end;
  until i>j;
  if m<j then QuickSort(m,j);
  if i<t then QuickSort(i,t);
 
End;
 
begin
 
 Assign(Input,'INPUT.TXT');
 Reset(Input);
 Assign(Output,'OUTPUT.TXT');
 Rewrite(Output);
 
 read(n);
 
 for i:=1 to n do
 read(arr[i]);
 
 QuickSort(1,n);
 
    for i:=1 to n do
    write(arr[i],' ');
 
 Close(Input);
 Close(Output);
 
end.

Мое решение пошло отлично, прошло все 10 тестов и набрало 100 баллов. Но поскольку я параллельно изучаю С++ и C#, то решил написать решение этой задачи на этих языках. Думал - легко, но вот что получилось:
Код на С++:

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
55
56
57
58
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <conio.h>
using namespace std;
  
class Program
{
public:
    long int arr[100000];
  
    void QuickSort(int m, int t)
    {
        int i,j,x,w;
        i = m;
        j = t;
        x = arr[ (int)((m+t) / 2)];
  
          
          while (arr[i]<x) i++;
          while (arr[j]>x) j--;
  
          if (i<=j) 
          {
            w = arr[i]; arr[i] = arr[j]; arr[j] = w;
            i++; j--;
          }
  
         if (m<j) QuickSort(m,j);
         if (i<t) QuickSort(i,t);
    }
  
};
  
int main()
{
   ifstream in("INPUT.TXT");    
   ofstream out("OUTPUT.TXT"); out.clear();
   int N = 0;
   Program obj;
  
   in >> N;
  
   for (int i = 1; i <= N; i++)
   {
       in >> obj.arr[i];
   }
  
   obj.QuickSort(1,N);
  
   for (int i = 1; i <= N; i++)
   out << obj.arr[i] << " ";
     
   in.close();
   out.close();
  
   return 0;
}

Код на C#:

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
55
56
57
using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;
using System.IO;
 
    class Program
    {
        public static int[] arr = new int[1000000];
 
        public static void QuickSort(int m, int t)
        {
            int i, j, x, w;
            i = m;
            j = t;
            x = arr[(int)((m + t) / 2)];
 
 
            while (arr[i] < x) i++;
            while (arr[j] > x) j--;
 
            if (i <= j)
            {
                w = arr[i]; arr[i] = arr[j]; arr[j] = w;
                i++; j--;
            }
 
            if (m < j) QuickSort(m, j);
            if (i < t) QuickSort(i, t);
        }
 
        public static void Main()
        {
            StreamReader sr = new StreamReader("input.txt");
            StreamWriter sw = new StreamWriter("output.txt");
            int N;
 
            string[] s = sr.ReadLine().Split();
            N = int.Parse(s[0]);
 
            s = sr.ReadToEnd().Split();
            for (int i = 0; i < N; i++)
            {
                arr[i] = int.Parse(s[i]);
            }
 
            QuickSort(0, N-1);
 
            for (int i = 0; i < N; i++)
            {
                sw.Write(arr[i] + " ");
            }
 
            sr.Close();
            sw.Close();
        }
    }

Оба решения провалились на 7 тесте: выдала ошибку Time Limit Exceeded. Проще говоря - алгоритмы работали медленнее положенного (больше 2 секунд), медленнее Паскаля!!! Я долго искал ошибку в алгоритме - так и не нашёл. Оба алгоритма работали и сортировали массив как надо.

Поискав в интернете, я нашёл более оптимизированный вариант сортировки:
Код на С++:

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
55
56
57
58
59
60
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <conio.h>
using namespace std;
  
class Program
{
public:
    long int arr[100000];
  
    void QuickSort(int l, int r)
    {
        int x = arr[l + (r - l) / 2];
        int i = l;
        int j = r;
        while(i <= j)
        {
        while(arr[i] < x) i++;
        while(arr[j] > x) j--;
        if(i <= j)
        {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
    if (i<r)
        QuickSort(i, r);
     
    if (l<j)    
        QuickSort(l, j);
    }
  
};
  
int main()
{
   ifstream in("INPUT.TXT");    
   ofstream out("OUTPUT.TXT"); out.clear();
   int N = 0;
   Program obj;
  
   in >> N;
  
   for (int i = 0; i < N; i++)
   {
       in >> obj.arr[i];
   }
  
   obj.QuickSort(0,N-1);
  
   for (int i = 0; i < N; i++)
   out << obj.arr[i] << " ";
     
   in.close();
   out.close();
  
   return 0;
}

Код на C#:

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
55
56
57
58
59
60
using System;
using System.IO;
 
    class Program
    {
        public static int[] arr = new int[1000000];
 
        public static void QuickSort(int l, int r)
        {
            int x = arr[l + (r - l) / 2];
            
            int i = l;
            int j = r;
            int w;
            
            while (i <= j)
            {
                while (arr[i] < x) i++;
                while (arr[j] > x) j--;
                if (i <= j)
                {
                    w = arr[j]; arr[j] = arr[i]; arr[i] = w;
                    i++;
                    j--;
                }
            }
            if (i < r)
                QuickSort(i, r);
 
            if (l < j)
                QuickSort(l, j);
        }
 
        public static void Main()
        {
            int N;
            StreamReader sr = new StreamReader("input.txt");
            StreamWriter sw = new StreamWriter("output.txt");
 
            string[] s = sr.ReadLine().Split();
            N = int.Parse(s[0]);
 
            s = sr.ReadToEnd().Split();
            for (int i = 0; i < N; i++)
            {
                arr[i] = int.Parse(s[i]);
            }
 
 
            QuickSort(0,N-1);
 
            for (int i = 0; i < N; i++)
            {
                sw.Write(arr[i] + " ");
            }
 
            sr.Close();
            sw.Close();
        }
    }

Результаты стали интереснее: код на С++ наконец прошёл 7 тест, но остановился на 8 - выдало ошибку Runtime Error (видимо код выполнялся бесконечно, насколько я понял), код на С# меня сильно удивил, он прошёл и седьмой и восьмой тест, но остановился на девятом - выдало ошибку Memory limit exceeded, т.е. память, затраченная программой превышала 16 МБ (мое решение заняло 20 МБ).

Ошибка в коде на С++ объяснялась тем, что я занял массив не на миллион элементов, а на сто тысяч, я пытался занять массив на миллион (видимо плоха идея), но Microsoft Visual Studio 2008 выдал мне ошибку (как я и ожидал) - Stack Overflow.

Теперь мой вопрос: реально ли написать быструю сортировку на С++/С#, которая сортировала бы массив на миллион элементов, учитывая, что на С++ нельзя заводить массивы на миллион элементов, а на C# все это дельце занимает слишком много памяти? Есть ли какой-нибудь более "хитрый" алгоритм сортировки именно под эту задачу?

P.S. Прочитал решение этой задачи на acmu - там говорилось про сортировку подсчетом и приводился псевдокод решения задачи. Идею предложенного там решения я понял, погуглил, написал такую сортировку, но вылетела опять на седьмом тесте. А псевдокод, приведенный там - неработающий бред.

Короче говоря - я в тупике уже два дня. Помогите пожалуйста!

@Shamil1 · 19.10.2015, 10:16

Сортировка подсчётом.
Заводим массив на 201 элемент.
Для каждого числа из входных данных увеличиваем на 1 элемент массива A[t+100].
На основе этого массива формируем выход. (Для каждого элемента массива выводим число i-100 A[i] раз).

Добавлено через 20 минут
Посмотрел код C# и не нашёл отличий между первым и вторым ("более продвинутым") вариантами.
Мне не нравится, как Вы считываете массив. Предлагаю считывать по одному числу (как Вы делаете в Паскале) и обойтись без ReadToEnd

@Dimension · 19.10.2015, 11:59

Сообщение от ОчереднойДжедай

Сразу понял, что задача решается обычной быстрой сортировкой

какой вы догадливый ,но название задачи "Сортировка Подсчетом" вам не о чем не говорит?Решается как уже написали выше

@Shamil1 · 19.10.2015, 12:11

Сообщение от Shamil1

Посмотрел код C# и не нашёл отличий между первым и вторым ("более продвинутым") вариантами.

Посмотрел более внимательно и обнаружил, что в первом коде не хватает цикла, который у Вас в Паскале "repeat ... until i> j". После исправления этой ошибки на моём компьютере быстрая сортировка работает полсекунды.

@ОчереднойДжедай · 19.10.2015, 12:28 **[ТС]**

Здравствуйте, спасибо, что написали.
Прочитал ваш вариант сортировки, опять погуглил, порылся в своих кодах, соединил вместе и написал следующее:
Код на C#:

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
using System;
using System.IO;
    class Program
    {
        public static int[] arr = new int[202];
 
        public static void Main()
        {
            int N, x = 0;
            StreamReader sr = new StreamReader("input.txt");
            StreamWriter sw = new StreamWriter("output.txt");
 
            string[] s = sr.ReadLine().Split();
            N = int.Parse(s[0]);
 
            s = sr.ReadToEnd().Split();
 
            for (int i = 0; i < 202; i++)
            {
                arr[i] = 0;
            }
 
            for (int i = 0; i < N; i++)
            {
                x = Int32.Parse(s[i]);
                arr[x+100] = arr[x+100] + 1;
            }
 
            for (x = 0; x < 201; x++)
            {
                for (int i = 0; i < arr[x]; i++)
                {
                    sw.Write(x - 100 + " ");
                }
            }
 
            sr.Close();
            sw.Close();
        }
    }

Решение прошло 8 тестов, но на девятом застряло опять, выдало ошибку Memory limit exceeded (мое решение заняло 16МБ из 16).

И я решил поэкспериментировать с типами, в принципе, диапазон - от - 100 до + 100, т.е. обычного sbyte должно было хватить.

Код на C#:

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
using System;
using System.IO;
    class Program
    {
        public static sbyte[] arr = new sbyte[202];
 
        public static void Main()
        {
            int N;
            sbyte x = 0;
            StreamReader sr = new StreamReader("input.txt");
            StreamWriter sw = new StreamWriter("output.txt");
 
            string[] s = sr.ReadLine().Split();
            N = int.Parse(s[0]);
 
            s = sr.ReadToEnd().Split();
 
            for (int i = 0; i < 202; i++)
            {
                arr[i] = 0;
            }
 
            for (int i = 0; i < N; i++)
            {
                x = sbyte.Parse(s[i]);
                ++arr[x+100];
            }
 
            for (byte y = 0; y < 201; y++)
            {
                for (int i = 0; i < arr[y]; i++)
                {
                    sw.Write(y - 100 + " ");
                }
            }
 
            sr.Close();
            sw.Close();
        }
    }

На седьмом тесте выдало ошибку - Wrong Answer. Это очень странно, ведь я проверял сортировку - она работает.
В ближайшее время начну писать эту задачу на С++ - памяти он меньше жрет, может прокатит.

P.S. По поводу чтения из файлов в C#, в отличие от Pascal - чтение реализуется только через строки(насколько я знаю), которые уже нужно переводить в целые числа. Поэтому и пользовался ReadToEnd.

Добавлено через 5 минут
По поводу этого цикла: "repeat...until i>j", я его естественно заменил на "do..while(i>j)", но из-за этого программа застревала и бесконечно работала (даже не сортировала), затем поискав в интернете, нашёл быструю сортировку на С++ - единственное отличие - не было этого цикла "do...while(i>j)", я его удалил - всё пошло на лад.
В любом случае, сейчас пороюсь в кодах и на свежую голову попробую вернуть этот цикл - может у меня там ошибка была в другом месте.

@Shamil1 · 19.10.2015, 12:57

Сообщение от ОчереднойДжедай

По поводу этого цикла: "repeat...until i>j", я его естественно заменил на "do..while(i>j)"

do...while(i<=j)

@ОчереднойДжедай · 19.10.2015, 13:14 **[ТС]**

Глупейшая ошибка! Я бы ее никогда не нашел, спасибо!)

@Shamil1 · 19.10.2015, 13:17

Сообщение от ОчереднойДжедай

По поводу чтения из файлов в C#, в отличие от Pascal - чтение реализуется только через строки(насколько я знаю), которые уже нужно переводить в целые числа. Поэтому и пользовался ReadToEnd.

Выделяется память под строку.
Затем выделяется память под массив строк и выделяется память для каждой строки.
Затем каждая строка обрабатывается парсером.
Это очень много лишней работы (в 5-10 раз больше, чем сама сортировка). И это время можно сократить на порядок, если не выделять ненужную память. Запись можно сократить примерно в 1.5 раза (не выделять память под строку-число), поэтому нет особого смысла усложнять код.

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
int[] ReadInput()
{
    const int zero = (int)'0';
    const string pathInput = @"d:\Temp\input.txt";
    int[] arr;
    using(var file = new StreamReader(pathInput))
    {
        int count = int.Parse(file.ReadLine());
        arr = new int[count];
        for(int i = 0; i < arr.Length; i++)
        {
            int sign = 1;
            int n = 0;
            int d = file.Read() - zero;
            if(d == -3)
            {
                sign = -1;
                d = file.Read() - zero;
            }
            while(d >= 0)
            {
                n = n*10 + d;               
                d = file.Read() - zero;
            }
            arr[i] = n * sign;
        }
    }
    return arr; 
}

@ОчереднойДжедай · 19.10.2015, 15:12 **[ТС]**

Мои решения этой задачи (все прошли на 100 баллов):
Код С#:

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
using System;
using System.IO;
namespace ex1
{
    class Program
    {
        public static /*sbyte*/int[] arr = new int/*sbyte*/[1000000];
 
        public static void QuickSort(int m, int t)
        {
            int i, j, x, w;
            i = m;
            j = t;
            x = arr[(int)((m + t) / 2)];
 
            do
            {
 
                while (arr[i] < x) i++;
                while (arr[j] > x) j--;
 
                if (i <= j)
                {
                    w = arr[i]; arr[i] = arr[j]; arr[j] = w;
                    i++; j--;
                }
            } while (i <= j);
 
            if (m < j) QuickSort(m, j);
            if (i < t) QuickSort(i, t);
        }
 
        public static int[] ReadInput()
        {
            const int zero = (int)'0';
            const string pathInput = @"input.txt";
            int[] arr;
            using (var file = new StreamReader(pathInput))
            {
                int count = int.Parse(file.ReadLine());
                arr = new int[count];
                for (int i = 0; i < arr.Length; i++)
                {
                    int sign = 1;
                    int n = 0;
                    int d = file.Read() - zero;
                    if (d == -3)
                    {
                        sign = -1;
                        d = file.Read() - zero;
                    }
                    while (d >= 0)
                    {
                        n = n * 10 + d;
                        d = file.Read() - zero;
                    }
                    arr[i] = n * sign;
                }
            }
            return arr;
        }
 
        public static void Main()
        {
            //int N;
            /*sbyte x = 0;*/
            StreamReader sr = new StreamReader("input.txt");
            StreamWriter sw = new StreamWriter("output.txt");
 
            //var file = new StreamReader("input.txt");
            //N = int.Parse(file.ReadLine());
            //file.Close();
 
            arr = ReadInput();
 
 
            QuickSort(0, arr.Length - 1);
           /* for (int i = 0; i < N; i++)
            {
                x = sbyte.Parse(s[i]);
                ++arr[x+100];
            }
 
            for (byte y = 0; y < 201; y++)
            {
                for (int i = 0; i < arr[y]; i++)
                {
                    sw.Write(y - 100 + " ");
                }
            } */
 
            for (int i = 0; i < arr.Length; i++)
            {
                sw.Write(arr[i] + " ");
            }
 
            sr.Close();
            sw.Close();
        }
    }
}

Код С++:

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
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <conio.h>
using namespace std;
  
int main()
{
   ifstream in("INPUT.TXT");    
   ofstream out("OUTPUT.TXT"); out.clear();
   int N, x;
   long int arr[202];
   in >> N;
 
   for (int i = 0; i < 201; i++)
       arr[i] = 0;
 
   for (int i = 0; i < N; i++)
   {
       in >> x;
       arr[x+100] = arr[x+100]+1;
   }
 
   for (x = 0; x < 201; x++)
   {
       for (int i = 0; i < arr[x]; i++)
       {
           out << x - 100 << " ";
       }
   }
 
   in.close();
   out.close();
   return 0;
}

Спасибо большое, наконец-то я могу заснуть спокойно)).
Про "особое" чтение массива из файла в С# - я бы никогда не догадался, спасибо вам ещё раз за помощь в "освоении" и в написании сортировки подсчётом, ну и за нахождение ошибки в быстрой сортировке.

Ну правда, очень помогли

@PhantomSoft · 22.10.2015, 03:47

Сообщение от ОчереднойДжедай

Pascal
1
var arr:array [1..1000000] of longint;

если температура от -100 до +100, то зачем LongInt? Достаточно ShortInt... и памяти программа жрет меньше в 4 раза!

Новые блоги и статьи Все статьи Все блоги /
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .

@Shamil1 Модератор 3133 / 2280 / 469 Регистрация: 26.03.2015 Сообщений: 8,876
	19.10.2015, 10:16
	Сортировка подсчётом. Заводим массив на 201 элемент. Для каждого числа из входных данных увеличиваем на 1 элемент массива A[t+100]. На основе этого массива формируем выход. (Для каждого элемента массива выводим число i-100 A[i] раз). Добавлено через 20 минут Посмотрел код C# и не нашёл отличий между первым и вторым ("более продвинутым") вариантами. Мне не нравится, как Вы считываете массив. Предлагаю считывать по одному числу (как Вы делаете в Паскале) и обойтись без ReadToEnd 1

@ОчереднойДжедай 0 / 0 / 0 Регистрация: 18.10.2015 Сообщений: 7
	19.10.2015, 13:14 [ТС]
	Глупейшая ошибка! Я бы ее никогда не нашел, спасибо!) 0