Advertisement
Guest User

Clean MergeSort attempt 2

a guest
Jan 19th, 2014
20
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 3.52 KB | None | 0 0
  1. ///////////////////////////////////////////////////////////////////////////////////////// CLASS
  2. public class MergeSort
  3. {
  4.     private int[] toSort;
  5.        
  6.     public MergeSort(int[] toSort)
  7.     {
  8.         this.toSort = toSort;
  9.     }
  10.    
  11.     public int[] Sort()
  12.     {
  13.         int[] sorted = new int[toSort.Length];
  14.         int[] tmp = new int[toSort.Length];
  15.         int firstIndex = 0;
  16.         int lastIndex = toSort.Length - 1;
  17.        
  18.         new MergeSortInternal(toSort, firstIndex, lastIndex, sorted, tmp).Sort();  
  19.        
  20.         return sorted;
  21.     }
  22. }
  23.  
  24. ///////////////////////////////////////////////////////////////////////////////////////// CLASS
  25. class MergeSortInternal
  26. {
  27.     private int[] toSort;
  28.     private int[] sorted;
  29.     private int[] tmp;
  30.  
  31.     private int leftIndex, rightIndex;
  32.  
  33.     public MergeSortInternal(int[] toSort, int firstElementIndex, int lastElementIndex, int[] sorted, int[] tmp)
  34.     {
  35.         this.toSort = toSort;
  36.         this.sorted = sorted;
  37.         this.tmp = tmp;
  38.         this.leftIndex = firstElementIndex;
  39.         this.rightIndex = lastElementIndex;
  40.     }
  41.  
  42.     public void Sort()
  43.     {
  44.         if(OnlyOneElement())
  45.             SortOneElementList();
  46.         else
  47.             RecursivelySortBothHalfsOfTheArrayAndMerge();
  48.     }
  49.  
  50.     private bool OnlyOneElement()
  51.     {
  52.         return leftIndex == rightIndex;
  53.     }
  54.    
  55.     private void SortOneElementList()
  56.     {
  57.         sorted[leftIndex] = toSort[leftIndex];
  58.     }
  59.    
  60.     private void RecursivelySortBothHalfsOfTheArrayAndMerge()
  61.     {
  62.         SplitSortArray splitArray = new SplitSortArray(toSort, leftIndex, rightIndex, sorted, tmp);    
  63.         splitArray.SortLeftPart();
  64.         splitArray.SortRightPart();
  65.         splitArray.MergeSortedArrays();
  66.     }
  67. }
  68.  
  69. ///////////////////////////////////////////////////////////////////////////////////////// CLASS
  70. public class SplitSortArray
  71. {
  72.     int[] toSort;
  73.     int[] splitArray;
  74.     int[] sorted;  
  75.    
  76.     int leftSideStart;                 
  77.     int leftSideEnd;
  78.     int rightSideStart;
  79.     int rightSideEnd;
  80.    
  81.     int leftCursor;
  82.     int rightCursor;
  83.    
  84.     public SplitSortArray(int[] toSort, int firstElementIndex, int lastElementIndex, int[] sorted, int[] tmp)
  85.     {
  86.         this.toSort = toSort;
  87.         this.splitArray = tmp;
  88.         this.sorted = sorted;
  89.        
  90.         this.leftSideStart = firstElementIndex;
  91.         this.rightSideEnd = lastElementIndex;
  92.        
  93.         SplitInTheMiddle();
  94.     }
  95.    
  96.     private void SplitInTheMiddle()
  97.     {
  98.         int middle = (leftSideStart + rightSideEnd) / 2;
  99.         this.leftSideEnd = middle - 1;
  100.         this.rightSideStart = middle;  
  101.     }
  102.    
  103.     public void SortLeftPart()
  104.     {
  105.         new MergeSortInternal(toSort, leftSideStart, leftSideEnd, splitArray, sorted).Sort();
  106.     }
  107.    
  108.     public void SortRightPart()
  109.     {
  110.         new MergeSortInternal(toSort, rightSideStart, rightSideEnd, splitArray, sorted).Sort();
  111.     }
  112.    
  113.     public int[] MergeSortedArrays()
  114.     {
  115.         leftCursor = leftSideStart;
  116.         rightCursor = rightSideStart;
  117.        
  118.         for (int i = leftSideStart; i < rightSideEnd; i++)
  119.         {
  120.             if(IsLeftSideEmpty())
  121.                 sorted[i] = TakeElementFromRightSide();
  122.             else if(IsRightSideEmpty())
  123.                 sorted[i] = TakeElementFromLeftSide();
  124.             else if(IsLeftElementSmaller())
  125.                 sorted[i] = TakeElementFromLeftSide();
  126.             else
  127.                 sorted[i] = TakeElementFromRightSide();
  128.         }
  129.        
  130.         return sorted;
  131.     }
  132.    
  133.     private bool IsRightSideEmpty()
  134.     {
  135.         return rightCursor > rideSideEnd;
  136.     }
  137.    
  138.     private bool IsLeftSideEmpty()
  139.     {
  140.         return leftCursor > leftSideEnd;
  141.     }
  142.  
  143.     private bool IsLeftElementSmaller()
  144.     {
  145.         return tmp[leftCursor] < tmp[rightCursor];
  146.     }
  147.    
  148.     private int TakeElementFromLeftSide()
  149.     {
  150.         int result = tmp[leftCursor];
  151.         leftCursor++;
  152.         return result;
  153.     }
  154.    
  155.     private int TakeElementFromRightSide()
  156.     {
  157.         int result = tmp[rightCursor];
  158.         rightCursor++;
  159.         return result;
  160.     }
  161.  
  162. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement