Sort | Learn for Master

  • Java Sort using Comparable or Comparator

    August 1, 2016 Author: david
    No comment yet

    In Java, it is straightforward to sort objects of the predefined class such as Integer, Double, Float and String. This is because these classes have been implemented the Comparable interface.  Comparable defines a natural ordering, as when you’re defining it, you specify which one is  considered “less than” or “greater than” the another.

    How can you sort custom Objects? For example, suppose you have a list of objects of Student class, which has name, age, and score attributes. You may want to sort the students by their scores. Another example is to sort a list strings by their length. 

    [Read More...]

  • Quicksort algorithm

    July 24, 2016 Author: david
    No comment yet

    Quicksort is one of the most famous sort algorithms because of its average good performance. Because of its importance and popularity, it is usually asked in technique interviews. It is also important to master QuickSort as its partitioning technique can also be used to find the Kth largest or smallest element of an array in O(n) time with O(1) space complexity. 

    How quickSort algorithm works

    Given an array A[s … e], a pivot is chosen to rearrange the array into two parts: ALeft and Aright. All the elements in ALeft are less than or equal to the pivot,

    [Read More...]

  • LeetCode – Merge Sorted Array without extra space

    July 24, 2016 Author: david
    No comment yet

    Given two sorted integer arrays A and B, merge B into A as one sorted array.

    Note:
    You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

    Analysis

    We have described how to merge two sorted arrays into a third sorted array. For this problem, as A is assumed to have enough space, we are not allowed to create a third array. 

    We cannot start the merge from the beginning of the two arrays,

    [Read More...]

  • Merge two sorted arrays algorithm (Java)

    July 24, 2016 Author: david
    No comment yet

    Given two sorted arrays or lists, how to merge them into a sorted array?  

    This is a fundamental problem as it is a common requirement to merge two sorted arrays into one sorted array. The algorithm of merging two sorted arrays is also the basics of the one of the most famous sort algorithms: merge sort.

    Suppose there are two sorted arrays A and B, and we want to merge them into a third Array C.

    We define three indexes a, b, c, which points to the beginning of the three arrays A, B,

    [Read More...]

  • Leetcode – Color Sort

    July 1, 2016 Author: david
    No comment yet

    Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

    Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

    Note:
    You are not suppose to use the library’s sort function for this problem.

    Follow up:
    A rather straight forward solution is a two-pass algorithm using counting sort.
    First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s,

    [Read More...]

  • Selection Sort Algorithm (Python)

    June 19, 2016 Author: david
    No comment yet

    Selection sort is one of the simplest sorting algorithms. This tutorial described how to implement selection sort algorithm in python.

    The basic idea of selection sort is that it repeatedly select the smallest item in list A[i+1:], and exchange it with the item at A[i].

    It works as follows:

    1. Find the smallest item in the array, and exchange it with the first entry.
    2. Find the next smallest item in the array, and exchange it with the second entry.
    3. Continue such a process until the whole array is sorted.

    [Read More...]