Introduction to Sorting

• Insertion sort
  • Cocktail Shaker Sort
  • MergeSort
  • QuickSort
  • LSD Radix Sort
  • Open address Hashmap

Insertion sort#

public static void insertionSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int j = i;
        // Move an element at `j` backward into the correct descending position
        while (j > 0 && array[j] > array[j - 1]) {
            //swap
            int temp = array[j];
            array[j] = array[j - 1];
            array[j - 1] = temp;
            j--; // Decrement to check previous elements
        }
    }
}

PS: Use the conditional loop to simplify the loop.

Cocktail Shaker Sort#

public static void cocktailSharkerSort(int[] array){
  // this method makes the array sorted in the decending
  int startIndex = 1;
  int endIndex = array.length - 1; 
  while(startIndex < endIndex){
    //Forwards
    int lastSwappedIndex = startIndex;
    //for Loop one
    for(int i = startIndex; i < endIndex; i++ ){
      if(array[i] < array[i + 1]){
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        lastSwappedIndex = i; // this index shouldn't be i + 1
      } else {
        continue;
      }
    }
    endIndex = lastSwappedIndex;
    // if the array is sorted right now, we break the loop.
    if(lastSwappedIndex == startIndex){
      break;
    }
    
    //Backwards
    lastSwappedIndex = endIndex;
    //for loop two
    for(int i = endIndex; i> start;i--){
      if(array[i - 1] < array[i]){
        lastSwappedIndex = i; // this index shouldn't be i - 1
        int temp = array[i];
        array[i] = array[i - 1];
        array[i - 1] = temp;
      }
    }
    startIndex = lastSwappedIndex;
    if(lastSwappedIndex == endIndex){
      break;
    }
    
  }
  
}

The thing worth the attention in the cocktail shaker method is:

• The lastSwappedIndex should only be set to i each time. Because the swapped one is the one we are sure to be in the correct position.
• Compare after each loop and set the startIndex/endIndex ~!

MergeSort#

public static void mergeSort(int[] array){
  if(array.length == 1){
    //ending condition of the recursion
    return;
  }
  // seperate the current array to left and right
  int mid = array.length / 2;
  int[] left = new int[mid];
  int[] right = new int[array.length - mid];
  for(int i = 0; i < mid; i++){
    left[i] = array[i];
  }
  for(int j = mid; j< array.length ; j++){
    right[j - mid] = array[j];
  }
  mergeSort(left);
  mergeSort(right);
  
  int leftIndex = 0;
  int rightIndex = 0;
  int overallIndex = 0; //this is the index of the current array
// use the length as the bound condition
  while(leftIndex < left.length && rightIndex < right.length){
    // the condition has to include the <=, or it won't work.
    if(left[leftIndex] <= right[rightIndex]){
      array[overallIndex++] = left[leftIndex ++];
    } else {
      array[overallIndex++] = right[rightIndex ++];
    }	
  }
  
  while(leftIndex < left.length){
    	array[overallIndex ++] = left[leftIndex ++];
  }
  while(rightIndex < right.length){
    	array[overallIndex ++] = right[rightIndex ++];
  }
}

1. A thing worth noting is that this sorting uses a lot of time generating left and right array. This is worth it since you have t

QuickSort#

public static void quickSort(int[] array, int startIndex, int endIndex) {
    if (startIndex >= endIndex) return; // Base case

    Random rand = new Random();
    int pivotIndex = rand.nextInt(endIndex - startIndex + 1) + startIndex;
    int pivot = array[pivotIndex];

    // Swap pivot to start
    swap(array, startIndex, pivotIndex);

    int i = startIndex + 1;
    int j = endIndex;

  // this while loop ensures that the order arround the pivot is correct.
    while (i <= j) {
        while (i <= j && array[i] <= pivot) i++; //if is already smaller, we move forward
        while (i <= j && array[j] > pivot) j--;// if is bigger, we move forward
        if (i <= j) {													// if is in the wrong order according to the pivot, then we change their position.
            swap(array, i, j);
            i++;
            j--;
        }
    }

    // Place pivot in correct position (at j)
    swap(array, startIndex, j);

    // Recursive calls with updated indices
    quickSort(array, startIndex, j - 1);
    quickSort(array, j + 1, endIndex);
}

