Sorting algorithm

Q1: Selection sort
Given an array of integers, sort the elements in the array in ascending order. The selection sort algorithm should be used to solve this problem.

Analysis:
selection sort algorithm sort an unordered array in this way: iterate the unordered array, in each iteration, find the smallest element and swap that element with leftmost element in this iteration

class Solution {
 public:
  vector<int> solve(vector<int> a) {
    //sanity check
    if (a.size() <= 1) return a;
    for (int i = 0; i < a.size()-1; i++) {
      //find the index of the smallest element
      int small = i;
      int j = 0;
      for (j = i+1; j < a.size(); j++) {
        if (a[j] <= a[small]){
          small = j;
        }
      }
      swap(a[i], a[small]);
    }
    return a;
  }
};
time complexity: O(n^2)
space complexity: O(1)
 
Q1-1： selection sort linklist
Given a singly-linked list, where each node contains an integer value, sort it in ascending order. The selectoin sort algorithm should be used to solve this problem.
analysis:
For linklist, the algorithm is as same as selection sort in array. Track the smallest pointer of the node and swap the value of that node with the leftmost node value. 
class Solution {
 public:
  ListNode* selectionSort(ListNode* a) { 
    // write your solution here
    //sanity check
    if (a == NULL || a->next == NULL) return a;
    ListNode *smallest;
    ListNode *p = a;
    while (p->next != NULL) {
      smallest = p;
      ListNode *q = p->next;
      while (q) {
        if (q->value < smallest->value) {
          smallest = q;
        }
        q = q->next;
      }
      int tmp = smallest->value;
      smallest->value = p->value;
      p->value = tmp;
      p = p->next;
    }
    return a;
  }
};
time complexity: O(n^2)
space complexity: O(1)
 

Q2: merge sort
Given an array of integers, sort the elements in the array in ascending order. The merge sort algorithm should be used to solve this problem.
analysis: 


class Solution {
 private:
  vector<int> combine(vector<int> left, vector<int> right) {
    vector<int> rst;
    int i = 0;
    int j = 0;
    while (i < left.size() && j < right.size()) {
      if (left[i] < right[j]) {
        rst.push_back(left[i]);
        i++;
      }else {
        rst.push_back(right[j]);
        j++;
      }
    }
    while (i < left.size()) {
      rst.push_back(left[i++]);
    }
    while (j < right.size()) {
      rst.push_back(right[j++]);
    }
    return rst;
  }
  vector<int> Merge(vector<int> array, int left, int right) {
    vector<int> solution;
    if (left > right) return solution;
    if (left == right) {
      solution.push_back(array[left]);
      return solution;
    }
    int mid = left + (right - left)/2;
    vector<int> left_solu = Merge(array, left, mid);
    vector<int> right_solu = Merge(array, mid+1, right);
    solution = combine(left_solu, right_solu);
    return solution;
  }
 public:
  vector<int> mergeSort(vector<int> array) {
    // Write your solution here
    //base case
    if (array.size() <= 1) return array;
    return Merge(array, 0, array.size()-1);
  }
};
Time complexity: O(nlogn)
split the array into half and half,  the height of  the recursion tree is logn, in each level of the tree, time complexity of merging two array is n, the total time complexity is O(nlogn).

space complexity: O(n)
for vector array, need space to store the temporary result, such as storing left half and right half of the array and when combining two sorted array, need extra space to store the result.

Q2-2: merge sort linklist
Given a singly-linked list, where each node contains an integer value, sort it in ascending order. The merge sort algorithm should be used to solve this problem.

analysis:
the algorithm is the same as mergesort in array. To find the middle of the linklist, we use fast-slow pointers. The difference between array and linklist is that space complexity in linklist is O(1)

class Solution {
 private:
  ListNode* merge(ListNode* l1, ListNode* l2) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;
    ListNode* p1 = l1;
    ListNode* p2 = l2;
    ListNode* head = new ListNode(0);
    ListNode* cur = head;
    while (p1 != NULL  && p2 != NULL) {
      if (p1->value < p2->value) {
        cur->next = p1;
        cur = p1;
        p1 = p1->next;
      } else {
        cur->next = p2;
        cur = p2;
        p2 = p2->next;
      }
    }
    if (p1 != NULL) {
      cur->next = p1;
    }
    if (p2 != NULL) {
      cur->next = p2;
    }
    return head->next;
  }
 public:
  ListNode* mergeSort(ListNode* a) {
    // write your solution here
    //sanity check
    if (a == NULL || a->next == NULL) return a;
    //find middle node
    ListNode* slow = a;
    ListNode* fast = a;
    while (fast->next != NULL && fast->next->next != NULL) {
      fast = fast->next->next;
      slow = slow->next;
    }
    ListNode* mid = slow;
    ListNode* right = mid->next;
    mid->next = NULL;
    ListNode* left = a;
    ListNode* left_solu = mergeSort(left);
    ListNode* right_solu = mergeSort(right);
    return merge(left_solu, right_solu);
  }
};
time complexity: O(nlogn)
space complexity: O(1)

Q3:quick sort
Given an array of integers, sort the elements in the array in ascending order. The quick sort algorithm should be used to solve this problem
analysis:
quick sort try to find the right position for each element. When the first element find its position, that position is called pivot. Recursively, we can do this algorithm for all the elements in leftside and rightside of the pivot. How to find the right position for an element? Use two boarders to swap elements so that the elements are in the right position:
boarder i: left side of i is elements smaller than pivot element
boarder j: right side of j is elements larger than pivot element
position between i and j are to be discovered.

class Solution {
 private:
  void swap(vector<int> &array, int i, int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
  }
  int pivot(vector<int> &array, int left, int right) {
    //swap left and right
    swap(array, left, right);
    int i = left;
    int j = right;
    while (i < j) {
      if (array[i] < array[right]) {
        i++;
      }else {
        j--;
        swap(array, i, j);
      }
    }
    swap(array, right, i);
    return i;
  }
  void quick(vector<int> &array, int left, int right) {
    //base case
    if (left >= right) return;
    int pivot1 = pivot(array, left, right);
    quick(array, left, pivot1-1);
    quick(array, pivot1+1, right);
  }
 public:
  vector<int> quickSort(vector<int> array) {
    //sanity check
    if (array.size() <= 1) {
      return array;
    }
   quick(array, 0, array.size()-1);
    return array;
  }
};
time complexity: O(n^2)
worst case is when the array is sorted, in each iteration, all elements have to be swapped. 

space complexity: O(1)

Q3-1: quick sort linklist
Given a singly-linked list, where each node contains an integer value, sort it in ascending order. The quick sort algorithm should be used to solve this problem.
analysis:
the algorithm is slightly different from quicksort for array because it's hard to use boarders to swap elements in linklist to find the right position for pivot element. But we can iterate the whole linklist to find all elements that are smaller than the pivot element and all elements that are larger than the pivot element.

class Solution {
 public:
  ListNode* quickSort(ListNode* a) {
    //sanity check
    if (a == NULL || a->next == NULL) return a;
    //find a pivot
    ListNode* pivot = a;
    //find the linklist smaller than a->value
    //find the linklist larger than a->value
    ListNode* small = new ListNode(0);
    ListNode* cur1 = small;
    ListNode* large = new ListNode(0);
    ListNode* cur2 = large;
    ListNode* p = a;
    while (p != NULL) {
      if (p->value < pivot->value) {
        cur1->next = p;
        cur1 = p;
      }else if (p->value > pivot->value) {
        cur2->next = p;
        cur2 = p;
      }
      p = p->next;
    }
    cur1->next = NULL;
    cur2->next = NULL;
    ListNode* s_solu = quickSort(small->next);
    ListNode* l_solu = quickSort(large->next);
    //merge two linklist
    if (s_solu == NULL) {
      pivot->next = l_solu;
      return pivot;
    }
    cur1 = s_solu;
    while (cur1->next) {
      cur1 = cur1->next;
    }
    cur1->next = pivot;
    pivot->next = l_solu;
    return s_solu;
  //  return a;
  }
};
time complexity: O(n^2)
space complexity: O(1)



Q4: Rainbow sort
Given an array of balls, where the color of the balls can only be Red, Green or Blue, sort the balls such that all the Red balls are grouped on the left side, all the Green balls are grouped in the middle and all the Blue balls are grouped on the right side. (Red is denoted by -1, Green is denoted by 0, and Blue is denoted by 1).

analysis:
This problem is similar to array shuffling, rearranging the array by swapping elements. 3 boarders can be used to solve this problem:
1. left side of boarder i is -1
2. right side of boarder j is 1
3. boarder k between i and j is 0
4. position between k and j is to be discovered
initial position: since the unknown position is the whole array, i=k=0 and j = array.size()-1. Treat k as the explored position, if a[k] == 1, swap k and j, j--, else if a[k] == -1, swap k, i, k++,i++, else k++

class Solution {
 public:
  vector<int> rainbowSort(vector<int> a) {
    //sanity check
    if (a.size() <= 1) return a;
    int i = 0;
    int k = 0;
    int j = a.size()-1;
    while (k <= j) {
      if (a[k] == 1) {
        swap(a[k], a[j]);
        j--;
      }else if (a[k] == -1) {
        swap(a[k], a[i]);
        i++;
        k++;
      }else {
        k++;
      }
    }
    return a;
  }
};
time complexity: O(n)
space complexity: O(1)