OS Miscs

OS Miscs

Critical section
A critical section is a piece of code that accesses a shared resource (data structure or device) that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to enter it (aka bounded waiting). Some synchronization mechanism is required at the entry and exit of the critical section to ensure exclusive use, for example a semaphore.
How critical sections are implemented varies among operating systems.
The simplest method is to prevent any change of processor control inside the critical section. On uni-processor systems, this can be done by disabling interrupts on entry into the critical section, avoiding system calls that can cause a context switch while inside the section and restoring interrupts to their previous state on exit. Any thread of execution entering any critical section anywhere in the system will, with this implementation, prevent any other thread, including an interrupt, from getting the CPU and therefore from entering any other critical section or, indeed, any code whatsoever, until the original thread leaves its critical section.
This brute-force approach can be improved upon by using semaphores. To enter a critical section, a thread must obtain a semaphore, which it releases on leaving the section. Other threads are prevented from entering the critical section at the same time as the original thread, but are free to gain control of the CPU and execute other code, including other critical sections that are protected by different semaphores.
Semaphore
A semaphore is a protected variable or abstract data type which constitutes the classic method for restricting access to shared resources such as shared memory in a parallel programming environment. A counting semaphore is a counter for a set of available resources, rather than a locked/unlocked flag of a single resource.
Semaphores can be either binary or counting, depending on the number of shared resources. If a single shared resource is used, then we would require just one semaphore for synchronization purposes. In that case, the semaphore is referred as a binary semaphore. In all other cases, where the number of resources shared across users are greater than one, you would use multiple semaphores, in which case they are referred as counting semaphores.
Semaphores basically implement two kinds of operations. One to wait on the semaphore variable and another that signals the semaphore variable. Since semaphores are nothing but a counter, the following algorithm depicts these two semaphore operations:
Assume :
s is the semaphore variable
W(s) denotes waiting on the semaphore
P(s) means signaling the availability of semaphore
The value of a semaphore is the number of units of the resource which are free. (If there is only one resource, a "binary semaphore" with values 0 or 1 is used.) The P operation busy-waits (uses its turn to do nothing) or maybe sleeps (tells the system not to give it a turn) until a resource is available, whereupon it immediately claims one. The V operation is the inverse; it simply makes a resource available again after the process has finished using it. The P and V operations must be atomic.
In software engineering practice, they are often called wait and signal, or acquire and release.
Binary semaphore vs. Mutex
A mutex is a binary semaphore (a semaphore with capacity of 1), usually including extra features like ownership, priority inversion protection or recursivity. The differences between mutexes and semaphores are operating system dependent, though mutexes are implemented by specialized and faster routines. Mutexes are meant to be used for mutual exclusion (post/release operation is restricted to thread which called pend/acquire) only and binary semaphores are meant to be used for event notification (post-ability from any thread) and mutual exclusion.
Monitor (synchronization)
Monitor is an object intended to be used safely by more than one thread. The defining characteristic of a monitor is that its methods are executed with mutual exclusion. That is, at each point in time, at most one thread may be executing any of its methods.
Monitors also provide a mechanism for threads to temporarily give up exclusive access, in order to wait for some condition to be met, before regaining exclusive access and resuming their task. Monitors also have a mechanism for signaling other threads that such conditions have been met.
Inter-process communication
Inter-process communication (IPC) is a set of techniques for the exchange of data among multiple threads in one or more processes. Processes may be running on one or more computers connected by a network. IPC techniques are divided into methods for message passing, synchronization, shared memory, and remote procedure calls (RPC).
Main IPC Methods
File, Signal, Socket, Message queue, Pipe, Named pipe, Semaphore, Shared memory, Message passing, memory-mapped file.
Anonymous pipe
An anonymous pipe is a simplex FIFO communication channel that may be used for one-way interprocess communication.
Typically a parent program opens anonymous pipes, and creates a new process that inherits the other ends of the pipes, or creates several new processes and arranges them in a pipeline.
Two anonymous pipes are required for full-duplex (two-way) communication.
In a Unix shell a pipeline is created using the "|" character and many Unix programs are designed as filters to work with pipes.
Named pipe
A traditional pipe is "unnamed" because it exists anonymously and persists only for as long as the process is running. A named pipe is system-persistent and exists beyond the life of the process and must be deleted once it is no longer being used. Processes generally attach to the named pipe (usually appearing as a file) to perform inter-process communication (IPC).
Instead of a conventional, unnamed, shell pipeline, a named pipeline is explicitly created using mkfifo() or mknod(), and two separate processes can access the pipe by name.
mkfifo my_pipe
gzip -9 -c < my_pipe > out.gz
cat file > my_pipe
rm my_pipe
Pipeline (Unix)
In Unix-like computer operating systems, a pipeline is the original software pipeline: a set of processes chained by their standard streams, so that the output of each process (stdout) feeds directly as input (stdin) to the next one. Each connection is implemented by an anonymous pipe. Filter programs are often used in this configuration.
Shared memory
Shared memory is memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies. Depending on context, programs may run on a single processor or on multiple separate processors.
Since both processes can access the shared memory area like regular working memory, this is a very fast way of communication (as opposed to other mechanisms of IPC such as named pipes, Unix domain sockets or CORBA). On the other hand, it is less powerful, as for example the communicating processes must be running on the same machine (whereas other IPC methods can use a computer network), and care must be taken to avoid issues if processes sharing memory are running on separate CPUs and the underlying architecture is not cache coherent.
Message queue
Message queues and mailboxes are software-engineering components used for interprocess communication, or for inter-thread communication within the same process. They use a queue for messaging – the passing of control or of content.
Message queues provide an asynchronous communications protocol, meaning that the sender and receiver of the message do not need to interact with the message queue at the same time. Messages placed onto the queue are stored until the recipient retrieves them.
Most message queues have set limits on the size of data that can be transmitted in a single message. Those that do not have such limits are known as mailboxes.
There are a number of open source choices of messaging middleware systems, including Apache ActiveMQ, JBoss Messaging.
Paging
In the paging memory-management scheme, the operating system retrieves data from secondary storage in same-size blocks called pages. The main advantage of paging is that it allows the physical address space of a process to be noncontiguous. Prior to paging, systems had to fit whole programs into storage contiguously which caused various storage and fragmentation problems.
Paging allowes to use disk storage for data that does not fit into physical Random-access memory (RAM)
The main functions of paging are performed when a program tries to access pages that are not currently mapped to physical memory (RAM). This situation is known as a page fault. The operating system must then take control and handle the page fault, in a manner invisible to the program. Therefore, the operating system must:
1. Determine the location of the data in auxiliary storage.
2. Obtain an empty page frame in RAM to use as a container for the data.
3. Load the requested data into the available page frame.
4. Update the page table to show the new data.
5. Return control to the program, transparently retrying the instruction that caused the page fault.
In reaction to a page fault, there are several strategies for guessing what pages might be needed, and speculatively pre-loading them: Demand paging, Anticipatory paging, Swap prefetch, Pre-cleaning.
Memory Segmentation
In a computer system using segmentation, an instruction operand that refers to a memory location includes a value that identifies a segment and an offset within that segment. A segment has a set of permissions, and a length, associated with it.
Segmentation with Paging
In this scheme, segmentations are broken into page, in this way, the user view is segmentation, but OS can implement with demand paging.
Virtual memory
Virtual memory is a computer system technique which gives an application program the impression that it has contiguous working memory (an address space), while in fact it may be physically fragmented and may even overflow on to disk storage.
Virtual memory separates user logical memory from physical memory, it allows an extremely large virtual memory to be provided when only a small physical memory is available.
Page replacement algorithm
In a computer operating system that uses paging for virtual memory memory management, page replacement algorithms decide which memory pages to page out (swap out, write to disk) when a page of memory needs to be allocated. Paging happens when a page fault occurs and a free page cannot be used to satisfy the allocation, either because there are none, or because the number of free pages is lower than some threshold.
Page replacement algorithms includes: Not recently used(NRU), First-in, first-out(FIFO), Least recently used(LRU),Not frequently used(NFU), Aging
Not recently used
The not recently used (NRU) page replacement algorithm is an algorithm that favours keeping pages in memory that have been recently used.
Least recently used
LRU works on the idea that pages that have been most heavily used in the past few instructions are most likely to be used heavily in the next few instructions too. While LRU can provide near-optimal performance in theory, it is rather expensive to implement in practice.
Not frequently used
The not frequently used (NFU) page replacement algorithm requires a counter, and every page has one counter of its own which is initially set to 0.
Aging
The aging algorithm is a descendant of the NFU algorithm, with modifications to make it aware of the time span of use.


Resources:
http://en.wikipedia.org/wiki/

Algorithm – Tree Concept

Algorithm – Tree Concept

A binary tree is a tree data structure in which each node has at most two children. Typically the first node is known as the parent and the child nodes are called left and right.
Complete Binary tree
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
Complete Binary tree is implemented using an array.
A binary search tree (BST) is a node based binary tree data structure which has the following properties:
* The left subtree of a node contains only nodes with keys less than the node's key.
* The right subtree of a node contains only nodes with keys greater than the node's key.
* Both the left and right subtrees must also be binary search trees.
Implementation
A self-balancing (or height-balanced) binary search tree is any binary search tree data structure that automatically keeps its height (number of levels below the root) small in the face of arbitrary item insertions and deletions.
Most operations on a binary search tree (BST) take time directly proportional to the height of the tree, so it is desirable to keep the height small.
In AVL tree is a self-balancing binary search tree.
In an AVL tree, the heights of the two child subtrees of any node differ by at most one; therefore, it is also said to be height-balanced. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
AVL trees perform better than red-black trees for lookup-intensive applications.
It is complex, but has good worst-case running time for its operations and is efficient in practice: it can search, insert, and delete in O(log n) time.
A red-black tree is a binary search tree where each node has a color attribute, the value of which is either red or black. In addition to the ordinary requirements imposed on binary search trees, the following additional requirements apply to red-black trees:
1. A node is either red or black.
2. The root is black. (This rule is used in some definitions and not others. Since the root can always be changed from red to black but not necessarily vice-versa this rule has little effect on analysis.)
3. All leaves are black.
4. Both children of every red node are black.
5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.
A splay tree is a self-balancing binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log(n)) amortized time.
All normal operations on a binary search tree are combined with one basic operation, called splaying. Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree. One way to do this is to first perform a standard binary tree search for the element in question, and then use tree rotations in a specific fashion to bring the element to the top. Alternatively, a top-down algorithm can combine the search and the tree reorganization into a single phase.
Advantages and disadvantages
Good performance for a splay tree depends on the fact that it is self-balancing, and indeed self optimizing, in that frequently accessed nodes will move nearer to the root where they can be accessed more quickly. This is an advantage for nearly all practical applications, and is particularly useful for implementing caches and garbage collection algorithms;
Splay trees also have the advantage of being considerably simpler to implement than other self-balancing binary search trees, such as red-black trees or AVL trees, while their average-case performance is just as efficient. Also, splay trees do not need to store any bookkeeping data, thus minimizing memory requirements. However, these other data structures provide worst-case time guarantees, and can be more efficient in practice for uniform access.
The B-tree is a generalization of a binary search tree in that more than two paths diverge from a single node.
Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data. It is most commonly used in databases and filesystems.
In B-trees, internal (non-leaf) nodes can have a variable number of child nodes within some pre-defined range. When data is inserted or removed from a node, its number of child nodes changes. In order to maintain the pre-defined range, internal nodes may be joined or split. Because a range of child nodes is permitted, B-trees do not need re-balancing as frequently as other self-balancing search trees, but may waste some space, since nodes are not entirely full. The lower and upper bounds on the number of child nodes are typically fixed for a particular implementation. For example, in a 2-3 B-tree (often simply referred to as a 2-3 tree), each internal node may have only 2 or 3 child nodes.
In the narrow sense, a B-tree stores keys in its internal nodes but need not store those keys in the records at the leaves.
B+ tree is a dynamic, multilevel index, with maximum and minimum bounds on the number of keys in each index segment (usually called a "block" or "node"). In a B+ tree, in contrast to a B-tree, all records are stored at the leaf level of the tree; only keys are stored in interior nodes.
A binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:
* The shape property: the tree is an almost complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
* The heap property: each node is greater than or equal to each of its children according to some comparison predicate which is fixed for the entire data structure.
There are two kinds of binary heaps: max-heaps and min-heaps.
Adding to the heap
If we have a heap, and we add an element, we can perform an operation known as up-heap, bubble-up, or percolate-up in order to restore the heap property. We can do this in O(logn) time, using a binary heap, by following this algorithm:
1. Add the element on the bottom level of the heap.
2. Compare the added element with its parent; if they are in the correct order, stop.
3. if not, swap the element with its parent and return to the previous step.
Binary heap is implemented using an array.
Implementation

Resources:

Algorithm - Sorting

Algorithm - Sorting

Insertion sort
Every iteration of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain.
Insertion sort is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. but it's about twice as fast as the bubble sort and somewhat faster than the selection sort in normal situations.However, insertion sort provides several advantages:
# efficient for (quite) small data sets
# adaptive, i.e. efficient for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
# more efficient in practice than most other simple quadratic (i.e. O(n2)) algorithms such as selection sort or bubble sort: the average running time is n2/4[citation needed], and the running time is linear in the best case
# stable, i.e. does not change the relative order of elements with equal keys
# in-place, i.e. only requires a constant amount O(1) of additional memory space
# online, i.e. can sort a list as it receives it.
Online Algorithm
In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from the beginning and is required to output an answer which solves the problem at hand. (For example, selection sort requires that the entire list be given before it can sort it, while insertion sort doesn't.)
// Simple insertion sort.
public static <AnyType extends Comparable<? super AnyType>> void insertionSort( AnyType [ ] a )
{
    for( int i = 1; i < a.length; i++ )
    {
        AnyType tmp = a[ i ];
        int j = i;
        // Insert a[p] into the sorted sublist
        for( ; j > 0 && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
            a[ j ] = a[ j - 1 ];
        a[ j ] = tmp;
    }
}
Shell sort
Shellsort is based on the insertion sort, it improves insertion sort by comparing elements separated by a gap of several positions. This lets an element take "bigger steps" toward its expected position. Multiple passes over the data are taken with smaller and smaller gap sizes. The last step of Shell sort is a plain insertion sort, but by then, the array of data is guaranteed to be almost sorted.
Gap sequence
The gap sequence is an integral part of the Shell sort algorithm. Any increment sequence will work, as long as the last increment is 1. The algorithm begins by performing a gap insertion sort, with the gap being the first number in the gap sequence. It continues to perform a gap insertion sort for each number in the sequence, until it finishes with a gap of 1
// Shellsort, using a sequence suggested by Gonnet.
public static <AnyType extends Comparable<? super AnyType>> void shellsort( AnyType [ ] a )
{
    for( int gap = a.length / 2; gap > 0;
                 gap = gap == 2 ? 1 : (int) ( gap / 2.2 ) )
        for( int i = gap; i < a.length; i++ )
        {
            AnyType tmp = a[ i ];
            int j = i;

            for( ; j >= gap && tmp.compareTo( a[ j - gap ] ) < 0; j -= gap )
                a[ j ] = a[ j - gap ];
            a[ j ] = tmp;
        }
}
Mergesort
http://www.vogella.de/articles/JavaAlgorithmsMergesort/article.html
Merge sort is an O(N*logN) comparison-based sorting algorithm. In most implementations it is stable, meaning that it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm.
Conceptually, a merge sort works as follows
1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
2. Divide the unsorted list into two sublists of about half the size.
3. Sort each sublist recursively by re-applying merge sort.
4. Merge the two sublists back into one sorted list.
// Mergesort algorithm.
public static <AnyType extends Comparable<? super AnyType>> void mergeSort( AnyType [ ] a )
{
    AnyType [ ] tmpArray = (AnyType []) new Comparable[ a.length ];
    mergeSort( a, tmpArray, 0, a.length - 1 );
}
/**
 * Internal method that makes recursive calls.
 * @param a an array of Comparable items.
 * @param tmpArray an array to place the merged result.
 * @param left the left-most index of the subarray.
 * @param right the right-most index of the subarray.
 */
private static <AnyType extends Comparable<? super AnyType>> void mergeSort( AnyType [ ] a, AnyType [ ] tmpArray,int left, int right )
{
    if( left < right )
    {
        int center = ( left + right ) / 2;
        mergeSort( a, tmpArray, left, center );
        mergeSort( a, tmpArray, center + 1, right );
        merge( a, tmpArray, left, center + 1, right );
    }
}
/**
 * Internal method that merges two sorted halves of a subarray.
 * @param a an array of Comparable items.
 * @param tmpArray an array to place the merged result.
 * @param leftPos the left-most index of the subarray.
 * @param rightPos the index of the start of the second half.
 * @param rightEnd the right-most index of the subarray.
 */
private static <AnyType extends Comparable<? super AnyType>> void merge( AnyType [ ] a, AnyType [ ] tmpArray,
        int leftPos, int rightPos, int rightEnd )
{
    int leftEnd = rightPos - 1;
    int tmpPos = leftPos;
    int numElements = rightEnd - leftPos + 1;

    // Main loop
    while( leftPos <= leftEnd && rightPos <= rightEnd )
        if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
            tmpArray[ tmpPos++ ] = a[ leftPos++ ];
        else
            tmpArray[ tmpPos++ ] = a[ rightPos++ ];

    while( leftPos <= leftEnd )    // Copy rest of first half
        tmpArray[ tmpPos++ ] = a[ leftPos++ ];

    while( rightPos <= rightEnd )  // Copy rest of right half
        tmpArray[ tmpPos++ ] = a[ rightPos++ ];

    // Copy tmpArray back
    for( int i = 0; i < numElements; i++, rightEnd-- )
        a[ rightEnd ] = tmpArray[ rightEnd ];
}
How Sorting Algorithm is used in JDK?
for Array of objects, Java's standard sorting method (Arrays.sort() and its derivative Collections.sort()) uses a version of mergesort algorithm(at least in Sun's implementation).
for arrays with built-in types,
for smallest arrays, Arrays.sort() and its derivative Collections.sort() uses Insertion sort, otherwise, it uses quicksort.
Quicksort - O(NlogN)
http://www.vogella.de/articles/JavaAlgorithmsQuicksort/article.html
Quicksort (also known as "partition-exchange sort") is a comparison sort and, in efficient implementations, on average, makes Θ(nlogn) (big O notation) comparisons to sort n items. In the worst case, it makes Θ(n2) comparisons, though if implemented correctly this behavior is rare. Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, it is not a stable sort.
Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.
The steps are:
1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
The base case of the recursion are lists of size zero or one, which are always sorted.
// Quicksort algorithm.
public static <AnyType extends Comparable<? super AnyType>> void quicksort( AnyType [ ] a )
{
    quicksort( a, 0, a.length - 1 );
}
private static final int CUTOFF = 10;
/**
 * Method to swap to elements in an array.
 * @param a an array of objects.
 * @param index1 the index of the first object.
 * @param index2 the index of the second object.
 */
public static final <AnyType> void swapReferences( AnyType [ ] a, int index1, int index2 )
{
    AnyType tmp = a[ index1 ];
    a[ index1 ] = a[ index2 ];
    a[ index2 ] = tmp;
}
/**
 * Internal quicksort method that makes recursive calls.
 * Uses median-of-three partitioning and a cutoff of 10.
 * @param a an array of Comparable items.
 * @param low the left-most index of the subarray.
 * @param high the right-most index of the subarray.
 */
private static <AnyType extends Comparable<? super AnyType>> void quicksort( AnyType [ ] a, int low, int high )
{
    if( low + CUTOFF > high )
        insertionSort( a, low, high );
    else
    {
        // Sort low, middle, high
        int middle = ( low + high ) / 2;
        if( a[ middle ].compareTo( a[ low ] ) < 0 )
            swapReferences( a, low, middle );
        if( a[ high ].compareTo( a[ low ] ) < 0 )
            swapReferences( a, low, high );
        if( a[ high ].compareTo( a[ middle ] ) < 0 )
            swapReferences( a, middle, high );

        // Place pivot at position high - 1
        swapReferences( a, middle, high - 1 );
        AnyType pivot = a[ high - 1 ];

        // Begin partitioning
        int i, j;
        for( i = low, j = high - 1; ; )
        {
            while( a[ ++i ].compareTo( pivot ) < 0 )
                ;
            while( pivot.compareTo( a[ --j ] ) < 0 )
                ;
            if( i >= j )
                break;
            swapReferences( a, i, j );
        }

        // Restore pivot
        swapReferences( a, i, high - 1 );

        quicksort( a, low, i - 1 );    // Sort small elements
        quicksort( a, i + 1, high );   // Sort large elements
    }
}
Quick select - find kth
To implement a quickselect we just modify a quicksort algorithm.
1. If the area you're searching has only one element in it, you have found the element you are looking for, so stop searching.
2. Choose a pivot element (see Selecting a pivot)
3. Swap the pivot element with the last element
4. First, the program looks at pointer L and moves it right, checking each element in turn. As soon as it finds an element whose value is greater or equal to the pivot, it stops. It also stops if it passes pointer R.
5. Now the program moves pointer R left until it finds an element whose value is less than or equal to the pivot, or it has passed pointer L.
6. If pointers L and R have not met, swap the 2 elements they point to, and continue from step 3. Otherwise, swap the last element (which is the pivot because of step 1) with the element that pointer L is at.
7. If the pivot is the element you're looking for, stop searching. If the pivot is to the right (or larger) than the element you're searching for, repeat the quickselect on the left group only, otherwise repeat the quickselect on the right group only.
/**
 * Quick selection algorithm.
 * Places the kth smallest item in a[k-1].
 * @param a an array of Comparable items.
 * @param k the desired rank (1 is minimum) in the entire array.
 */   
public static <AnyType extends Comparable<? super AnyType>> void quickSelect( AnyType [ ] a, int k )
{
    quickSelect( a, 0, a.length - 1, k );
}
/**
 * Internal selection method that makes recursive calls.
 * Uses median-of-three partitioning and a cutoff of 10.
 * Places the kth smallest item in a[k-1].
 * @param a an array of Comparable items.
 * @param low the left-most index of the subarray.
 * @param high the right-most index of the subarray.
 * @param k the desired rank (1 is minimum) in the entire array.
 */
private static <AnyType extends Comparable<? super AnyType>>void quickSelect( AnyType [ ] a, int low, int high, int k )
{
    if( low + CUTOFF > high )
        insertionSort( a, low, high );
    else
    {
        // Sort low, middle, high
        int middle = ( low + high ) / 2;
        if( a[ middle ].compareTo( a[ low ] ) < 0 )
            swapReferences( a, low, middle );
        if( a[ high ].compareTo( a[ low ] ) < 0 )
            swapReferences( a, low, high );
        if( a[ high ].compareTo( a[ middle ] ) < 0 )
            swapReferences( a, middle, high );

        // Place pivot at position high - 1
        swapReferences( a, middle, high - 1 );
        AnyType pivot = a[ high - 1 ];

        // Begin partitioning
        int i, j;
        for( i = low, j = high - 1; ; )
        {
            while( a[ ++i ].compareTo( pivot ) < 0 )
                ;
            while( pivot.compareTo( a[ --j ] ) < 0 )
                ;
            if( i >= j )
                break;
            swapReferences( a, i, j );
        }

        // Restore pivot
        swapReferences( a, i, high - 1 );

        // Recurse; only this part changes
        if( k <= i )
            quickSelect( a, low, i - 1, k );
        else if( k > i + 1 )
            quickSelect( a, i + 1, high, k );
    }
}
Other Simple Sort Algorithms
Bubble sort
Bubble sort works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list.
private static <AnyType> void swap(AnyType[ ] a, int one, int two)
{
    AnyType temp = a[one];
    a[one] = a[two];
    a[two] = temp;
}
public static <AnyType extends Comparable<? super AnyType>> void bubbleSort(AnyType [ ] a )
{
    int out, in;
    int nElems = a.length;
    for(out=nElems-1; out>1; out--)  // outer loop (backward)
    {
        for(in=0; in<out; in++)    // inner loop (forward)
        {
            if( a[in].compareTo(a[in+1]) > 0 )    // out of order?
            {
                swap(a, in, in+1);
            }
        }
    }
}
Selection Sort
Selection Sort is an in-place comparison sort. It has O(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort.
The algorithm works as follows:
1. Find the minimum value in the list
2. Swap it with the value in the first position
3. Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)
public static <AnyType extends Comparable<? super AnyType>> void selectionSort(AnyType[ ] a )
{
    int out, in, min;
    int nElems = a.length;
    for(out=0; out<nElems-1; out++)  // outer loop
    {
        min = out;           // minimum
        for(in=out+1; in<nElems; in++) // inner loop
            if(a[in].compareTo(a[min]) < 0 )     // if min greater,
                min = in;        // we have a new min
        swap(a, out, min);
    }
}


Resources:
Data Structures and Problem Solving Using Java (3rd Edition)
http://users.cis.fiu.edu/~weiss/dsj3/code/code.html
http://en.literateprograms.org/Category:Programming_language:Java

Labels

Java (159) Lucene-Solr (110) All (60) Interview (59) J2SE (53) Algorithm (37) Eclipse (35) Soft Skills (35) Code Example (31) Linux (26) JavaScript (23) Spring (22) Windows (22) Web Development (20) Tools (19) Nutch2 (18) Bugs (17) Debug (15) Defects (14) Text Mining (14) J2EE (13) Network (13) PowerShell (11) Chrome (9) Continuous Integration (9) How to (9) Learning code (9) Performance (9) UIMA (9) html (9) Design (8) Dynamic Languages (8) Http Client (8) Maven (8) Security (8) Trouble Shooting (8) bat (8) blogger (8) Big Data (7) Google (7) Guava (7) JSON (7) Problem Solving (7) ANT (6) Coding Skills (6) Database (6) Scala (6) Shell (6) css (6) Algorithm Series (5) Cache (5) IDE (5) Lesson Learned (5) Miscs (5) Programmer Skills (5) System Design (5) Tips (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) OpenNLP (4) Project Managment (4) Python (4) Spark (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Firefox (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Google Drive (2) Gson (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Bit Operation (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Troubleshooting (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts