Advertisement
zoltanvi

Insertion sort vs Bubble short

May 20th, 2018
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 3.14 KB | None | 0 0
  1. using System;
  2. using System.Diagnostics;
  3.  
  4.  
  5. public class Sorting
  6. {
  7.     public static void Main()
  8.     {
  9.         Random rand = new Random();
  10.         Stopwatch sw = new Stopwatch();
  11.        
  12.         int[] array1 = new int[10000];
  13.         int[] array2 = new int[10000];
  14.         int[] array3 = new int[10000];
  15.         int[] array4 = new int[10000];
  16.        
  17.        
  18.         // Feltöltés
  19.         for (int i = 0; i < array1.Length; i++)
  20.         {
  21.             array1[i] = array2[i] = array3[i] = array4[i] = rand.Next(Int32.MinValue, Int32.MaxValue); 
  22.         }
  23.        
  24.         // Quicksort
  25.         sw.Start();
  26.         UnsafeQuickSort(array1);
  27.         sw.Stop();
  28.         Console.WriteLine("========= Quicksort\nElapsed time on a random array (size = 10000): = {0}",sw.Elapsed);
  29.         sw.Reset();
  30.        
  31.         sw.Start();
  32.         UnsafeQuickSort(array1);
  33.         sw.Stop();
  34.         Console.WriteLine("Elapsed time on a sorted array (size = 10000): = {0}",sw.Elapsed);
  35.         sw.Reset();
  36.        
  37.         Console.WriteLine();
  38.        
  39.         // Insertion sort
  40.         sw.Start();
  41.         InsertionSort(array2);
  42.         sw.Stop();
  43.         Console.WriteLine("========= Insertion sort\nElapsed time on a random array (size = 10000): = {0}",sw.Elapsed);
  44.         sw.Reset();
  45.  
  46.         sw.Start();
  47.         InsertionSort(array2);
  48.         sw.Stop();
  49.         Console.WriteLine("Elapsed time on a sorted array (size = 10000): = {0}",sw.Elapsed);
  50.         sw.Reset();
  51.        
  52.         Console.WriteLine();
  53.        
  54.         // Bubble sort
  55.         sw.Start();
  56.         BubbleSort(array3);
  57.         sw.Stop();
  58.         Console.WriteLine("========= Bubble sort\nElapsed time on a random array (size = 10000): = {0}",sw.Elapsed);
  59.         sw.Reset();
  60.  
  61.         sw.Start();
  62.         BubbleSort(array3);
  63.         sw.Stop();
  64.         Console.WriteLine("Elapsed time on a sorted array (size = 10000): = {0}",sw.Elapsed);
  65.         sw.Reset();
  66.     }
  67.    
  68.     public static void InsertionSort(int[] data)
  69.     {
  70.         for (int i = 0; i < data.Length - 1; i++)
  71.         {
  72.             for (int j = i + 1; j > 0; j--)
  73.             {
  74.                 if (data[j - 1] < data[j])
  75.                 {
  76.                     int temp = data[j - 1];
  77.                     data[j - 1] = data[j];
  78.                     data[j] = temp;
  79.                 }
  80.             }
  81.         }
  82.     }
  83.    
  84.     public static void BubbleSort(int[] data)
  85.     {
  86.         for(int i=0; i < data.Length; i++){  
  87.             for(int j=1; j < (data.Length-i); j++){  
  88.                 if(data[j-1] < data[j]){  
  89.                     //swap elements  
  90.                     int temp = data[j-1];  
  91.                     data[j-1] = data[j];  
  92.                     data[j] = temp;  
  93.                 }  
  94.             }  
  95.         }
  96.     }
  97.    
  98.    
  99.     public unsafe static void UnsafeQuickSort(int[] data)
  100.     {
  101.         fixed (int* pdata = data)
  102.         {
  103.             UnsafeQuickSortRecursive(pdata, 0, data.Length - 1);
  104.         }
  105.     }
  106.  
  107.     private unsafe static void UnsafeQuickSortRecursive(int* data, int left, int right)
  108.     {
  109.         int i = left - 1;
  110.         int j = right;
  111.  
  112.         while (true)
  113.         {
  114.             int d = data[left];
  115.             do i++; while (data[i] < d);
  116.             do j--; while (data[j] > d);
  117.  
  118.             if (i < j)
  119.             {
  120.                 int tmp = data[i];
  121.                 data[i] = data[j];
  122.                 data[j] = tmp;
  123.             }
  124.             else
  125.             {
  126.                 if (left < j) UnsafeQuickSortRecursive(data, left, j);
  127.                 if (++j < right) UnsafeQuickSortRecursive(data, j, right);
  128.                 return;
  129.             }
  130.         }
  131.     }
  132.    
  133.    
  134.    
  135. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement