chapter4-merge-sort.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Loading Libraries\n",
    "\n",
    "Let's import all the necessary packages first. You can safely ignore this section."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import java.util.Random;\n",
    "import java.lang.*;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "%maven org.knowm.xchart:xchart:3.5.2\n",
    "import org.knowm.xchart.*;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Helper Methods\n",
    "\n",
    "Let's code three helper methods:\n",
    "\n",
    "* random array generator\n",
    "* array printer\n",
    "* copyArray\n",
    "\n",
    "It is assumed that you are fully capable of coding two similar methods by yourself. If you are new to Java (but have some experience with a different language), playing with these methods will help you get familiar with Java faster."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "// random array generator\n",
    "public int[] randomArr(int size) {\n",
    "    Random r = new Random();\n",
    "    int[] arr = new int[size];\n",
    "    \n",
    "    for (int i = 0; i < size; i++) {\n",
    "        arr[i] = r.nextInt(1000) + 1;\n",
    "    }\n",
    "    \n",
    "    return arr;\n",
    "}\n",
    "\n",
    "// array printer\n",
    "public void printArr(int[] arr) {\n",
    "    for (int num : arr) {\n",
    "        System.out.print(num + \" \");\n",
    "    }\n",
    "    System.out.println();\n",
    "}\n",
    "\n",
    "// array deep copy\n",
    "public void copyArray(int[] from, int[] to) {\n",
    "    if (from.length != to.length) {\n",
    "        System.exit(0);\n",
    "    }\n",
    "    \n",
    "    for (int i = 0; i < from.length; i++) {\n",
    "        to[i] = from[i];\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Merge Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Practice - sort by color\n",
    "\n",
    "Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.\n",
    "\n",
    "Example:\n",
    "\n",
    "```\n",
    "Input: [2,0,2,1,1,0]\n",
    "Output: [0,0,1,1,2,2]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "public void mergeSort(int[] arr, int n) {\n",
    "    if (n < 2) {\n",
    "        return;\n",
    "    }\n",
    "    int mid = n / 2;\n",
    "    int[] l = new int[mid];\n",
    "    int[] r = new int[n - mid];\n",
    " \n",
    "    for (int i = 0; i < mid; i++) {\n",
    "        l[i] = arr[i];\n",
    "    }\n",
    "    for (int i = mid; i < n; i++) {\n",
    "        r[i - mid] = arr[i];\n",
    "    }\n",
    "    mergeSort(l, mid);\n",
    "    mergeSort(r, n - mid);\n",
    " \n",
    "    merge(arr, l, r, mid, n - mid);\n",
    "}\n",
    "\n",
    "public void merge(int[] arr, int[] l, int[] r, int left, int right) {\n",
    "  \n",
    "    int i = 0, j = 0, k = 0;\n",
    "    while (i < left && j < right) {\n",
    "        if (l[i] <= r[j]) {\n",
    "            arr[k++] = l[i++];\n",
    "        }\n",
    "        else {\n",
    "            arr[k++] = r[j++];\n",
    "        }\n",
    "    }\n",
    "    while (i < left) {\n",
    "        arr[k++] = l[i++];\n",
    "    }\n",
    "    while (j < right) {\n",
    "        arr[k++] = r[j++];\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**<span style=\"color:red\">Can you write a few methods to make the testing of the above solution scalable?</span>**\n",
    "\n",
    "Such methods may include:\n",
    "\n",
    "* *array generator*: generate a random array\n",
    "\n",
    "You can reuse my code that generates a random array."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Practice - merge two sorted linked lists\n",
    "\n",
    "Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.\n",
    "\n",
    "Example:\n",
    "```\n",
    "Input: 1->2->4, 1->3->4\n",
    "Output: 1->1->2->3->4->4\n",
    "```\n",
    "\n",
    "A linked listnode is defined for you as the following."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "public class ListNode {\n",
    "    int val;\n",
    "    ListNode next;\n",
    "    ListNode(int data) {\n",
    "        val = data;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "public ListNode insertLSort(ListNode head) {\n",
    "    // your code goes here\n",
    "    // remove this line\n",
    "    return ListNode(-1);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**<span style=\"color:red\">Can you provide a solution and write a few testing methods for your solution?</span>**\n",
    "\n",
    "You want to make sure that anyone who is interested in testing your solution can utlize your testing methods to achieve effective testing easily. Such methods may include:\n",
    "\n",
    "* *linked list printer*: print out all elements of a linked list\n",
    "* *linked list generator*: generate a randomly linked list\n",
    "\n",
    "You can reuse your testing code for testing the solution of insertion sort (linked list)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Practice - merge k sorted linked lists\n",
    "\n",
    "Merge k sorted linked lists and return it as one sorted list.\n",
    "\n",
    "Example:\n",
    "\n",
    "```\n",
    "Input:\n",
    "  1->4->5,\n",
    "  1->3->4,\n",
    "  2->6\n",
    "Output: 1->1->2->3->4->4->5->6\n",
    "```\n",
    "\n",
    "A linked listnode is defined for you as the following."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "public class ListNode {\n",
    "    int val;\n",
    "    ListNode next;\n",
    "    ListNode(int data) {\n",
    "        val = data;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**<span style=\"color:red\">Can you provide a solution and write a few testing methods for your solution?</span>**\n",
    "\n",
    "You want to make sure that anyone who is interested in testing your solution can utlize your testing methods to achieve effective testing easily. Such methods may include:\n",
    "\n",
    "* *linked list printer*: print out all elements of a linked list\n",
    "* *linked list generator*: generate a randomly linked list\n",
    "\n",
    "You can reuse your testing code for testing the solution of insertion sort (linked list)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Do It Yourself"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even. Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even. You may return any answer array that satisfies this condition. \n",
    "\n",
    "Example:\n",
    "```\n",
    "Input: [4,2,5,7]\n",
    "Output: [4,5,2,7]\n",
    "Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.\n",
    "```\n",
    "\n",
    "Please also indicate the best, average and worst time complexity of your own solution. You may want to lay out some basic reasoning for your answers (*maybe with a plot*).\n",
    "\n",
    "**When you finish (or not) playing your exploration of the whole interactive notebook and DIY assignment, you should download a html file and upload it to the assignment box on Canvas:**\n",
    "\n",
    "* File --> Download as --> HTML (.html)\n",
    "\n",
    "![download](images/html.png)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".jshell",
   "mimetype": "text/x-java-source",
   "name": "Java",
   "pygments_lexer": "java",
   "version": "12.0.2+10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}