Sort

sorting

Selection Sort:

• two pointers: from the beginning point i = 0 which is first round. j = i+1, which record the minIndex each round, swap i with minIndex, then i++.

public int[] selectSort(int[] arr){
    if(arr == null || arr.length <= 1) return arr;
    for(int i = 0; i < arr.length - 1; i++){
        int minIndex = i;
        for(int j = i+1; j < arr.length; j++){
            minIndex = arr[minIndex] > arr[j] ? j : minIndex;
        }
        swap(arr, minIndex, i);
    }
    return arr;
}

• i don't need to move to the last Index.

• minIndex should be create outside of j loop

• always compare minIndex with j

• TC: O(n^2), use minHeap to optimize.

Merge Sort:

• stable ? exampLe: 0 1a 1b 1c 2 3

  • before merging , 0 is at left of 2, after, still at 2's left

  • before, 1a is at left of 1b, after, still at left

• ArrayList:

  • TC: nlogn + O(n) + nlogn

  • SC: O(n)

public List<Integer> mergerSort(ArrayList<Integer> list){
    if(list == null || list.size() == 0) return null;
    ArrayList<Integer> sortedArray = sort(list, 0, list.size()-1);
    return sortedArray;   
}
public List<Integer> sort(ArrayList<Integer> list, int left, int right){
    List<Integer> res = new ArrayList<>();
    if(left == right){
        res.add(list.get(left));
        return res;
    }
    int mid = left + (right - left)/2;
    ArrayList<Integer> leftRes = sort(list, left, mid);
    ArrayList<Integer> rightRes = sort(list, mid+1, right);
    return merger(leftRes, rightRes);
}
public List<Integer> merge(ArrayList<Integer> left, ArrayList<Integer> right){
    left.addAll(right);
    Collections.sort(left);
}

• Array:

  • TC: nlogn + O(n) + nlogn

  • SC: O(n)

public int[] mergeSort(int[] array){
    //cc
    int[] helper = new int[array.length];
    sort(array, 0, array.length-1, helper);
    return array;
}
public int[] sort(int[] array, int left, in right, int[] helper){
    if(left == right) return;
    int mid = left + (right - left) /2;
    sort(array, left, mid, helper);
    sort(array, mid+1, right, helper);
    merge(array, left, mid, right, helper);
}
public int[] merge(int[] array, int left, int mid, int right, int[] helepr){
    int leftStart = left, rightStart = mid+1;
    for(int i = left; i <= right; i++){
        helper[i] = array[i];
    }
    while(leftStart <= mid && rightStart <= right){
        if(helper[leftStart] <= helper[rightStart]){
            array[left++] = helper[leftStart]++;
        }else{
            array[left++] = helper[rightStart]++;
        }
    }
    while(leftStart <= mid){
        array[left++] = helper[leftStart++];
    }
}

Quick Sort:

• find the pivot value to compare with left and right. if left > pivot and right < pivot, switch left and right, then left++, right --;