How to Get The Kth Smallest Element in an Array

Problem:

As the title said, "How to get the kth smallest element in an array?"
This array could be totally unordered.

Solution:

Most intuitive method for this problem would be sort the array, then return the kth value of the array, which cost O(NlogN) + O(1), which is O(NlogN). But there is O(N) algorithms for average case called Selective Algorithms.

It's very like Quick-Sort Algorithm, but this one always cuts the array in two, and choose the one we need. So it would be like:

T(n) = T(P) + O(n) , P is one of (1 , n)

 For average, P would be n/2, since we choose it randomly, then we could have T(n) = O(n).

If K is n/2, then this problem turns to be finding the medium element of array.

This is a very popular interview question, so have fun.

---

Source Code:

private int getKthSmallestElement(int[] uA, int start, int end, int kth) {
  print(uA, start, end);
  Random r = new Random();
  int pivot = start + r.nextInt(end - start + 1);
  System.out.println(String.format("Pivot Element %d", uA[pivot]));
  int tmp = uA[start];
  uA[start] = uA[pivot];
  uA[pivot] = tmp;
  pivot = start;
  int i, j;
  for (i = start + 1, j = end; i < j;) {
   while (uA[i] <= uA[pivot] && i < j)
    i++;
   while (uA[j] > uA[pivot] && i < j)
    j--;
   if (i < j) {
    tmp = uA[i];
    uA[i] = uA[j];
    uA[j] = tmp;
    i++;
    j--;
   }
  }

  if (i > j || uA[i] > uA[pivot]) {
   i--;
  }
  tmp = uA[i];
  uA[i] = uA[pivot];
  uA[pivot] = tmp;
  pivot = i;

  System.out.println(String.format("(Start, End) : (%d %d)", start, end));
  print(uA, start, end);
  System.out.println(String.format("(i, j) : (%d %d)", i, j));
  System.out.println(String.format("Pivot: %d\n", pivot));
  if (pivot + 1 == kth)
   return uA[pivot];
  else if (pivot + 1 > kth) {
   return getKthSmallestElement(uA, start, pivot - 1, kth);
  } else
   return getKthSmallestElement(uA, pivot + 1, end, kth);
 }

 private void print(int[] array, int start, int end) {
  for (int i = start; i <= end; i++)
   System.out.print(" " + array[i]);
  System.out.println();
 }

Insert into a Cyclic Sorted List

Problem:

 * Given a node from a cyclic linked list which has been sorted, 

 * write a function to insert a value into the list such that it remains a cyclic sorted list. 

 * The given node can be any single node in the list.

Solution:

---

Source Code:

/**
 * Given a node from a cyclic linked list which has been sorted, 
 * write a function to insert a value into the list such that it remains a cyclic sorted list. 
 * The given node can be any single node in the list.
 */

/**
 * @author Antonio081014
 * @since Oct 28, 2013, 10:43:52 AM
 */
public class Test {

 public static void main(String[] args) {
  CycledList list = new CycledList();
  list.print();
  list.insert(3);
  list.print();
  list.insert(1);
  list.insert(1);
  list.print();
 }
}

class CycledList {
 public Node head;

 /**
  * Several Cases:

  * 1st, when linked list is empty; 

  * 2nd, when new element is either minimum or maximum; 

  * 3rd, when new element is in between two sorted elements. 

  * 
  * 
  * Since this list is like a circle, we don't necessary to have the smallest
  * element as the head, but it's definitely sorted.
  * */
 public void insert(int x) {
  // 1st Case;
  if (head == null) {
   head = new Node(x);
   head.next = head;
   return;
  }
  Node p = head;
  Node prev = null;
  do {
   prev = p;
   p = p.next;
   // 2nd Case;
   if (prev.data >= p.data && (x <= p.data || x >= prev.data))
    break;
   // 3rd Case;
   if (prev.data <= x && p.data >= x)
    break;
  } while (p != head);
  Node tmp = new Node(x);
  prev.next = tmp;
  tmp.next = p;
 }

 public void print() {
  if (head == null) {
   System.out.println("Empty Cycled List");
   return;
  }
  Node p = head;
  do {
   System.out.print(p.data + " ");
   p = p.next;
  } while (head != p);
  System.out.println();
 }
}

class Node {
 public int data;
 public Node next;

 public Node(int x) {
  this.data = x;
  next = null;
 }

 public Node(int x, Node n) {
  this.data = x;
  this.next = n;
 }
}