Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- namespace ConsoleApplication1 {
- class Program {
- static void Main(string[] args) {
- int[] tokuda = { 1, 4, 9, 20, 46, 103, 233, 525, 1182, 2660, 5985, 13467, 30301, 68178, 153401, 345152, 776591 };
- int[] s248 = { 1, 3, 7, 16, 38, 94, 233, 577, 1431, 3549, 8801, 21826, 54128, 134237, 332908, 825611 };
- int[] sizes = {10000, 50000, 100000, 200000, 300000, 500000, 1000000};
- string csv = "";
- foreach(int size in sizes) {
- // foreach size, try 100 times.
- for (int k = 0; k < 100; k++) {
- int[] list = new int[size];
- Random rnd = new Random();
- for (int i = 0; i < list.Length; i++) {
- list[i] = rnd.Next(0, Int32.MaxValue);
- }
- int[] tmp = (int[])list.Clone();
- int c = shellsort(tmp, tokuda);
- // Writing the CSV in the following format
- // Size of Array, Tokuda's comparison, Tokuda's swap
- csv += size + "," + c + "," + swap;
- tmp = (int[])list.Clone();
- c = shellsort(tmp, s248);
- csv += "," + c + "," + swap + "\n";
- }
- }
- System.IO.File.WriteAllText("result.csv", csv);
- }
- public static int compare = 0;
- public static int swap = 0;
- public static bool greaterthan(int a, int b) {
- compare++;
- return a > b;
- }
- public static int shellsort(int[] a, int[] gaps) {
- // For keeping track of number of swap and comparison
- compare = 0;
- swap = 0;
- int temp, gap, i, j;
- // Finding a gap that is smaller than the length of the array
- int gap_index = gaps.Length - 1;
- while (gaps[gap_index] > a.Length) gap_index--;
- while (gap_index >= 0) {
- // h-sorting
- gap = gaps[gap_index];
- for (i = gap; i < a.Length; i++) {
- temp = a[i];
- for(j = i; (j >= gap) && (greaterthan(a[j - gap], temp)); j -= gap) {
- a[j] = a[j - gap];
- swap++;
- }
- // swapping
- a[j] = temp;
- swap++;
- }
- gap_index--;
- }
- return compare;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement