Sorting algorithm is an algorithm that puts elements of a list in a certain order . The most-used orders are numerical order and lexicographical order.
Sorting algorithm classification:
Stability-Maintaining relative order of records with equal keys.
Methods applied like insertion,exchange,,selection,merging etc.
Sorting is a process of linear ordering of list of objects
Sorting techniques are categoried into:
1. Internal sorting
2. External sorting
It takes the place in the main memory of a computer.
Eg: Bubble sort,Insertion sort,Shell sort,Quick sort,Heap Sort,etc
It takes the place in secondary memory of a computer,Since the number of objects to be stored is too large to fit in main memory.
Eg:Merge sort,Multiway Merge,Polyphase merge.
Selection sort is a sorting algorithm, specifically 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. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.
Analysis of selection sort:
Effectively, we divide the list into two parts: the sublist of items already sorted, which we build up from left to right and is found at the beginning, and the sublist of items remaining to be sorted, occupying the remainder of the array.
It have n(n-1) comparisios.
Worest case performance O(n2)
Best case performance O(n2)
Average case performance O(n2)
1. It is very simple to implement.
1. If list is very large it takes long time to evaluate.
C Program To Implement Selection Sort
- Find the minimum value in the list
- Swap it with the value in the first position
- Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)
CPP Program To Implement Selection Sort