I wanted to know how can I implement merge sort and quick sort using multithreading in c#
Shruti Tapadiya 0 Newbie Poster
avirag 10 Posting Whiz
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 1,622 Senior Poster Featured Poster
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);
}
}
}
}
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.