KInds of Sorting

Selection Sort

• It performs sorting by repeatly putting the largest element in the unprocessed portion of the array to the end of the this unprocessed portion until the whole array is sorted.
• Is an easy-to-program, but very inefficient sorting algorithm.

Algorithm

1. 1st iteration selects the smallest element in the array, and swaps it with the first element.
2. 2nd iteration selects the 2nd smallest element (which is the smallest element of the remaining elements) and swaps it with the 2nd element.
3. The algorithm continues until the last iteration selects the 2nd largest element and swaps it with the 2nd last index, leaving the largest element in the last index.

This are some link to know more about selection sort:

• http://en.wikipedia.org/wiki/Selection_sort
• http://www.cs.ust.hk/faculty/tcpong/cs102/summer96/aids/select.html
• http://lionel.textmalaysia.com/selection-sort.html

Insertion Sort

Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:

• Simple implementation
• 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(n²) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
• 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

Most humans when sorting—ordering a deck of cards, for example—use a method that is similar to insertion sort.

Source: Wikipedia, the free encyclopedia

Here are some links to follow to know more about insertion sort:

• http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/insert/insertionen.htm

• http://en.wikipedia.org/wiki/Insertion_sort

• http://www.softpanorama.org/Algorithms/Sorting/insertion_sort.shtml

Bubble Sort

Bubble sort is a simple sorting algorithm that 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. Because it only uses comparisons to operate on elements, it is a comparison sort.

From Wikipedia, a free Encyclopedia

Algorithm

1. Iterates thru every element of the array, starting with the first 2 elements.

1. 
   
2. If left element is bigger than right element, swap them.

1. 
   
2. Repeat step #1 and #2 until there are no more swaps.

Shell sort

The idea of Shell sort is the following:

1. arrange the data sequence in a two-dimensional array
2. sort the columns of the array

The effect is that the data sequence is partially sorted. The process above is repeated, but each time with a narrower array, i.e. with a smaller number of columns. In the last step, the array consists of only one column. In each step, the sortedness of the sequence is increased, until in the last step it is completely sorted. However, the number of sorting operations necessary in each step is limited, due to the presortedness of the sequence obtained in the preceding steps.

Example: Let 3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2 be the data sequence to be sorted. First, it is arranged in an array with 7 columns (left), then the columns are sorted (right):

3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2

3 3 2 0 5 1 5 7 4 4 0 6 1 6 8 7 9 9 8 2

Data elements 8 and 9 have now already come to the end of the sequence, but a small element (2) is also still there. In the next step, the sequence is arranged in 3 columns, which are again sorted:

3 3 2 0 5 1 5 7 4 4 0 6 1 6 8 7 9 9 8 2

0 0 1 1 2 2 3 3 4 4 5 6 5 6 8 7 7 9 8 9

Now the sequence is almost completely sorted. When arranging it in one column in the last step, it is only a 6, an 8 and a 9 that have to move a little bit to their correct position.

This are some links to know more about shell sort:

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

http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm

http://goanna.cs.rmit.edu.au/~stbird/Tutorials/ShellSort.html

Empirical Analysis, Algorithm Analysis and Big oh Notation

Empirical Analysis

Is an analysis that is based on your observation, experience or experiments.

As I have research there are many steps to achieve an empirical analysis:

• Choose on the essential process.
• Think and choose your input sample (range, size,...).
• Convert the algorithm to a program
• Create a sample of inputs.
• Execute the program;
• Evaluate the data.

Algorithm Analysis

Is an analysis to determine the amount of the resources and the efficiency of the algorithm that you use in your program. And also as we analyze an algorithm we can determine the running time of a program as a function of its inputs, determine the total or maximum memory space needed for program data, determine the total size of the program code, determine whether the program correctly computes the desired result, determine the complexity of the program--e.g., how easy is it to read, understand, and modify, and determine the robustness of the program--e.g., how well does it deal with unexpected or erroneous inputs?

Big oh Notation

The Big-O notation describes the behavior of a function for big inputs. It tries to capture the core of a function.

The Union-Find Algorithm

A Union-Find Algorithm is an algorithm that maintains and combines different sets. It performs two useful operations on a data structure such as:

• Find determine which set a particular element is in. It is useful for determining if two elements are in the same set.
• Union combine or merge two sets into a single set.

Because it supports these two operations, a disjoint-set data structure is sometimes called a union-find data structure or merge-find set. The other important operation, MakeSet, which makes a set containing only a given element, is generally trivial. With these three operations, many practical partitioning problem can be solved.

In order to define these operations more precisely, some way of representing the sets is needed. One common approach is to select a fixed element of each set, called its representative, to represent the set as a whole. Then, Find(x) returns the representative of the set that x belongs to, and Union takes two set representatives as its arguments.

A simple approach to creating a disjoint-set data structure is to create a linked list for each set. The element at the head of each list is chosen as its representative.

MakeSet creates a list of one element. Union appends the two lists, a constant-time operation. The drawback of this implementation is that Find requires (n) or linear time.

This can be avoided by including in each linked list node a pointer to the head of the list; then Find takes constant time. However, Union now has to update each element of the list being appended to make it point to the head of the new combined list, requiring (n) time.

When the length of each list is tracked, the required time can be improved by always appending the smaller list to the longer. Using this weighted-union heuristic, a sequence of m MakeSet, Union, and Find operations on n elements requires O(m + nlog n) time. For asymptotically faster operations, a different data structure is needed.

Source: An article from Wikipedia, the free Encyclopedia

Definition

The defining properties of the subset ADT are union and find. It is used to maintain sets of subsets. In itially there are n subsets each consisting of 1 element. These elements may be assumed to be the numbers 0 to n - 1. Gradually subsets get fused (union) together and become larger. At the same time there are queries (find operations) asking for the unique identifier, the name of the subset to which an element belongs. Initially the name might be taken equal to the single number in the subset. Later it might be one of the numbers in the subset, possibly, but not necessarily, the smallest number. The only important thing is that find(x) and find(y) return the same values when x a nd y belong to the same subset, and different values when they belong to different subsets.

The above leaves much freedom in how to perform the unions and how to choose the names. A possibility is to apply a rule like "add first to second", meaning that an operation union(x, y) is performed by adding all elements of the subset in which x lies to the subset in which y lies. The new name for this set then becomes the name of the subset in which y lies.

The subset ADT may sound unimportant, but it shows up everywhere. Subsets are the canonical example of the mathematical concept of equivalence relations. An equivalence relation is a binary operator "~" on elements of a set with the property that

• a ~ a, for all a: ~ is reflexive
• a ~ b implies that b ~ a, for all a and b: ~ is symmetric
• a ~ b and b ~ c implies that a ~ c, for all a, b and c: ~ is transitive

If we read "~" like "in the same subset as", then all three properties are satisfied. The most important example of an equivalence relation is "is reachable": in a road system with two-way roads, all three properties are satisfied. Thus, the subset ADT can be used to compute something called the "connected components" of a graph.

The subset ADT allows to maintain equivalence relations dynamically: relations may be added by applying the union operation. The only limitation is that there is no de-union: once unified, the sets cannot be split anymore. This latter feature would be much more expensive to implement, in particular it would require that all previous operations are recorded.

There are several implementations, ranging from extremely simple giving modest performance (one operation O(1), the other O(n)), to slightly less simple giving excellent performance (almost constant time for both operations).

Author:Jop Sibeyn

And here some link to know how this algorithm works: http://www.users.csbsju.edu/~lziegler/CS239/UnionFind.html