Messed array k step away - mocking experience scrip - 30 minutes read/ write, conversation and talk, and more

MessedArrayKStepAway.cs

using System;
///
/// n = 10, k =2, index 6, 4, 5, 6,7 or 8 
// 1 - 10 sort ascending order 
// mess up, k = 2, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
// index = 0, 1 -> index = 1, index = 2
// index = 4, in the middle   [index -2, index +2], at most 5 positions for each number
// arr length n -> k places alawys -> sort the array 
// element -> brute force, 5 element, ascending order find minimum number, left -> right
// check right, not left, left side is already sorted, 
// 1 2 3 4 5
// k = 2
// 3 2 1 5 4
// find elment starting 0, 3, 2, 1, find min one 1, 
// swap 1,2 3, 5, 4 -> 1 is sorted, work on 2, right side, 2, 3, 5, find minimum one -> 2
// 1, 2, [3,5,4], 
// 1, 2, 3, O(kn)  algorithm, right side only, k is much smaller than n, still efficent, k = 2, n 1000000 -
// k is close to n -> O(nn)  - k neighbor o(nlogn)
// space trade time complexity -> [5,4,3] -> 5 v 4, reverse first,
// how to find minimum number, 5 vs 4, swap , 4 vs 3 , swap, bubble sort
// [5,4,3] 
// n = 1 million, k = 10, how to find small one in 10 numbers, O(kk)  o(klogk) O(k)
// selection sort, heap sort -> complete sort, binary tree, max/ min 
// keep k in a heap, heap should be min-heap, -> O(logk) find sort, insert/
// array to implment, heap. 
// 3 2 1 5 4
// put first k number in a min-heap, -> extra top one - min
// iterate the array from k+1 to n 
// pop min 
// add new elment into end of heap
// go to next iteration  
// 

class SaturdayPractice {
   static void Main(string[] args) {
      Console.WriteLine("Learning starts from real conversation");
      
      
   }
   
   /// k = 2, array size is 10 
   public static void SortUsingHeapForKMessArray(int[] numbers, int k)
   {
      if( k <= 0 || numbers == null || numbers.Length == 0)   return; 
      
      // build a heap 
      var heap = new MinHeap(); 
      int length = numbers.Length; 
      int heapSize = Math.Min(length, k); 
      for( int i = 0; i < heapSize; i++)
      {
         var current = numbers[i];
         heap.Insert(current); 
      }
      
      int index = 0; 
      for(int i = heapSize; i < length; i++)
      {
         var pop = heap.Pop(); 
         
         numbers[index++] = pop; 
         
         var currrent = numbers[i];
         heap.Add(current);          
      }
      
      // still have at most k number in the heap
      // continue to empty heap, no insertion 
      while(heap.Count > 0)
      {
         var pop = heap.Pop(); 
         numbers[index++] = pop; 
      }
      
      // in place, not return 
   }
}