Analysis of Sorting Algorithms And Sorting Techniques With Time Complexity

 Sorting Concepts :

Data can be arranged either in ascending order or in descending order with is called sort order.

i. Sort Stability :

1. A sorting algorithm is said to be stable if it preserves the order for all records with deuplicate keys means if for all records, if key of records are equal then the equal key records are appeared in sorted table as same as the order in which they appeared unsorted table.
2. Examples of stable sorting algorithms are bubble sort, merge sort and insertion sort.

ii. Efficiency of sorting Algorithms : 

1. The complexity of sorting algorithm is analyzed using the amount of time required for running the program and hte amount of space requied for the program.
2. To get the amount of time required, we have to estimate the number of comparisons and data movement required to sort the data.
3. During the sorted process, the data are traversed many times. Each traversal of the data is referred to as a sort pass. Various sorting methods are nalyzed in the cases like - best case, worst cae or average case.

iii. Objective of sorting algorithms :

1. Minimize exchanges of data an dreduce processing time.
2. Iin case of large data, move data form secondary storage.
3. If possible, retain all the data in main memory; so that random access into an arrayy can be effectively used.
4. In most of the sorting algorihms, the time complexity ranges form o(n log n ) to O (n2).
5. In efficiency of sorting method is measured by the run time used for execution of algorithm. One sorting method may use different runtimes on different machines.
6. Normallyy, those programs that requires less time, require more space and vice versa. But some algorithm use both minimum time and minimum space having complexity O(log n).

iv. Sorting Techniques With Time Complexity :

1. Sorting is a technique to rearrange the elements in ascending or desending order, which can be numerical, lexicographical, or any use-defined order.
2. For example, consider a telephone directory which consists of four fields; phone number, name, address, pin code.
3. so, a large data is maintained in the form of  records. If we want to search a phone number and name is in alphabetically sorted, then we can search easily. It would be very difficult if records were unsorted.

V. Two Different Types of Sorting Techniques : 

1. Internal Sorting : 

1. This method uses only the primary memory during sorting Process. All data items are held in main memory and no secondary memory is required this sorring process. 
2. if all the data that is to be sorted can be accmmodated at a time in memory is called internal sorting. 
3. There  is a limitaion for internal sorts; they can onlyy process relatively small lists due to memory constraints.
4. Example : Bubble sort, Insertion sort, Quick Sort.

2. External Sorts :

1. Sorting large amount of data requires external or secondary memory.  
2. This process uses external memory such as Hard Disk, Floppy Disk, Magnetic Tape etc. to store the data which is not fit into the main memory. 
3. So,primary memory holds the currently being sorted data onlyh. All external sorts are based on process of merging.
4. Different parts of data are sorted separately and merged together. 
5. Example : Merge Sort.