A005_SortWithGraph

<Window x:Class="SortWithGraph.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
        xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
        xmlns:local="clr-namespace:SortWithGraph"
        mc:Ignorable="d"
        Title="Sort with Graph" Height="450" Width="1127.48">
    <Grid Margin="0,0,2,-3">
        <Grid.ColumnDefinitions>
            <ColumnDefinition Width="15*"/>
            <ColumnDefinition Width="29*"/>
        </Grid.ColumnDefinitions>
        <TextBlock HorizontalAlignment="Left" Margin="56,36,0,0" TextWrapping="Wrap" Text="데이터 갯수
                   " VerticalAlignment="Top"/>
        <TextBox x:Name="txtData" HorizontalAlignment="Left" Height="23" Margin="132,35,0,0" TextWrapping="Wrap" Text="200" VerticalAlignment="Top" Width="142" HorizontalContentAlignment="Center" Grid.ColumnSpan="2"/>
        <Button x:Name="btnCreate" Content="랜덤 숫자 생성" HorizontalAlignment="Left" Margin="52,35,0,0" VerticalAlignment="Top" Width="100" Height="23" Grid.Column="1" Click="BtnCreate_Click"/>
        <Canvas x:Name="canvas" HorizontalAlignment="Left" Height="238" Margin="58,150,0,0" VerticalAlignment="Top" Width="1000" Background="#FFD3E3E4" Grid.ColumnSpan="2"/>
        <TextBlock HorizontalAlignment="Left" Margin="124,102,0,0" TextWrapping="Wrap" Text="수행과정 그래프 확인 : " VerticalAlignment="Top" Grid.ColumnSpan="2" Width="150"/>
        <Button x:Name="btnTime" Content="시간측정" HorizontalAlignment="Left" Margin="52,70,0,0" VerticalAlignment="Top" Width="100" Grid.Column="1" Click="BtnTime_Click"/>
        <TextBlock HorizontalAlignment="Left" Margin="124,72,0,0" TextWrapping="Wrap" Text="알고리즘 별 실행속도 : " VerticalAlignment="Top" RenderTransformOrigin="0.468,1.138" Grid.ColumnSpan="2" Width="150"/>
        <Button x:Name="btnBubble" Content="버블정렬" Grid.Column="1" HorizontalAlignment="Left" Margin="52,102,0,0" VerticalAlignment="Top" Width="100" RenderTransformOrigin="0.015,0.635" Click="BtnBubble_Click"/>
        <Button x:Name="btnQuick" Content="퀵 정렬" Grid.Column="1" HorizontalAlignment="Left" Margin="172,102,0,0" VerticalAlignment="Top" Width="100" RenderTransformOrigin="0.015,0.635" Click="BtnQuick_Click"/>
        <Button x:Name="btnMerge" Content="합병 정렬" Grid.Column="1" HorizontalAlignment="Left" Margin="290,102,0,0" VerticalAlignment="Top" Width="100" RenderTransformOrigin="0.015,0.635" Click="BtnMerge_Click" />

    </Grid>
</Window>

 

using System;
using System.Threading;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Media;
using System.Windows.Shapes;

namespace SortWithGraph
{
  public partial class MainWindow : Window
  {
    static int MAX = 1000000;
    int[] a = new int[MAX];
    int N = 0; 
    Thread t1;
    private bool timeFlag;

    public MainWindow()
    {
      InitializeComponent();      
    }

    private void BtnCreate_Click(object sender, RoutedEventArgs e)
    {
      N = int.Parse(txtData.Text);
      Console.WriteLine(N);

      Random r = new Random();
      for (int i = 0; i < N; i++)
      {
        a[i] = r.Next(3 * N);
      }

      Graph();
      PrintArray(0, N);
    }

    private void Graph()
    {
      canvas.Children.Clear();

      for (int i = 0; i < N; i++)
      {        
        Line l = new Line();
        l.X1 = l.X2 = i * 5;
        if (l.X1 > canvas.Width)
          break;
        l.Y1 = canvas.Height - (int)(a[i] / (3.0 * N) * canvas.Height);
        l.Y2 = canvas.Height;
        l.HorizontalAlignment = HorizontalAlignment.Left;
        l.VerticalAlignment = VerticalAlignment.Bottom;
        l.Stroke = Brushes.RoyalBlue;
        l.StrokeThickness = 4;
        canvas.Children.Add(l);
      }
    }

