17.1. Sorting: Concluding Remarks

Let us look back on all the different sorting algorithms that we have considered. So, one of the important criteria that we should not forget is that, sorting often happens in phases. So, we might have a list of names of people say Aswin, Bharathi, Chander and Deepa. So, we have sorted this in order and they might have got some marks in an exam. So, they may be got 60, 43, 60 and 95, now we might want to sort this by marks. So, when we sort this by marks of course, we need to exchange the position of Bharathi and Ashwin, but we do not want to exchange the position of Aswini and Chander.

This chunk introduces the idea that sorting can involve multiple criteria or phases. For instance, if we first sort names alphabetically and then want to sort them by marks, we need to ensure that the alphabetical order remains stable for names that have equal marks. This means that when two students, like Ashwin and Chander, both have the same mark, their initial order (alphabetical) should be maintained.

Imagine you are organizing a set of books on a shelf. First, you arrange them by author name and later you decide to organize them by publication year. If two authors published their books in the same year, you still want their books to appear in alphabetical order based on their names. This reflects stable sorting where initial arrangements are preserved during subsequent sorting.

So, this is called stable sorting that is there was, so very often when you are sorting a sorting on one attribute, but there may be other attributes. So, data item is not typically a unique values, it is not just a number, but it is a… So, you are taking names, marks and various other addresses may be phone number and you might sort on difference.

The concept of stable sorting is crucial as it maintains the order of equal values based on prior sorting criteria. For example, if you have multiple attributes such as name and marks, stable sorting ensures that when you sort by marks and two students have the same grade, their alphabetical order from the previous sort is preserved.

Think about sorting a list of employees first by department and then by hire date. If two employees were hired on the same day, we still want them to appear in alphabetical order within their department. In this way, stable sorting helps maintain clarity and organization in our information.

So, quick sort as shown is not a stable operation, so remember that we took that at a bit and in the at least in our implementation what we did was we constructed this lower set and then the upper set to the right of it...

Unstable sorting algorithms, like quicksort and selection sort, can disrupt the initial order of equal elements. In quicksort, the swapping of elements during the partitioning phase can lead to a loss of original order, while selection sort similarly moves elements around that can disturb order when certain conditions are met.

Imagine you're rearranging chairs in a room already set up in a specific order based on height. If you decide to move the tallest chair to the front without considering its relationship with the others, you may end up reversing the order inadvertently. This illustrates how careless rearranging can disrupt existing organized information.

What about merge sort? Well, merge sort would normally be stable provided… all we want that something to the right should not go to the left of something in the original array...

Merge sort is generally stable because it preserves the order of equal elements. When merging two sorted arrays, if we encounter equal elements, we should select from the left array first, ensuring that the earlier order is maintained. This careful selection is crucial for maintaining the overall stability of the sorting process.

Picture a relay race where runners are sorted by their times. If two runners finish at exactly the same time, we want to keep them in the order they started in the race, ensuring that their original positions are respected even after sorting by time.

And another criteria, which is related to what we just saw is that we have only concentrated on the number of steps required in order to compare and exchange two elements...

Sorting isn't just about the number of comparisons or swaps; it can also take into account the distance data moves across an array. Sorting algorithms that swap adjacent elements, like bubble sort, can be more efficient in certain contexts than those that involve larger movements.

Think about moving boxes in a warehouse. It's easier and less costly to slide a box over a short distance rather than lifting it and moving it across the entire room. Just like sorting, minimizing movement can lead to better efficiency.

So, very often a question is asked which sort is best. So, unfortunately it turns out that no single sorting algorithm always guarantees to be the best...

The effectiveness of a sorting algorithm often depends on the specific context and data type. While quicksort may be optimal for simple data, other scenarios might require different algorithms, like external merge sort when dealing with large datasets.

Choosing a sorting method is like picking the right tool for a job. Just as you wouldn't use a hammer for everything—sometimes you need a screwdriver or a saw—different sorting algorithms are more suited for particular types of data and sorting requirements.

We have seen merge sort as an order n log n algorithm, there are other n log n algorithm we will see one later on this course for heap sort...

Many sorting algorithms can be combined or used in hybrid forms. For example, one might start sorting with a complex algorithm like quicksort for larger datasets, then switch to a simpler algorithm like insertion sort when the dataset becomes smaller.

Consider making a dish that starts with complex steps (like baking a cake) but needs close attention towards the end (like frosting the cake). Similarly, starting with sophisticated algorithms and using simpler ones later can lead to efficient sorting results.

--