Searching and Sorting algorithms and techniques

 

An algorithm in terms of Computer Science can be defined as a step-by-step procedure for calculations. Algorithms are used for calculation, data processing, and automated reasoning.

Often, the difference between a fast program and a slow one is the use of a good algorithm for the data set.

Searching Algorithm Techniques:

A search algorithm is an algorithm for finding an item with specified properties among a collection of items.

Searching plays an important role in computer science. Searching for data like a keyword or value is one of the fundamental and the basis of many computing applications, whether on an internet search engine or looking up a bank account balance.

Scientists and researchers have devised and industrialized many advanced algorithms and data structures for the sole purpose of making searches more efficient. And as the data sets become larger and larger, development of better searching algorithms finds immense importance.

Often, the difference between a fast program and a slow one is the use of a good algorithm for the data set.

The following are the commonly used searching algorithms. Click on any of the algorithms listed below to find out its description, working program code, time complexity and various other details related to the algorithm.
1) Linear Search
2) Sequential Search
3) Binary Search

Sorting Algorithm Techniques: 

A sorting algorithm is an algorithm that puts elements of a list or an array in a certain order. Sorting algorithms are an important part of managing data.
More formally, the output must satisfy two conditions:

1. The output is in non-decreasing or non-increasing order (each element is no smaller or bigger than the previous element according in the required output);
2. The output is a permutation (reordering) of the input.

Efficient sorting is very important for optimizing the use of other algorithms which requires the use of the data in sorted form as its input. It is also often useful for increasing the readability of the output.

Each algorithm has particular strengths and weaknesses.

Sorting algorithms are usually judged on the basis of the following efficiencies:

Algorithmic efficiency: number of elements to be sorted is one of the greatest factors that affects the algorithmic efficiency. Generally it is donated by Big-Oh notation O(f(n)). Most of the algorithms in use have an algorithmic efficiency of either O(n^2) or O(n*log(n)).

Space requirement: Most sorting algorithms like heap sort never requires extra space. The arrays can be sorted in place without additional memory. Some sorting techniques like merge sort depends on the data structure used (merge sort on arrays versus merge sort on linked lists, for instance have different memory requirement).

Stability: does the sort preserve the order of keys with equal values? Most simple sorts do just this, but some sorts, such as heap sort, do not.

It is not necessary that soring algorithms with the same efficiency do not have the same speed on the same input. The algorithms must be judged on the basis of their average case, best case, and worst case efficiency.

An ideal sorting algorithm technique should have the following properties:

Stable: Equal keys aren't reordered.

Operates in place, requiring O(1) extra space.

Worst-case O(n•lg(n)) key comparisons.

Worst-case O(n) swaps.

Adaptive: Speeds up to O(n) when data is nearly sorted or when there are few unique keys.

There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application.

The following chart compares most of the commonly used sorting algorithm techniques on the basis of the various benchmarks outlined above.
Click on any of the algorithms listed below to find out its description, working program code, time complexity and various other details related to the algorithm.

	Time
Sort	Average	Best	Worst	Space	Stability	Remarks
Insertion Sort	O(n^2)	O(n)	O(n^2)	Constant	Stable	In the best case (already sorted), every insert requires constant time
Bubble sort	O(n^2)	O(n^2)	O(n^2)	Constant	Stable	Always use a modified bubble sort
Modified Bubble sort	O(n^2)	O(n)	O(n^2)	Constant	Stable	Stops after reaching a sorted array
Selection Sort	O(n^2)	O(n^2)	O(n^2)	Constant	Stable	Even a perfectly sorted input requires scanning the entire array
Heap Sort	O(n*log(n))	O(n*log(n))	O(n*log(n))	Constant	Instable	By using input array as storage for the heap, it is possible to achieve constant space
Merge Sort	O(n*log(n))	O(n*log(n))	O(n*log(n))	Depends	Stable	On arrays, merge sort requires O(n) space; on linked lists, merge sort requires constant space
Quicksort	O(n*log(n))	O(n*log(n))	O(n^2)	Constant	Stable	Randomly picking a pivot value (or shuffling the array prior to sorting) can help avoid worst case scenarios such as a perfectly sorted array.