Randomized Quick-sort

Quick-sort is another type of comparison sorting algorythm. It's much better than other comparing algorythms cause it doesn't require additional space for its work (unlike merge sort for example). It also has a good time of work in average case - O(n lgn) - that is best time for every comparing algorytm as you know. It's also has asymptotic n^2 time of work in worst case, that occurs rarely. Using randomization at the each step of algorytm helps to avoid receiving "pre-defined worst case", when our solution gives us worst time on a particular sequence. Here is an implementation of randomized qucik-sort: Show/Hide

1:  using System;  
2:  using System.Collections.Generic;  
3:  using System.Linq;  
4:  using System.Text;  
5:  namespace QuickSort  
6:  {  
7:       public class SortManager  
8:       {  
9:            public int[] Sort(int[] data)  
10:            {  
11:                 try  
12:                 {  
13:                      SortRange(data, 0, data.Length - 1);  
14:                 }  
15:                 catch (Exception ex)  
16:                 {  
17:                      int a = 1;  
18:                 }  
19:                 return data;  
20:            }  
21:            public void SortRange(int[] data, int startIndex, int endIndex)  
22:            {  
23:                 if (startIndex >= endIndex) return;  
24:                 int rangeLen = endIndex - startIndex + 1;  
25:                 Random rnd = new Random();  
26:                 int randomIndex = rnd.Next(rangeLen - 1) + startIndex;  
27:                 int val = data[randomIndex];  
28:                 data[randomIndex] = data[endIndex];  
29:                 data[endIndex] = val;  
30:                 int temp = 0;  
31:                 int j = startIndex;  
32:                 bool isRangeEqual = true;  
33:                 for (int i = startIndex; i <= endIndex; i++)  
34:                 {  
35:                      if (data[i] != val) isRangeEqual = false;  
36:                      if (data[i] < val)  
37:                      {  
38:                           temp = data[j];  
39:                           data[j] = data[i];  
40:                           data[i] = temp;  
41:                           j++;  
42:                      }  
43:                 }  
44:                 if (isRangeEqual) return;  
45:                 SortRange(data, startIndex, j - 1);  
46:                 SortRange(data, j, endIndex);  
47:            }  
48:       }  
49:  }  

Lines 35 and 44 are a small cheat cause i can't understand how it should behaves when all items in the input are equal. I alse add some test to view how it works

1:  using System;  
2:  using System.Text;  
3:  using System.Collections.Generic;  
4:  using System.Linq;  
5:  using NUnit;  
6:  using NUnit.Framework;  
7:  using Karn.PerfomanceLibrary;  
8:  namespace QuickSort.Fixture  
9:  {  
10:       /// <summary>  
11:       /// Summary description for UnitTest1  
12:       /// </summary>  
13:       public class SortManagerTest  
14:       {  
15:            private Observer watches = new Observer();  
16:            public SortManagerTest()  
17:            {  
18:                 //  
19:                 // TODO: Add constructor logic here  
20:                 //  
21:            }  
22:            [Test]  
23:            public void SortCommonOrder()  
24:            {  
25:                 //  
26:                 // TODO: Add test logic     here  
27:                 //  
28:                 var manager = new SortManager();  
29:                 watches.Start("SortCommonOrder");  
30:                 var input = new[] { 9, 13, 2, 6, 19, 8, 24, 49, 3, 33, 27, 16, 11 };  
31:                 int[] data = manager.Sort(input);  
32:                 watches.Stop("SortCommonOrder");  
33:                 Assert.IsTrue(watches["SortCommonOrder"].ElapsedMilliseconds < 100);  
34:                 Assert.IsTrue(input.Length == data.Length);  
35:                 Assert.IsTrue(checkDataSorted(data));  
36:            }  
37:            [Test]  
38:            public void SortEqualOrder()  
39:            {  
40:                 var manager = new SortManager();  
41:                 watches.Start("SortEqualOrder");  
42:                 var input = new[] { 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 };  
43:                 int[] data = manager.Sort(input);  
44:                 watches.Stop("SortEqualOrder");  
45:                 Assert.IsTrue(watches["SortEqualOrder"].ElapsedMilliseconds < 100);  
46:                 Assert.IsTrue(input.Length == data.Length);  
47:                 Assert.IsTrue(checkDataSorted(data));  
48:            }  
49:            [Test]  
50:            public void SortSorted()  
51:            {  
52:                 var manager = new SortManager();  
53:                 watches.Start("SortSorted");  
54:                 var input = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 };  
55:                 int[] data = manager.Sort(input);  
56:                 watches.Stop("SortSorted");  
57:                 Assert.IsTrue(watches["SortSorted"].ElapsedMilliseconds < 100);  
58:                 Assert.IsTrue(input.Length == data.Length);  
59:                 Assert.IsTrue(checkDataSorted(data));  
60:            }  
61:            [Test]  
62:            public void SortUnsorted()  
63:            {  
64:                 var manager = new SortManager();  
65:                 watches.Start("SortUnsorted");  
66:                 var input = new[] { 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };  
67:                 int[] data = manager.Sort(input);  
68:                 watches.Stop("SortUnsorted");  
69:                 Assert.IsTrue(watches["SortUnsorted"].ElapsedMilliseconds < 100);  
70:                 Assert.IsTrue(input.Length == data.Length);  
71:                 Assert.IsTrue(checkDataSorted(data));  
72:            }  
73:            bool checkDataSorted(int[] data)  
74:            {  
75:                 if (data.Length <= 1) return true;  
76:                 for (int i = 1; i < data.Length; i++)  
77:                 {  
78:                      if (data[i] < data[i - 1]) return false;  
79:                 }  
80:                 return true;  
81:            }  
82:       }  
83:  }