    private void BtnTime_Click(object sender, RoutedEventArgs e)
    {
      timeFlag = true;

      var watch = System.Diagnostics.Stopwatch.StartNew();
      BubbleSort();
      watch.Stop();
      long tickBubble = watch.ElapsedTicks;

      Graph();

      TextBlock txtBubble = new TextBlock();
      txtBubble.Text = "Bubble Sort : " + tickBubble + " Ticks.  " + tickBubble / 10000.0 + " ms.";
      txtBubble.Foreground = Brushes.Black;
      txtBubble.Background = Brushes.White;
      Canvas.SetLeft(txtBubble, 100);
      Canvas.SetTop(txtBubble, 100);
      canvas.Children.Add(txtBubble);

      Random r = new Random();
      for (int i = 0; i < N; i++)
      {
        a[i] = r.Next(3 * N);
      }
      watch = System.Diagnostics.Stopwatch.StartNew();
      DSQSort(a, 0, N - 1);
      watch.Stop();
      long tickQuick = watch.ElapsedTicks;

      TextBlock txtQuick = new TextBlock();
      txtQuick.Text = "Quick Sort : " + tickQuick + " Ticks.  " + tickQuick / 10000.0 + " ms.";
      txtQuick.Foreground = Brushes.Black;
      txtQuick.Background = Brushes.White;
      Canvas.SetLeft(txtQuick, 100);
      Canvas.SetTop(txtQuick, 120);
      canvas.Children.Add(txtQuick);

      for (int i = 0; i < N; i++)
      {
        a[i] = r.Next(3 * N);
      }

      watch = System.Diagnostics.Stopwatch.StartNew();
      MergeSort(a, 0, N - 1);
      watch.Stop();
      long tickMerge = watch.ElapsedTicks;

      TextBlock txtMerge = new TextBlock();
      txtMerge.Text = "Merge Sort : " + tickMerge + " Ticks.  " + tickMerge/10000.0 + " ms.";
      txtMerge.Foreground = Brushes.Black;
      txtMerge.Background = Brushes.White;
      Canvas.SetLeft(txtMerge, 100);
      Canvas.SetTop(txtMerge, 140);
      canvas.Children.Add(txtMerge);

      timeFlag = false;
    }


    private void BubbleSort()
    {
      for (int i = N - 1; i > 0; i--) { 
        for (int j = 0; j < i; j++)
        {
          if (a[j] > a[j + 1])
          {
            int t = a[j];
            a[j] = a[j + 1];
            a[j + 1] = t;
          }
        }
        
        if (timeFlag == false)
        {
          Dispatcher.Invoke(new Action(Graph));
          Thread.Sleep(50);
        }
      }
    }

    private void QuickSortMain()
    {
      DSQSort(a, 0, N - 1); 
      PrintArray(0, N);
    }

    private void DSQSort(int[] a, int left, int right)
    {
      if(left < right)
      {
        int q = partition(a, left, right);
        DSQSort(a, left, q - 1);
        DSQSort(a, q + 1, right);
        if (timeFlag == false)
        {
          Dispatcher.Invoke(new Action(Graph));
          Thread.Sleep(50);
        }
      }
    }
    
    private int partition(int[] a, int left, int right)
    {
      int low = left;
      int high = right + 1;
      int pivot = a[left];


      do
      {
        do
        {
          low++;
        } while (low <= right && a[low] < pivot);
        do
        {
          high--;
        } while (high >= left && a[high] > pivot);
        if (low < high)
        {
          int tmp = a[low];
          a[low] = a[high];
          a[high] = tmp;
        }
      } 
      while (low < high);
      
      a[left] = a[high];
      a[high] = pivot;


      return high;
    }

    private void QuickSort(int[] arr, int left, int right)
    {
      if (left < right)
      {
        int pivot = Partition(arr, left, right);
        QuickSort(arr, left, pivot - 1);
        QuickSort(arr, pivot + 1, right);

        Dispatcher.Invoke(new Action(Graph));
        Thread.Sleep(50);
      }
    }

    private void PrintArray(int left, int right)
    {
      for (int i = left; i < right; i++)
      {
        Console.Write(a[i] + ", ");
      }
      Console.WriteLine();
    }

    private int Partition(int[] arr, int left, int right)
    {
      int i = left;
      int j = right;

      int pivot = arr[left]; 

      while (i < j)
      {
        while ((i <= right) && (arr[i] < pivot))
          i++;

        while ((j >= left) && (arr[j] > pivot))
          j--;

        if (i < j)
        {
          int t = arr[i];
          arr[i] = arr[j];
          arr[j] = t;

          if (arr[i] == arr[j])
          {
            Console.WriteLine(".. in if index a[{0}] = a[{1}] = {2}", i, j, arr[i]);
            j--;
          }
        }
      }
      return j;
    }


    private void BtnBubble_Click(object sender, RoutedEventArgs e)
    {
      t1 = new Thread(BubbleSort);
      t1.Start();
    }

    private void BtnQuick_Click(object sender, RoutedEventArgs e)
    {
      t1 = new Thread(QuickSortMain);
      t1.Start();
    }

    private void BtnMerge_Click(object sender, RoutedEventArgs e)
    {
      t1 = new Thread(MergeSortMain);
      t1.Start();
    }

    private void MergeSortMain()
    {
      MergeSort(a, 0, N - 1);
    }

    private void MergeSort(int[] arr, int left, int right)
    {
      if(left < right)
      {
        int mid = (left + right) / 2;
        MergeSort(a, left, mid);
        MergeSort(a, mid + 1, right);
        Merge(a, left, mid, right);
        if (timeFlag == false)
        {
          Dispatcher.Invoke(new Action(Graph));
                    Thread.Sleep(50);
                }
      }
    }

    int[] sorted = new int[MAX];
    private void Merge(int[] a, int left, int mid, int right)
    {
      int i, j, k = left;
      for (i = left, j = mid+1; i<=mid && j<=right; )
      {
        sorted[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
      }
      if (i > mid) 
        for (int l = j; l <= right; l++)
          sorted[k++] = a[l];
      else 
        for (int l = i; l <= mid; l++)
          sorted[k++] = a[l];

      for (int l = left; l <= right; l++)
      {
        a[l] = sorted[l];
      }
    }
  }
}