fork download 
  1. using System; using System.Text;
  2. using System.Text.RegularExpressions;
  3.  
  4. public static class ThanosMeanLessMemory
  5. {   // --- int[] ---
  6.     public static void ThanosIntSortInPlace(int[] a)
  7.     {   if (a == null || a.Length < 2) return;
  8.         var sorted = SortNoExtraCopy(a);
  9.         Array.Copy(sorted, a, a.Length);
  10.     }
  11.  
  12.     private static int[] SortNoExtraCopy(int[] seg)
  13.     {   int n = seg.Length;
  14.         if (n < 2) return seg;
  15.  
  16.         int mn = seg[0], mx = seg[0]; long sum = seg[0];
  17.         for (int i = 1; i < n; i++) { int v = seg[i]; if (v < mn) mn = v; if (v > mx) mx = v; sum += v; }
  18.         if (mn == mx) return seg;
  19.  
  20.         double c = sum / (double)n;
  21.  
  22.         int cntL = 0; foreach (var v in seg) if (v <= c) cntL++;
  23.         int cntR = n - cntL;
  24.  
  25.         var left = new int[cntL];
  26.         var right = new int[cntR];
  27.         int iL = 0, iR = 0;
  28.         foreach (var v in seg) if (v <= c) left[iL++] = v; else right[iR++] = v;
  29.  
  30.         left = SortNoExtraCopy(left);
  31.         right = SortNoExtraCopy(right);
  32.  
  33.         var outArr = new int[n];
  34.         Array.Copy(left, 0, outArr, 0, left.Length);
  35.         Array.Copy(right, 0, outArr, left.Length, right.Length);
  36.         return outArr;
  37.     }
  38.  
  39.     // --- генераторы ---
  40.  
  41.     public static int[] GenerateRandomArray(int n, int min, int max)
  42.     {   var rnd = new Random();
  43.         var arr = new int[n];
  44.         for (int i = 0; i < n; i++) arr[i] = rnd.Next(min, max + 1);
  45.         return arr;
  46.     }
  47. }
  48.  
  49. public class Program
  50. {   static string Arr<T>(T[] a) => "[" + string.Join(", ", a) + "]";
  51.  
  52.     public static void Main()
  53.     {   // Консоль в UTF-8
  54.         Console.OutputEncoding = Encoding.UTF8;
  55.         Console.InputEncoding = Encoding.UTF8;
  56.  
  57.         // int
  58.         var x = new[] { 5, 1, 9, 3, 7, 2, 2, 8, 4, 6 };
  59.         ThanosMeanLessMemory.ThanosIntSortInPlace(x);
  60.         Console.WriteLine(Arr(x));
  61.  
  62.         var arr = ThanosMeanLessMemory.GenerateRandomArray(25, -1000, 1000);
  63.         Console.WriteLine("arr  before : " + Arr(arr));
  64.         ThanosMeanLessMemory.ThanosIntSortInPlace(arr);
  65.         Console.WriteLine("arr  sorted : " + Arr(arr));
  66. }}
Success #stdin #stdout 0.05s 27960KB
comments (?)
stdin 
Standard input is empty
stdout 
[1, 2, 2, 3, 4, 5, 6, 7, 8, 9]
arr  before : [279, -834, 473, 451, 15, 943, -335, 326, -943, -956, 953, 8, -371, 933, 893, 187, -985, 159, 911, 593, -599, 60, 130, 633, 753]
arr  sorted : [-985, -956, -943, -834, -599, -371, -335, 8, 15, 60, 130, 159, 187, 279, 326, 451, 473, 593, 633, 753, 893, 911, 933, 943, 953]
https://ideone.com/xfItX6
language:
C# (NET 6.0)
created:
1 day 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!