Data needs to be sorted in a particular manner before it can be understood or used to perform any operations. Various data sorting techniques are available which will help you sort the given data in an efficient manner.

Sorting is a process of arranging the records of a table or the elements of a list in some sequential order according to a particular criterion.

Types of Sorting
Sorting algorithms can be classified into two categories, namely internal sorting and external sorting.
If all the data to be sorted is kept in the main memory, then internal sorting techniques can be used. Various types of internal sorts are insertion sort, quick sort, heap sort, etc.

External sorting allows us to sort huge amounts of data. In external sorting, there is no need to place the entire data in the main memory. A peripheral device such as tape devices is used as intermediate storage. In this sorting, sequential access is used since it requires less number of passes.For example bubble sort, selection sort.

1. Bubble sort: It is a simple and popular sorting algorithm. Bubble sorting is used frequently because it is relatively easy to understand. In bubble sort the first two elements are read and swapped, if necessary. The second and third elements are then read and swapped again, if necessary and so on. After the first pass, the largest item will be at the end of the array. Similarly, in the second pass, the second largest item will be in position. If n such passes are made, the array would have been sorted. The complexity of bubble sort is O(n2). Complexity of bubble sort in best case is n, in average case is n2 and worst case is n2.

2. Selection sort: The selection sort technique is based upon the extension of the maximum/ minimum technique. The smallest element is selected and it is compared with the element in the first position and swapped if necessary, another remaining element is made to find the next smallest element, which is placed in the next second position and so on. The complexity of selection sort is O(n2).

3. Insertion sort: An insertion sorts is one that sorts a set of values by inserting values into an existing sorted file.The complexity of insertion sort is O(n2).

4. Merge sort: merge sort is a sorting technique which divides the array into sub arrays of size 2 and merge adjacent pairs. We than have approximately n/2 arrays of size 2. The process is repeated until there is only one array remaining of size n.

5. Quick sort: The Quick sort technique is also known as partition exchange sort. In quick sort algorithm a specific element is placed at the right position, in each partition.In partition one of the array elements is chosen as a key value. This key value can be first element of an array. That is if a is an array than key=a[0] and rest of the array element are grouped into two partition such that:One partition contains element smaller than the key valueanother partition contains elements larger than the key value. The complexity of quick sort is O(nlog(n)).

6. Heap sort: Heaps are a kind of trees. The top node of a heap is called the root and this is where the heap begins. It is conceptualized as a binary tree of n nodes. Each node of the tree is numbered consecutively. This allows a heap to be implemented as an array. In a heap, every parent is greater than its child. A reverse heap is one in which the root node is less than the child.

The Brute-Force-AlgorithmIn this algorithm, the pattern and text are compared character by character. In case of a mismatch, the patternis shifted one position to the right and the comparison is repeated, until a match is found or the end of the textis reached. This algorithm is an inefficient method for binary text strings or other text strings consisting of smallnumber of letters.

String matching with finite automataString matching with finite automata is a more efficient approach. It uses a finite automaton to scan foroccurrences of the pattern in the text. In order to use finite automata for the string matching problem, themachine has to be built according to the end string; the resulting automaton will have (m+1) states of whichthe last one is the only accepting state.

The Knuth-Morris-Pratt-AlgorithmKnuth, Pratt and Morris developed this algorithm, in 1976. It works like the finite automaton matcher. Thepattern and text characters are compared in a left-to-right scan. If a mismatch occurs, the algorithm searchesfor the largest suffix of the 'false start', which is also a prefix of the pattern. It thereby determines how far thepattern can be shifted to the right without missing a possible match. The next shifting position is stored in anauxiliary 'next' - table, which is computed in a pre-processing step by comparing the pattern with itself.

Local Variables: Local variables are defined as those variables which are accessible to a program within a particular scope. Theseare accessible to the code within the limited scope, which means they cannot be accessed by the code that isoutside their scope. Local variables are generally used when recursion is desired in programming.

Global Variable: Global variables are those variables, which are declared outside a scope. These variables are available throughout the program. Global variables are used when you want to reuse a certain variable.

Flow-charts are pictorial representation of data describing the process. As they are graphical it is easy to understand and analyze the data. The following the advantages of using Flow-charts:
1. They are graphical, so easy to understand and representation the application.
2. As the whole process is partitioned, data is segregated and it eases the task to write algorithms.
3. It is easy to identity the negative aspect in the process.
4. It reduces the paper work.


Fill in the blanks.
WYSIWYG is the abbreviation for ________
The first pair of square brackets in a three-dimensional array denotes____table__.
The last value in an array will be a ________ character.
FIFO stands for _______________.
A deque is also called a _____________.
ASCII stands for _____________.
Heaps are a kind of _________.
Every node of a tree can be partitioned into ______ parts.
Hashing functions are distributed into ________classes.
A graph consists of a ________ and ________.
——— is used to establish the shortest path between the various switching stations ofa satellite network
The shortest path is found using ________ algorithm.

II. True or False
Arrays are considered data types.
A string is a collection of characters that are in a particular order.
The Quick sort technique is also known as partition exchange sort.
In a heap sort, the elements are first organized into a binary tree.
The 2-3 trees is a type of height balanced tree structure.
Pointers provide an alternate way of accessing information stored in arrays.
In modern programming languages, an integer occupies 4 bytes
Pointers allow the creation of dynamic data structures

Programs..
Write a C program to enter an ASCII value and display the corresponding character
Write a C program to enter 3 scores/marks of the students and display the average and grade of the students in a format.
Write a program to enter a string and display the number of vowels in it.
Write a program to enter a string and display the number of vowels, consonants and spaces.
Write a program to reverse a string
Write a program to enter a range and display the squares of those numbers.
Implement the Preorder, Inorder and Postorder traversing methods and traverse the tree given below.