In this tutorial, we will study Sorting in Data Structures.
- Sorting is a process of arranging the data into a particular order.
- Definition: Arranging set of data in some kind of order is referred as sorting.
- In sorting data is arranged in ascending or descending order.
Example:-
Telephone directory names of persons arranged in alphabetical order.
Consider a simple example of sorting, We are having 5 random numbers as 10 2 19 1 8
As these are the random number we need to sort the number as, 1 2 8 10 19
We got the sorted list easily but how we sort these random numbers to be sorted. For this, there are various techniques available in a data structure which are different from each other and performed in the different fashion to arrange the data in particular order.
Different techniques of Sorting in Data Structures.
As above we are having different techniques for sorting these techniques has different time complexity.
Time complexity:-
The total time required for execution of a program is known as time complexity.
We will choose anyone sorting technique whose complexity will be suitable for your needs or we use sorting technique which is efficient.
Advantages of sorting
- It will make retrieving and traversing data easy and simple.
- It makes memory management easy.
- Sorting also makes searching easy.
Time complexity table:-
| SORTING TECHNIQUE | BEST CASE | AVERAGE CASE | WORST CASE |
|---|---|---|---|
| Bubble | O(n) | O(n2) | O(n2) |
| Insertion | O(n) | O(n2) | O(n2) |
| Selection | O(n2) | O(n) | O(n) |
| Quick | O(n2) | O(n log n) | O(n log n) |
| Merge | O(n log n) | O(n log n) | O(n log n) |
| Binary | O(n log n) | O(n log n) | O(n2) |
| Radix | O(n2) | O(n log n) | O(n log n) |
| Hip | O(n log n) | O(n log n) | O(n log n) |