Sorting - Arrangement of elements in non-decreasing or non-increasing order.
Why is the arrangement of elements in non-decreasing or non-increasing order, why is not increasing or decreasing order?
Ans - if you have an input of duplicate elements, then you can never say increasing or decreasing.
I will explain to you why...
suppose input is 12 6 4 7 8 6 3
and you have to sort the number in the increasing direction, so the output will be
3 4 6 7 8 12.
The input has 6 numbers but the output has only 5 numbers. 6 is not greater than 6.
If you are searching elements in increasing order then you have to take only one 6. But a non-decreasing word can help to get the second 6.
Types of Sorting
1. Comparison Sort - When sorting is based on comparing two elements.
2. Inplace Sort - means that the input and output occupy the same memory storage space. It uses space complexity is theta (1).
3. Stable Sort - If ai = aj & i < j & after sorting ai & aj are placed at u & v positions respectively then u < v.
This means the first come first serve policy is applied in the stable sort.
4. Internal Sort - Sorting is based on elements of main memory. Example - Binary Search Tree
5. External Sort - Sorting is based on elements of secondary memory. Example - B and B+ trees
6. Efficient Sort - Time & Space complexity is minimum.
7. Data Sensitive Sort - If best case ≠ worst case.
0 Comments