fork download 
  1. using System;
  2. using System.Text;
  3. using System.Text.RegularExpressions;
  4.  
  5. public static class ThanosMeanLessMemory
  6. {
  7.  
  8.     // --- int[] ---
  9.     public static void ThanosIntSortInPlace(int[] a)
  10.     {
  11.         if (a == null || a.Length < 2) return;
  12.         var sorted = SortNoExtraCopy(a);
  13.         Array.Copy(sorted, a, a.Length);
  14.     }
  15.  
  16.     private static int[] SortNoExtraCopy(int[] seg)
  17.     {
  18.         int n = seg.Length;
  19.         if (n < 2) return seg;
  20.  
  21.         int mn = seg[0], mx = seg[0]; long sum = seg[0];
  22.         for (int i = 1; i < n; i++) { int v = seg[i]; if (v < mn) mn = v; if (v > mx) mx = v; sum += v; }
  23.         if (mn == mx) return seg;
  24.  
  25.         double c = sum / (double)n;
  26.  
  27.         int cntL = 0; foreach (var v in seg) if (v <= c) cntL++;
  28.         int cntR = n - cntL;
  29.  
  30.         var left = new int[cntL];
  31.         var right = new int[cntR];
  32.         int iL = 0, iR = 0;
  33.         foreach (var v in seg) if (v <= c) left[iL++] = v; else right[iR++] = v;
  34.  
  35.         left = SortNoExtraCopy(left);
  36.         right = SortNoExtraCopy(right);
  37.  
  38.         var outArr = new int[n];
  39.         Array.Copy(left, 0, outArr, 0, left.Length);
  40.         Array.Copy(right, 0, outArr, left.Length, right.Length);
  41.         return outArr;
  42.     }
  43.  
  44.     // --- генераторы ---
  45.  
  46.     public static int[] GenerateRandomArray(int n, int min, int max)
  47.     {
  48.         var rnd = new Random();
  49.         var arr = new int[n];
  50.         for (int i = 0; i < n; i++) arr[i] = rnd.Next(min, max + 1);
  51.         return arr;
  52.     }
  53. }
  54.  
  55. public class Program
  56. {
  57.     static string Arr<T>(T[] a) => "[" + string.Join(", ", a) + "]";
  58.  
  59.     public static void Main()
  60.     {
  61.         // Консоль в UTF-8
  62.         Console.OutputEncoding = Encoding.UTF8;
  63.         Console.InputEncoding = Encoding.UTF8;
  64.  
  65.         // int
  66.         var x = new[] { 5, 1, 9, 3, 7, 2, 2, 8, 4, 6 };
  67.         ThanosMeanLessMemory.ThanosIntSortInPlace(x);
  68.         Console.WriteLine(Arr(x));
  69.  
  70.         var arr = ThanosMeanLessMemory.GenerateRandomArray(25, -1000, 1000);
  71.         Console.WriteLine("arr  before : " + Arr(arr));
  72.         ThanosMeanLessMemory.ThanosIntSortInPlace(arr);
  73.         Console.WriteLine("arr  sorted : " + Arr(arr));
  74.  
  75.         }
  76. }
Success #stdin #stdout 0.06s 28176KB
comments (?)
stdin 
Standard input is empty
stdout 
[1, 2, 2, 3, 4, 5, 6, 7, 8, 9]
arr  before : [378, 547, 785, -288, -594, -418, 804, -132, 174, 230, 29, 680, 569, -687, -649, 33, 656, -380, -950, 646, 877, 224, -835, 602, -656]
arr  sorted : [-950, -835, -687, -656, -649, -594, -418, -380, -288, -132, 29, 33, 174, 224, 230, 378, 547, 569, 602, 646, 656, 680, 785, 804, 877]
https://ideone.com/k27j7a
language:
C# (NET 6.0)
created:
14 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!