merge sort and quick sort

[Shruti Tapadiya]

I wanted to know how can I implement merge sort and quick sort using multithreading in c#

[avirag]

I wanted to know how can I implement merge sort and quick sort using multithreading in c#

Hi shruti you can do like this:
MERGE SORT:

// array of integers to hold values
private int[] a = new int[100];
private int[] b = new int[100];

// number of elements in array
private int x;

// Merge Sort Algorithm
public void sortArray()
{
  m_sort( 0, x-1 );
}

public void m_sort( int left, int right )
{
  int mid;

  if( right > left )
  {
    mid = ( right + left ) / 2;
    m_sort( left, mid );
    m_sort( mid+1, right );

    merge( left, mid+1, right );
  }
}

public void merge( int left, int mid, int right )
{
  int i, left_end, num_elements, tmp_pos;

  left_end = mid - 1;
  tmp_pos = left;
  num_elements = right - left + 1;

  while( (left <= left_end) && (mid <= right) )
  {
    if( a[left] <= a[mid] )
    {
      b[tmp_pos] = a[left];
      tmp_pos = tmp_pos + 1;
      left = left +1;
    }
    else
    {
      b[tmp_pos] = a[mid];
      tmp_pos = tmp_pos + 1;
      mid = mid + 1;
    }
  }

  while( left <= left_end )
  {
    b[tmp_pos] = a[left];
    left = left + 1;
    tmp_pos = tmp_pos + 1;
  }

  while( mid <= right )
  {
    b[tmp_pos] = a[mid];
    mid = mid + 1;
    tmp_pos = tmp_pos + 1;
  }

  for( i = 0; i < num_elements; i++ )
  {
    a[right] = b[right];
    right = right - 1;
  }
}

And QUICK SORT:

// array of integers to hold values
private int[] a = new int[100];

// number of elements in array
private int x;

// Quick Sort Algorithm
public void sortArray()
{
  q_sort( 0, x-1 );
}

public void q_sort( int left, int right )
{
  int pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = a[left];

  while( left < right )
  {
    while( (a[right] >= pivot) && (left < right) )
    {
      right--;
    }

    if( left != right )
    {
      a[left] = a[right];
      left++;
    }

    while( (a[left] <= pivot) && (left < right) )
    {
      left++;
    }

    if( left != right )
    {
      a[right] = a[left];
      right--;
    }
  }

  a[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;

  if( left < pivot )
  {
    q_sort( left, pivot-1 );
  }

  if( right > pivot )
  {
    q_sort( pivot+1, right );
  }
}

Hope its help you............:)

[sknake]

Here is an example of running the code in another thread:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Collections;
using System.Runtime.Remoting.Messaging;

namespace daniweb
{
  public partial class frmQuickSort : Form
  {
    public frmQuickSort()
    {
      InitializeComponent();
    }

    public static int GetRandom(int Maxvalue)
    {
      byte[] randomNumber = new byte[1];
      System.Security.Cryptography.RNGCryptoServiceProvider Gen = new System.Security.Cryptography.RNGCryptoServiceProvider();
      Gen.GetBytes(randomNumber);
      int rand = Convert.ToInt32(randomNumber[0]);
      return rand % Maxvalue + 1;
    }


    private void button1_Click(object sender, EventArgs e)
    {
      List<int> lst = new List<int>();
      for (int i1 = 0; i1 < 50; i1++)
      {
        lst.Add(GetRandom(200));
      }
      int[] array = lst.ToArray();
      DoSort(array);
    }

    private void DoSort(int[] array)
    {
      MergeSorter ms = new MergeSorter(array);
      Func<int[]> del = new Func<int[]>(ms.sortArray);
      del.BeginInvoke(new AsyncCallback(SortCallback), null);
    }
    private void SortCallback(IAsyncResult ar)
    {
      AsyncResult result = (AsyncResult)ar;
      Func<int[]> del = (Func<int[]>)result.AsyncDelegate;
      try
      {
        int[] array = del.EndInvoke(ar);
        this.textBox1.Invoke(new MethodInvoker(
          delegate()
          {
            string[] sArray = array.ToList().ConvertAll<string>(Convert.ToString).ToArray();
            textBox1.Text = string.Join(", ", sArray);
          }
        ));
      }
      catch (Exception ex)
      {
        this.textBox1.Invoke(new MethodInvoker(
          delegate()
          {
            textBox1.Text = "Error sorting array: " + Environment.NewLine +
              ex.Message;
          }
        ));
      }
    }


  }

  public class MergeSorter
  {
    private int[] a;
    // number of elements in array
    private int x;
    // Quick Sort Algorithm
    private MergeSorter()
    {
    }
    public MergeSorter(int[] array)
      : this()
    {
      this.a = array;
      this.x = array.Length;
    }
    public int[] sortArray()
    {
      q_sort(0, x - 1);
      return a;
    }
    private void q_sort(int left, int right)
    {
      int pivot, l_hold, r_hold;

      l_hold = left;
      r_hold = right;
      pivot = a[left];

      while (left < right)
      {
        while ((a[right] >= pivot) && (left < right))
        {
          right--;
        }

        if (left != right)
        {
          a[left] = a[right];
          left++;
        }

        while ((a[left] <= pivot) && (left < right))
        {
          left++;
        }

        if (left != right)
        {
          a[right] = a[left];
          right--;
        }
      }

      a[left] = pivot;
      pivot = left;
      left = l_hold;
      right = r_hold;

      if (left < pivot)
      {
        q_sort(left, pivot - 1);
      }

      if (right > pivot)
      {
        q_sort(pivot + 1, right);
      }
    }
  }
}