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

@ОчереднойДжедай · Регистрация: 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 раза!

Новые блоги и статьи Все статьи Все блоги /
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,886
	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