## 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();
}
```

## 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.

## 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 {

/**
* 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;
return;
}
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;
Node tmp = new Node(x);
prev.next = tmp;
tmp.next = p;
}

public void print() {
System.out.println("Empty Cycled List");
return;
}
do {
System.out.print(p.data + " ");
p = p.next;
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;
}
}

```