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

    • Cloud Computing
      It’s been really long, since I last wrote a tech post. In this post, I’m just sharing few useful links to get started on Cloud Computing, whether you’re a developer, quality engineer, business leader, or a project manager intending to get started with Cloud Computing. I’m currently designing systems and services, for a platform that’s […]
    • 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 […]
  • Twitter Updates

Sorting in Linear Time

Posted by sanstechbytes on August 17, 2011

Sorting in linear time is achievable using COUNTING SORT, RADIX SORT, BUCKET SORT algos under special cases. All these trade space for time.  The point in this post is, to sort in linear time, in-place, for special case of array-or-the-list-or-the-attribute-that-can-have-only-two-distinct-values problem.

I call the technique of using two pointers to rearrange(sort) elements based on comparisons or perform math operations like add, subtract, multiply, squaring, divide to yield the target output, the “Two-Pointer Technique”.  This technique is used to efficiently solve problems like:
a) Finding the pair in array that add up to the given target(it’s a sub-problem of EXACT-SUBSET-SUM problem (refer to Introduction to Algorithms by CLRS))
b) Sorting an array with 0’s and 1’s or in general, any array that contains only two distinct values.
c) Finding the Pythagorean triples in an array etc.

The thing is, most of us (I’m talking to the java developers here) just use Collections.sort(…) or Arrays.sort(…)   for all our sorting needs , even for special cases like, the array-or-the-list-can-have-only-two-distinct-values problem.  In a related note, for problem of sorting ‘Person’ objects by age, we can think of implementing BUCKET SORT (runs in O(kn) time) where k could be < 130(age) etc, instead of merge sort of Array.sort(…)  or Collections.sort(…) that runs in O(n log n) worst-case.

The below sort  algorithms run in linear time, in-place and I think, are worth considering for those cases. Below  sort implementations (in Java) are based on Two-Pointer Technique. Think of using this technique to solve many problems. Comments follow in line.

Special mention is for sort(…) method to sort objects based on one field that can contain only one of any two values(say, gender – can only be F or M), for all practical purposes. This implementation compares with Collections.sort(in Java) as follows:
a) Avoids the cost of loading classes: Collections, (say)PersonComparator, Comparable
b) Runs in O(n) compared to Merge-Sort O(n log n) used in Collections.sort(…)
c) Reduces space complexity (merge sort uses auxiliary array of length n, to copy the elements in the sorted array). This is done, in-place (constant amount of space).

Try yourself quantifying the above differences with sample input and run. You’ll notice the significant efficiency achieved.

//Code

public static void testSort( ) {
 int[] a = new int[] { 1, 0, 0, 0, 0, 0, 1 };
 int x = 0, y = 1; // generalized to
System.out.println(“before sort”);
 // printArray(a);
 sortTwoVals(a, x, y); // for int’s
String[] s = new String[] { “Male”, “female”, “male”, “Female”, “male” };
 // printArray(s);
 String s1 = “Female”;
 String s2 = “male”;
sortTwoVals(s, s1, s2); //for strings
List list = new ArrayList();
 String F = “F”;
 String M = “M”;
 list.add(new Person(“Sanjeev”, 27, M));
 list.add(new Person(“Mridul”, 30, M));
 list.add(new Person(“Roark”, 27, M));
 list.add(new Person(“Howard”, 28, M));
 list.add(new Person(“Sheldon”, 23, M));
 list.add(new Person(“Leonard”, 31, F));
 list.add(new Person(“Shanti”, 25, F));
 list.add(new Person(“Pavan”, 27, M));
System.out.println(“Before sort…”);
 // printArray(list.toArray());
 String firstAfterSort = F, secondAfterSort = M;
 list = sort(list, firstAfterSort, secondAfterSort);
 System.out.println(“After sort…”);
 System.out.println(“Persons sorted according to their gender”);
 // printArray(list.toArray());
 }


// When two pointers (‘start’ and ‘end’ converge), we’re done with sorting.
// For integers
public static int[] sortTwoVals(int[] a, int x, int y) {
 int start = 0, end = a.length – 1;
 while (start < end) {
  if (a[start] == y) {
    while (a[end] == y) {
     if (end < start) {
     break; // Sorted case
    }
  end–;
 }

   if (a[end] == x) {
    a[end] = y;
    a[start] = x;
   }
  }
  start++;
 }
 return a;
}


// For Strings
public static String[] sortTwoVals(String[] s, String s1, String s2) {
 int start = 0, end = s.length – 1;
 while (start < end) {
  if (s2.equalsIgnoreCase(s[start])) {
   while (s2.equalsIgnoreCase(s[end])) {
    if (end < start) {
      break; // Sorted case
    }
   end–;
 }

  if (s1.equalsIgnoreCase(s[end])) {
   s[end] = s2;
   s[start] = s1;
  }
 }
 start++;
}
return s;
}


// For objects
public static List sort(List personsList, String firstAfterSort,
 String secondAfterSort) {
 Object[] persons = personsList.toArray();
 int start = 0, end = persons.length – 1;
// When two pointers converge, we’re done with sorting
 while (start < end) {
 if (secondAfterSort.equalsIgnoreCase(((Person) persons[start])
 .getGender())) {
 while (secondAfterSort.equalsIgnoreCase(((Person) persons[end])
 .getGender())) {
 if (end <= start) {
 break; // Sorted case
 }
 end–;
 }
 if (firstAfterSort.equalsIgnoreCase(((Person) persons[end])
 .getGender())) {
 Person swap = (Person) persons[end];
 persons[end] = persons[start];
 persons[start] = swap;
 }
 }
 start++;
 }
 return java.util.Arrays.asList(persons);
 }


public class Person {
 private String name;
 private int age;
 private String gender;
 private Address address;
public Person(String name, int age, String gender) {
 this.name = name;
 this.age = age;
 this.gender = gender;
 }
public Address getAddress() {
 return address;
 }
public void setAddress(Address address) {
 this.address = address;
 }
public int getAge() {
 return age;
 }
public void setAge(int age) {
 this.age = age;
 }
public String getName() {
 return name;
 }
public void setName(String name) {
 this.name = name;
 }
public String getGender() {
 return gender;
 }
public void setGender(String gender) {
 this.gender = gender;
 }
}


class Address {

}

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: