Understand quicksort partitioning

The most important part of understanding quicksort is to understand the partitioning function.

Here is an intuitive way to present the array being currently partitioned, let's say we've selected a pivot in the middle of the array and its value is 100. Here's the array being partitioned.

Where pivot was prior to partitioning and after the partitioning doesn't really matter, as long as it ends up being on the correct side of the result boundary.What really matters is that when partitioning is done, all elements to the left of left index are smaller than pivot.(or all elements to the right of right index are larger than pivot)Let's assume the pivot element 100 has already been swapped to the blue part. 

1. The left index keeps increasing, and all elements it left behind are smaller than the pivot. At the same time, the right index keeps decreasing, and all elements it left behind are larger than the pivot.
2. If left index meets an element larger than or equal to the pivot, it stops, and wait for right index to find an element smaller than or equal to the pivot, then they swap the elements and continue the step 1 until the left index is larger than the right index. What if the right index does not find an element smaller than or equal to the pivot? Then the right index will just continue moving to the left until it passes the left index, and stops at the next element of the left index (because its value is smaller than pivot). Then the partitioning is done.
3. return the left index as the boundary to which all elements on the left are smaller than the pivot.

Bonus: Have you seen this amusing Hungarian quicksort dance before? 

https://www.youtube.com/watch?v=ywWBy6J5gz8

Continue reading →

Mimicked version of Alice's Adventures in Wonderland

Why?

This is an easy algorithm I coded to practise Python.

I've been studying Machine Learning for a while, mainly by following courses on Coursera. Even though I have some occasions to implement the training algorithms such as Gradient Descent for Linear Regression, Logistic Regression for Classification; I mainly used Matlab, which is an efficient and practical tool and very easy to get start with. However, I think it would also be great to learn to use some of the ML libraries in Python, such as scikit-learn, which is already tuned and optimised by a lot of data scientists.  I also want to start doing some of the problems on Kaggle, and I'm not sure if Matlab is a perfect tool for that. This is why I decided to learn python by following Google Python Class.

What's the mimicked version of Alice's Adventures in Wonderland?

Basically, you pick a random word in the book. I picked the first word in the book, which is "Alice". Then you shall follow these steps to generate your version of the book:

• Print the chosen word, and then look up what words might come next in the original novel, then pick one at random.
• Do this recursively for 200 times.

Can you show me the mimicked version?

Here's the mimicked version I generated with the algorithm mentioned above :)

Alice's elbow was gently brushing away quietly marched off together, Alice a minute, `and I can be seen: she spread his book, `Rule Forty-two. ALL RETURNED FROM HIM TWO--" why, I ought to a well?' The first saw the mistake about for her eyes were of him), while she is asleep again,' said after her: its full of the opportunity of things--I can't have signed at once set to feel very dull!' `You might belong to my youth,' said the right THROUGH the Mouse with such nonsense!' `I feared it might knock, and his pocket, and anxious.) Alice to be civil, you'd better with the sea,' the rattle of the Cat went on a week: HE was.' `I feared it was certainly was, what? Alice called after it, and Grief, they don't believe there's nothing seems to be a thick wood. `The fourth.' `Two days and then, saying to speak again. This was I the others. `Are they were nowhere to have to Alice said; but there stood the King. `Nearly two and hurried on, looking over their own business!' said Alice. `Why the stairs. Alice thought was coming. It sounded promising, certainly: but the Mock Turtle, and doesn't understand

Isn't it fun? :)

I'll continue following the rest of the ML course. Hope I could use what I learned one day to solve real world problems.

Continue reading →