|
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!--------------------------------------------------------------------------->
<!-- INTRODUCTION
The Code Project article submission template (HTML version)
Using this template will help us post your article sooner. To use, just
follow the 3 easy steps below:
1. Fill in the article description details
2. Add links to your images and downloads
3. Include the main article text
That's all there is to it! All formatting will be done by our submission
scripts and style sheets.
-->
<!--------------------------------------------------------------------------->
<!-- IGNORE THIS SECTION -->
<html>
<head>
<title>The Code Project</title>
<Style>
BODY, P, TD { font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10pt }
H2,H3,H4,H5 { color: #ff9900; font-weight: bold; }
H2 { font-size: 13pt; }
H3 { font-size: 12pt; }
H4 { font-size: 10pt; color: black; }
PRE { BACKGROUND-COLOR: #FBEDBB; FONT-FAMILY: "Courier New", Courier, mono; WHITE-SPACE: pre; }
CODE { COLOR: #990000; FONT-FAMILY: "Courier New", Courier, mono; }
</style>
<link rel="stylesheet" type="text/css" href="http://www.codeproject.com/App_Themes/NetCommunity/CodeProject.css">
</head>
<body bgcolor="#FFFFFF" color=#000000>
<!--------------------------------------------------------------------------->
<!------------------------------- STEP 1 --------------------------->
<!-- Fill in the details (CodeProject will reformat this section for you) -->
<pre>
Title: Merge Sort
Author: Ronnen Nagal
Email: nagalr@gmail.com
Member ID: Ron10001
Language: C# 3.0
Platform: Windows, .NET 3.5
Technology:
Level: Beginner
Description: Using Merge Sort
Section Algorithm
SubSection Sorting
License: CPOL
</pre>
<!------------------------------- STEP 2 --------------------------->
<!-- Include download and sample image information. -->
<ul class=download>
<li><a href="MergeSort.zip">Download source - 116 Kb</a></li>
</ul>
<p><img src="MergeSort.png"></p>
<!------------------------------- STEP 3 --------------------------->
<!-- Add the article text. Please use simple formatting (<h2>, <p> etc) -->
<h2>Introduction</h2>
<p>Sorting is a common activity in the programming work.<br />
Merge-Sort is one of the best implementation for Sorting, Since Its running on O(nlogn) - which is the best run-time available for Sorting.<br />
On one of my projects I had a requirement to sort Objects.
<br />After a short research, I decided to write a Generic Merge-Sort Class that will work for me.
<br />During the work, I found few major points that should be considered while using that Generic Class for Sorting.
<h2>Background</h2>
<p>Merge Sort (pseudo-code in the picture) is a recursive algorithm, that Split an Array of the Objects to 2 sub Arrays - A,B (which initialize to infinite values), <br />Sort this 2 sub-Arrays and finally merge them. (Therefor, 'merge' sort)
<h2>Using the Code</h2>
<p>For using the Generic Merge Sort, you should (probably) know what is the objects parameter that the objects will be sorted by.<br />
Now, Since the 2 sub-Arrays should be initialized with an infinite value, You should use the default-ctor to make that initialization.<br />
Example: For sorting an Array of 'Persons' Objects that will be sorted according to their ID number (from low to high), <br />you should declare infinite ID-number (infinite int32 value) in the default-ctor.<br />
(I know This is not an elegant implementation, but In that case there is no alternative.)
<pre lang= cs>
class MergeSort
{
/// <summary>
/// Sorts an array of Objects
/// IComparable - use 'CompareTo' to compare objects
/// where T : new() - need to create a new Type 'T' object inside the method
/// </summary>
/// <param name="X"></param>
public static T[] Merge_Sort<T>(T[] X) where T : IComparable, new()
{
int n = X.Length;
X = MegrgeSort_Internal(X, n);
return X;
}
/// <summary>
/// Internal method for sorting
/// </summary>
/// <param name="X"></param>
/// <param name="n"></param>
private static T[] MegrgeSort_Internal<T>(T[] X, int n) where T : IComparable, new()
{
// Define 2 aid Sub-Arrays
T[] A = new T[(n / 2) + 2];
T[] B = new T[(n / 2) + 2];
// Initialize the 2 Sub-Arrays with an infinite 'sorting parameter'
// Therefor, You must include a default ctor in your class
// which will initialize an infinite value - To the sorting parameter
// using 'where T : new()' here
for (int i = 0; i < A.Length; i++)
{
A[i] = new T(); ;
B[i] = new T();
}
// Recursive Stop-Condition, Sorting a Basic Array (Size 2)
if (n == 2)
{
int CompareValue = X[0].CompareTo(X[1]);
if (CompareValue > 0)
{
T tempT = X[0];
X[0] = X[1];
X[1] = tempT;
}
}
else
{
// The Sub-Arrays Size is Large than 2
if (n > 2)
{
int m = n / 2;
// Initialize the 2 Sub-Arrays (The first relevant values)
for (int i = 0; i < m; i = i + 1)
{
A[i] = X[i];
}
for (int j = m; j < n; j++)
{
B[j - m] = X[j];
}
// 2 Recursive Calling, Sorting Sub-Arrays
A = MegrgeSort_Internal(A, m);
B = MegrgeSort_Internal(B, n - m);
// Merging the Sorted Sub-Arrays into the main Array
int p = 0;
int q = 0;
for (int k = 0; k < n; k++)
{
{
int CompareValure = A[p].CompareTo(B[q]);
if (CompareValure == 0 ||
CompareValure == -1)
{
X[k] = A[p];
p = p + 1;
}
else
{
X[k] = B[q];
q = q + 1;
}
}
}
} // if
} // else
return X;
} // MegrgeSort_Internal
}
</pre>
<h2>Points of Interest</h2>
<p>When writing a class for using Generic Merge Sort, you should implement the 'IComparable' interface since the code using the 'CompareTo' function - to compare objects.<br />
You should also write your own 'overloading operators' that will be in use to compare objects: ==, !=, >, >=, <, <= plus 'Equals' and 'GetHashCode'.
<br />Please notice that 'GetHashCode' will be in use by the CLR implicitly - so you must write your own implementation that will return the same value for the same object.
<br />There are 2 project attached:<br />
The first one is a simple (int32) Implementation, that Sorts an Array of Integers.<br />
The Second one is the Generic Merge Sort, Plus a simple 'Person' class that will demonstrate the using of the Generic code.
<p>
<!------------------------------- That's it! --------------------------->
</body>
</html>
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.
Submit an article or tip