Topics Covered
- Definition of sorting
- Types of sorting
- Stable Sort
- Unstable Sort
- Adaptive Sorting
- Non-adaptive sorting
- in-place sorting
- not-in-place sorting
Definition
Sorting in the arrays means arranging the elements of the array in a certain order. It is like the arrangement of the data in proper order. Sorting can be done in ascending (increasing) or descending (decreasing) order. Sorting makes the searching of the data easier by arranging it in proper order. There are various algorithms like bubble sort, merge sort, etc. that are designed for sorting. Every algorithm has its own functionalities and properties and is used in certain places.
- Ascending order
- list[i] <= list[i+1] , 0 < i < n-1
- Descending order
- list[i] >= list[i+1] , 0 < i < n-1
Example: Suppose we have a record of students of an university. Record has the following data:
Student Roll Number
Student Name
Student DOB
Student Branch
Here, the roll number can be taken as a key for sorting because it is unique for every student and arranged in sequence. We can arrange the roll numbers in their increasing or decreasing order. If, we have to search for an student of roll no. 232 so we start our searching from 200 not from zero.Types of Sorting in arrays
- Stable Sort
- Unstable Sort
- Adaptive Sorting
- Non-adaptive sorting
- in-place sorting
- not-in-place sorting
1. Stable Sort
A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in the sorted output as they appear in the unsorted input. Examples: Insertion sort, Bubble sort, Merge sort and Binary tree sort.
2. Unstable Sort
A sorting algorithm is said to be unstable if there are two or more objects with equal keys which don’t appear in the same order before and after sorting. Examples: Heap sort, Quick sort, and Selection sort.
3. Adaptive Sorting
Adaptive sorting algorithms used the advantage of already sorted elements in the array or the list. While sorting it will not disturb the elements which are already sorted. Examples: Bubble Sort, Insertion Sort, and Quick Sort.
4. Non-adaptive Sorting
Non-adaptive algorithms does not take the advantage of the already sorted elements in the array or the list. They try to sort each and every element of the array and make the array sorted. Examples: Merge Sort, Selection Sort, and Heap Sort.
5. In-place sorting
Sorting algorithms may require some extra space for comparison and temporary storage of few data elements. These algorithms do not require any extra space and sorting is said to happen in-place, or for example, within the array itself. This is called in-place sorting. Example: Bubble Sort.
6. Not-in-place sorting
In some sorting algorithms, the program requires space that is more than or equal to the elements being sorted. Sorting which uses equal or more space is called not-in-place sorting. Example: Merge Sort.
