What are the advantages of sorting c plus plus?

Answer 1

It's always much quicker (on average) to search a sorted array than it is to search an unsorted array. This is because you can start in the middle of the array. If the value you seek is there then you're done. If it is not there, but the value you seek is less than the value you found, then you immediately know it must be in the left half of the array, otherwise it must be in the right half. In other words you've reduced the number of items to be searched by 50%. If you repeat the process with this smaller subset you'll reduce the search to 25% of the original array, then 12.5%, and so on. Eventually you'll find the value you're looking for. The worst case for any search is when the value does not exist. But you'll know that as soon as the reduced subset has no elements.

We often use Big-O notation to determine how long we expect an operation to take. We know that we can access any element in an array in constant time, which is denoted O(1). We also know that we can compare values in constant time. So we're really only interested in the cumulative time it takes to search the array. For an array of n elements, the worst case involves inspecting every element, which is denoted O(n), which means O(1)*n, or n constant-time operations. For a large array of say, 1,000,000 elements, that's a lot of constant-time operations.

If we imagine an unsorted array, it will always take O(n) time to determine that a value does not exist. But if we sort the array and inspect each element in turn, it will only take O(n/2) time on average because we can stop searching as soon as we find a value that is greater than the one being sought. However, the worst case is still O(n) if the value being sought happens to be greater than any in the array. But if we start in the middle of a sorted array, the average and worst cases both drop to just O(log n).

Note that there will be some overhead in recalculating the subset boundaries, which is itself a constant-time operation, but this is only of concern when dealing with small arrays. It would, in fact, be much quicker to search small arrays one item at a time. For larger arrays, reducing the problem by 50% on each iteration means the overhead quickly becomes irrelevant, but it only works when the array is sorted. Hence new programmers tend to spend an inordinate amount of time studying sorting algorithms to ensure their programs operate as efficiently as possible.

Some algorithms are better than others, but there is no single algorithm that is suitable in every situation. For instance, insert sort is the ideal sorting algorithm for small subsets, but when dealing with a subset of more than a few hundred items it is woefully inadequate. And while quicksort performs extremely well when dealing with large amounts of data, it is unstable (equal items may not be in the same order they were input) and it doesn't work at all when the amount of data is so enormous that it simply will not fit into working memory. For that you need merge sort which uses multiple tape drives or separately controlled disks to sort the data. With slow-to-access media such as this, efficiency is far more important than raw speed alone.