private static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

1. Why do we need recursion here? Why can’t we just use a for-loop and traverse everything?

   Essentailly we need to sort the two seperate list on both left and right, for code simplicity, the best strategy is to use recursion.

2. Why do we need the pivotIndex to be randomly generated?

   Because random number allow the existence of a relatively big left and right array, so that it would promote the advantage of using two pointer(i,j)

LSD Radix Sort#

public static void LSDRadixSort(int[] array) {
    if (array.length == 0) return;

    // Initialize 10 buckets for digits 0-9.
    // The real algorithm has 19 buckets which implement 19 bucket accounting for the negatice numbers.
    final int RADIX = 10;
    Queue<Integer>[] buckets = new LinkedList[RADIX];
    for (int i = 0; i < RADIX; i++) {
        buckets[i] = new LinkedList<>();
    }

    // Find the maximum number to determine the number of passes (digits)
    int max = array[0];
    for (int num : array) {
        if (num > max) max = num;
    }
  	int maxDigit = 0;
    while(max > 0){
      max /= 10;
      maxDigit ++;
    }
    int base = 10;
    for (int digitIndex = 0; digitIndex < k; digitIndex++) {
        // Distribute elements into buckets based on the current digit
        for (int num : array) {
            int divisor = base / 10; // Isolate the current digit (LSD first)
            int digit = (num / divisor) % 10;
            buckets[digit].add(num); // Add to the corresponding bucket
        }

        // Collect elements back into the array in order (0-9)
        int index = 0;
        for (Queue<Integer> bucket : buckets) {
            while (!bucket.isEmpty()) {
                array[index++] = bucket.poll();
                // In the stack way for in-place sorting
            }
        }

        base *= 10; // Move to the next digit (e.g., 10 → 100)
    }
}

1. Why do we need 19 buckets?

   From -9 to +9, though, we don’t care about the negative part in this implementation.

2. Why do we need the stack implementation for each bucket?

   This is because we want an in-place implementation.

Open address Hashmap#

Probably the hardest method to implement in the open address hashmap is put method. We just going to implement this method simply. Also, we are not digging into the complex theory of choosing the correct hash function, so our hash function is just .hashcode % array.length.

Function overall organization:

whileLoop

• Same key condition
  • isRemoved : set firstRemoved
  • replace the current value
• Process that each loop has to experience
  • ! isRemoved: noInfinite ++
  • isRemoved: set firstRemoved

endWhile

    public static final int INITIAL_CAPACITY = 13;
    public static final double MAX_LOAD_FACTOR = 0.67;
    private LinearProbingMapEntry<K, V>[] table;
    private int size;

public V remove(K key, V value){
  //if the load factor is greater than the MAX_LOAD_FACTOR, then expand the list
  if((double)(size/table.length > MAX_LOAD_FACTOR){
    resize(table.length * 2 + 1);
  }
  int hash = Math.abs(key.hashcode() % table.length);
  int firstRemoved = -1;
  int noInfinite = 0; // to limit the loop to go for ever.
  while(table[hash] != null && noInfinite < size){
    if(table[hash].equals(key)){
      if(!isRemoved()){
        // we got it
        V returnValue = table[hash].getValue();
        table[hash].setValue(value);
        return returnValue;
      }
      
    }
    if(!table[hash].isRemoved()){
      //this is a real element and 
      //we need to check whether we have an infinite loop with noInfinite.
      noInfinite ++;
    } else {
        // we found the first removed place
        // but wait, we don't want duplicate key in the list,
        // so we only record the first Removed position.
      if(firstRemoved == -1){
        fisrtRemoved = hash;
      }
    }
    // increase the hash;
    hash = (hash + 1)%table.length;
  }
  //out of the loop
 	// make the final judgement.
  if (firstRemoved != -1) {
      table[firstRemoved] = new LinearProbingMapEntry<>(key, value);
      ++size;
      return null;
  }
  table[hash] = new LinearProbingMapEntry<>(key, value);
  ++size;
  return null;
  
}