Sanstech

Ideas, Knowledge, Technology, Computer Science, Experience associated with my work and some geeky stuff I progressively encounter during my journey towards enlightenment. Read on…

  • RSS RSS Feed

    • The Pragmatic Programmer
      I finished reading The Pragmatic Programmer by Andrew Hunt and David Thomas. It’s not a new book in the market but I was curious to read this. The technology topics covered, are not any different from those found in most software engineering books, but the way they’re presented using Pragmatic Philosophy Approach, is remarkable. Code […]
    • 2013 in review
      The WordPress.com stats helper monkeys prepared a 2013 annual report for this blog. Here’s an excerpt: A San Francisco cable car holds 60 people. This blog was viewed about 1,200 times in 2013. If it were a cable car, it would take about 20 trips to carry that many people. Click here to see the […]
    • Goodbye, Ness!
      It had to happen sometime. I thought Feb 2013 was the right time. I quit Ness after a long 5 years and 4 months of stay, in Feb. I joined FICO (formerly, Fair Isaac) last Feb.  While I get an opportunity to work with many varied stakeholders like Scientists, Architect, Product Management, Peer Developers, PMO, Technical Publications and also […]
    • Meta: information retrieval from Tweets
      I pick significant problems randomly sometimes and enjoy solving them, or at least attempt designing api :-). Here’s one such problem! Problem: How’d you go about finding meta information about a person’s tweets? NOTE: a) Tweet == Twitter updates b) Meta information –> Loosely defined. You can interpret it anyway you want –> Frequency, topics, follower […]
    • Understanding Big Data
      It’s been a while, since I last posted! To keep this rolling (I’m hardly getting any time to post my own articles or stuff about my experiments these days 😦  ), I just wanted to share this ebook on Big Data titled  Understanding Big Data: Analytics for Enterprise Class and Streaming Data. Cheers!
  • Twitter Updates

Find the kth Smallest Element in Array in Linear Time

Posted by sanstechbytes on July 24, 2011

Finding the kth smallest element in array is an application related to Order Statistics problem. For details on the algo used here, watch the video lecture embedded below.

Robert Sedgewick, whose lecture this approach has been inspired from, proposes random shuffle mechanism and partitioning strategy to select the kth smallest element. The strategy requires maintaining variables lo and hi to delimit the subarray that contains the index k of the element to be selected, using partitioning to shrink the size of the subarray (Step 2). The assumption made is that the input array to the algo doesn’t contain duplicates (This can be carried out as a preprocessing step, which is performed as first step in the algo below, though). Runs in linear time, O(n).

Algo:
1) Preprocess array to remove duplicates.
2) Rearrange the array from a[lo] through a[hi] and return an integer j such that a[lo] through a[j-1] are less than a[j], and a[j+1] through a[hi] are greater than a[j].
a) If k is equal to j, done.
b) Else If k is less than j, then continue working in the right subarray (by changing the value of hi to j-1).
c) Else If k is greater than j, then continue working in the right subarray (by changing lo to j+1).
3) Repeat step (2), until the array consists just of k.

MIT Video Lecture on Order Statistics:

Java Code:


/** Sedgewick's partitioning approach */
 public class QuickSelect {

private static Random random = new Random();

public static Comparable select(Comparable[] a, int k) {
 if (k = a.length) {
 throw new RuntimeException("Selected element out of bounds");
 }

shuffle(a);

int lo = 0, hi = a.length - 1;
 while (hi > lo) {
 int i = partition(a, lo, hi);
 if (i > k)
 hi = i - 1;
 else if (i < k)
 lo = i + 1;
 else
 return a[i];
 }
 return a[lo];
 }

private static int partition(Comparable[] a, int lo, int hi) {
 int i = lo;
 int j = hi + 1;
 Comparable v = a[lo];
 while (true) {
 // find item on lo to swap
 while (less(a[++i], v))
 if (i == hi)
 break;
 // find item on hi to swap
 while (less(v, a[--j]))
 if (j == lo)
 break; // redundant since a[lo] acts as sentinel
 // check if pointers cross
 if (i >= j)
 break;
 exch(a, i, j);
 }
 // put v = a[j] into position
 exch(a, lo, j);
 // with a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
 return j;
 }

public static void shuffle(Object[] a) {
 int n = a.length;
 for (int i = 0; i < n; i++) {
 int r = i + uniform(n - i); // between i and N-1
 Object temp = a[i];
 a[i] = a[r];
 a[r] = temp;
 }
 }

/**
 * Return an integer uniformly between 0 and N-1.
 */
 public static int uniform(int N) {
 return random.nextInt(N);
 }

// is v < w ?
 private static boolean less(Comparable v, Comparable w) {
 return (v.compareTo(w) < 0);
 }

// exchange a[i] and a[j]
 private static void exch(Object[] a, int i, int j) {
 Object swap = a[i];
 a[i] = a[j];
 a[j] = swap;
 }

// Read strings from standard input, sort them, and print.
 public static void main(String[] args) {
 // Read input from StdIn here
 // String[] a = new String[]{"aa", "aaa", "bb", "ab", "ca", "bc",
 // "cab", "cc", "cad" };
 Integer[] a = new Integer[] { 2, 11, 10, 6, 8, 99, 7, 100, 101, 28,
 9 };
 int k = 2;
 Object kth = Quick.select(a, k - 1); // returns a[k-1]
 System.out.println(k + "th smallest element in given array = "
 + kth);
 }
 }

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: