Heap Sort

What is a Heap?
- Consider the case of ascend sorting, Heap is defined as an array of element a_l , a_l+1 ...a_r that satisfy: ∀ i belong to [l,r] and i starts from 0
  

1/.	ai  >= a2i +1
2/.	ai  >= a2i+2     {(ai , a2i +1), (ai ,a2i+2) is a pair of joint elements}

-  If  a_l , a_l+1 ...ar is a Heap,  a_l is the largest element


Algorithm:
- Phase 1: Adjust the initial array to heap (from the middle element of the array)
- Phase 2: Sort the array base on heap

• Step 1: move the largest element to the end of the array
• Step 2:
  + Exclude the largest element out of heap: r = r-1 
  + Adjust the remain of array
• Step 3: Compare r and l:
  + If r > l, repeat step 2
  + Else: stop

Implementation:
        public static void HeapSort (double[] list)
        {
            CreateHeap(list);         
            for (int i = list.Length - 1; i >= 1; i--)
            {
                double Temp = list[0];
                list[0] = list[i];
                list[i] = Temp;              
                Shift (list, 0, i - 1);
            }           
        }
       
        private static void CreateHeap(double []a)
        {         
            for (int i = (a.Length - 1) / 2; i >= 0; i--)
                Shift(a, i, a.Length - 1);
        }

        static void Shift(double[] a, int left, int right)
        {
            int curr = left;
            int joint = 2 * curr + 1;
            double x = a[curr];

            while (joint <= right)
            {
                if (joint < right)
                { 
                    if (a[joint] < a[joint + 1])
                    {
                        joint = joint + 1;
                    }
                }
                if (a[joint] < x)
                {
                    break;
                }
                a[curr] = a[joint];
                curr = joint;
                joint = 2 * curr + 1;
            }
            a[curr] = x;
        }
         
Hope this help!

Read more »

Selection Sort

Idea: 
- Select the smallest element and move to the first position of current array
- Consider the number of elements of  the current array is n-1
- Repeat the two above steps until the number of elements of the current array is 1

Algorithm:
- Step 1: Assign i =0
- Step 2: Loop
       + Look for a[min] from a[i] to a[n-1]
       + Swap a[min] and a[i]
- Step 3: Compare i and n
       + If i <=: i + 1, repeat step 2
       + On the contrary: Stop

Implementation
        static void Swap(ref int a, ref int b)
        {
            int c = a;
            a = b;
            b = c;
        }

        static void SelectionSort(int[] a)
        {
            int max;
            for (int i = 0; i < a.Length - 1; i++)
            {                 
                max = i;
                for (int j = i + 1; j < a.Length; j++)
                {                     
                    if (a[j] > a[max])
                    {
                        max = j;
                    }
                }
                 if (max != i)
                {
                    Swap(ref a[max], ref a[i]);
                }
            }           
        }


Hope this help!

Read more »