Sort

void main() {
//   List letters = ['a','b','r','g','j'];
//   List basket = [1,3,4,67,78,4,3,4,9];
   
//     basket.sort();
//     print(basket);
    
    dynamic numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

 bubbleSort(array) {
     for(var i = 0; i < array.length-1; i++){
         for(var j = 1+i; j < array.length; j++){
           if(array[i] > array[j]){
               int temp = array[i];
               array[i] = array[j];
               array[j] = temp;
           }
         }
     }
    //Code here
}

 selectionSort(array) {
    int smallestItemindex = 0;
     for(var i = 0; i < array.length-1; i++){
          // Set current index as minimum
        int min = i;
        int temp = array[i];
         for(var j = 1+i; j < array.length; j++){
           if(array[j] < array[min]){
               
           min = j;
            
           }
         }
         //frist item updated with the lowest in the list 
         array[i] = array[min];
         //then the first item shifts to the position where the smallest number was remove from then loop to the second array in the list
         array[min] = temp;
         
         
     }
    //Code here
}


insertionSort(array) {
    for(var i = 0; i < array.length; i++){
      
      // if current element is less than the first element then remove from the index and insert at the first index
        if(array[i] < array[0]){
           array.insert(0, array.removeAt(i));
        }else{
        // else loop through the current sorted array and check where current index is greater 
        //than the previous element and less than the next element 3 56 current index = 4 so here 4 is 
        //greater than 3 and less than 5 so it will enter inbetween them
            for(var j = 1; j< i; j++){
                // 
                if(array[i] > array[j-1] && array[i]< array[j]){
                    array.insert(j, array.removeAt(i));
                }
            }
        }
      
    }

   
}

 merge(left, right){
    // compare the left and right array and insert where suppose
    // just take it as the left and right is not sorted 
    // you can think it as [1 2] and [4 3] as your first input 
   int i = 0;
    int j= 0;
    List arr =[];
    
    while(i < left.length && j < right.length ){
        //compare the first item in the left and right array 
        if(left[i] < right[j] ){
            // swap if the left is greater than the right 
            arr.add(left[i]);
           
            i++;
        }else{
            arr.add(right[j]);
            j++;
        }
    }
      // Add remaining elements
  arr.addAll(left.sublist(i));
  arr.addAll(right.sublist(j));
    
  return arr;
}

 mergeSort (array) {
  if (array.length == 1) {
    return array;
  }
  // Split Array in into right and left
// return for each recursion the sorted and merge
// see the left and right as an array
 dynamic length = array.length;
 
  int mid = array.length ~/ 2; // Find middle index
  List left = mergeSort( array.sublist(0, mid)); // First half
  List right = mergeSort(array.sublist(mid)); // Second half
  
  return merge(
    left,
    right
  );
}



void quickSort(List<int> array, int left, int right) {
  if (left < right) {
    int partitionIndex = partition(array, left, right);
    
    quickSort(array, left, partitionIndex - 1);
    quickSort(array, partitionIndex + 1, right);
  }
}

int partition(List<int> array, int left, int right) {
  int pivot = array[right]; // Choose last element as pivot
  int partitionIndex = left;

  for (int i = left; i < right; i++) {
    if (array[i] < pivot) {
      swap(array, i, partitionIndex);
      partitionIndex++;
    }
  }
  
  swap(array, partitionIndex, right); // Move pivot to correct position
  return partitionIndex;
}

void swap(List<int> array, int i, int j) {
  int temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}


dynamic answer = mergeSort(numbers); 
print(answer); 



// insertionSort(numbers);
// print(numbers);


// #1 - Sort 10 schools around your house by distance: insertion sort

// #2 - eBay sorts listings by the current Bid amount:raddix or counting -- a fixed length of intehers based on amount 

// #3 - Sport scores on ESPN:  quick sort because of different sports and memory in consideeration

// #4 - Massive database (can't fit all into memory) needs to sort through past year's user data:  quick sort

// #5 - Almost sorted Udemy review data needs to update and add 2 new reviews: insertion sort based on its almost sorted

// #6 - Temperature Records for the past 50 years in Canada: quick sort

// #7 - Large user name database needs to be sorted. Data is very random: merge sort

// #8 - You want to teach sorting for the first time: reddix
}