Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Dingleberry fetish

By: a guest on May 16th, 2012  |  syntax: C#  |  size: 4.28 KB  |  hits: 18  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. namespace DS2012prac3
  5. {
  6.     class R_Quicksort
  7.     {
  8.         static void Main(string[] args)
  9.         {
  10.             try
  11.             {
  12.             R_Quicksort QS = new R_Quicksort();
  13.  
  14.             int InputAmount = int.Parse(Console.ReadLine());
  15.             NumberPair[] Numbers = new NumberPair[InputAmount];
  16.  
  17.             string[] test;
  18.             for (int x = 0; x < InputAmount; x++)
  19.             {
  20.                 test = Console.ReadLine().Split(' ');
  21.                 Numbers[x] = new NumberPair(int.Parse(test[0]), int.Parse(test[1]));
  22.             }
  23.            
  24.             QS.RandomizedQuicksort(Numbers, 0, Numbers.Length - 1);
  25.  
  26.             for (int y = 0; y < Numbers.Length; y++)
  27.                 Console.WriteLine(Numbers[y].FirstNumber + " " + Numbers[y].SecondNumber);// + "<" + Numbers[y].Pair + " >" );
  28.             }
  29.             catch (Exception e)
  30.             {
  31.                 Console.WriteLine("error: " + e);
  32.             }
  33.             Console.ReadLine();
  34.         }
  35.  
  36.         //---------------------------------------------------------------------------\\
  37.  
  38.         public void RandomizedQuicksort(NumberPair[] Numbers, int p, int r)
  39.         {
  40.             if (p < r)
  41.             {      
  42.                 if (r - p < 20)
  43.                     InsertionSort(Numbers, p, r);
  44.                 else
  45.                 {
  46.                     int q = RandomizedPartition(Numbers, p, r);
  47.                     RandomizedQuicksort(Numbers, p, q - 1);
  48.                     RandomizedQuicksort(Numbers, q + 1, r);
  49.                 }
  50.             }
  51.         }
  52.  
  53.         public int RandomizedPartition(NumberPair[] Numbers, int p, int r)
  54.         {
  55.             Random random = new Random();
  56.             int i = random.Next(p, r);
  57.             Switchems(Numbers, i, r);
  58.             return Partition(Numbers, p, r);
  59.         }
  60.  
  61.         public int Partition(NumberPair[] Numbers, int p, int r)
  62.         {
  63.             NumberPair x = Numbers[r];
  64.             int i = p - 1;
  65.             for (int j = p; j < r; j++)
  66.             {
  67.                 if (Numbers[j].Pair < x.Pair)
  68.                 {
  69.                     i = i + 1;
  70.                     Switchems(Numbers, i, j);
  71.                 }
  72.                 else if (Numbers[j].Pair == x.Pair)
  73.                     if (Numbers[j].FirstNumber < x.FirstNumber)
  74.                     {
  75.                         i = i + 1;
  76.                         Switchems(Numbers, i, j);
  77.                     }
  78.             }
  79.             Switchems(Numbers, i + 1, r);
  80.  
  81.             return i + 1;
  82.         }
  83.  
  84.         //---------------------------------------------------------------------------\\
  85.  
  86.         public NumberPair[] Switchems(NumberPair[] Numbers, int i, int r)
  87.         {
  88.             NumberPair holdr = Numbers[r];
  89.             Numbers[r] = Numbers[i];
  90.             Numbers[i] = holdr;
  91.             return Numbers;
  92.         }
  93.  
  94.         //---------------------------------------------------------------------------\\
  95.  
  96.         public void InsertionSort(NumberPair[] Numbers, int bottom, int top)
  97.         {
  98.             for (int j = bottom + 1; j <= top; j++)
  99.             {
  100.                 NumberPair key = Numbers[j];
  101.                 int i = j - 1;
  102.                 while (i >= bottom && key.Pair <= Numbers[i].Pair)
  103.                 {
  104.                     if (key.Pair == Numbers[i].Pair)
  105.                     {
  106.                         if (key.FirstNumber < Numbers[i].FirstNumber)
  107.                             Numbers[i + 1] = Numbers[i];
  108.                         else break;
  109.                     }
  110.                     else
  111.                        Numbers[i + 1] = Numbers[i];
  112.  
  113.                     i--;
  114.                 }
  115.                 Numbers[i + 1] = key;
  116.             }
  117.         }
  118.     }
  119.  
  120.     //---------------------------------------------------------------------------\\
  121.  
  122.     class NumberPair
  123.     {
  124.         public int FirstNumber;
  125.         public int SecondNumber;
  126.         private double pair;
  127.         public NumberPair(int first, int second)
  128.         {
  129.             this.FirstNumber = first;
  130.             this.SecondNumber = second;
  131.             this.pair = (double)FirstNumber / (double)SecondNumber;
  132.         }
  133.    
  134.         public double Pair
  135.         {
  136.             get { return this.pair;  }
  137.         }
  138.     }
  139. }
create a new version of this paste RAW Paste Data