This might be a silly question; for all of you who have been in this field for a while, nevertheless, I would still appreciate your insight on the matter - why does an array need to be sorted, and in what scenario would we need to sort an array?
So far it is clear to me that the whole purpose of sorting is to organize the data in such a way that will minimize the searching complexity and improve the overall efficiency of our program, though I would appreciate it if someone could describe a scenario in which it would be most useful to sort an array? If we are searching for something specific like a number wouldn't the process of sorting an array be equally demanding as the process of just iterating through the array until we find what we are looking for? I hope that made sense.
Thanks.
This is just a general question for my coursework.
CodePudding user response：
Sorting brings useful structure in a list of values.
In raw data, reading a value tells you absolutely nothing about the other value in the list. In a sorted list, when you read a value, you know that all preceding elements are not larger, and following elements are not smaller.
So to search a raw list, you have no other choice than exhaustive comparison, while when searching a sorted list, comparing to the middle element tells you in which half the searched value can be found and this drastically reduces the number of tests to be performed.
When the list is given in sorted order, you can benefit from this. When it is given in no known order, you have to ponder if it is worth affording the cost of the sort to accelerate the searches.
Sorting has other algorithmic uses than search in a list, but it is always the ordering property which is exploited.
CodePudding user response：
A lot of different algorithms work much faster with sorted array, including searching, comparing and merging arrays.
For one time operation, you're right, it is easier and faster to use unsorted array. But as soon as you need to repeat the operation multiple times on the same array, it is much faster to sort the array one time, and then use its benefits.
Even if you are going to change array, you can keep it sorted, again it improves performance of all other operations.
CodePudding user response：
Sorting an array can be useful in many situations, but one common scenario is when you need to search for an element in the array. If the array is not sorted, you would need to search through the entire array to find the element you are looking for, which can be time-consuming if the array is large. However, if the array is sorted, you can use a more efficient search algorithm, such as binary search, to find the element more quickly.
Another reason to sort an array is to make it easier to compare elements in the array. For example, if you are looking for the largest or smallest element or kth largest or kth smallest element in the array, you can quickly find it by sorting the array in ascending or descending order, respectively. This can be useful in many applications, such as finding the maximum or minimum value in a set of data.
Also, say you are looking to find the smallest value which is greater than x and you are solving it for q queries, then by sorting it out, later using binary search for each query would result in O(nlgn qlgn) time complexity.
In short, sorting an array can make it easier to search for elements, compare elements, and perform other operations on the data. Although it can require some computational effort to sort an array, this effort is often worthwhile because it can improve the overall efficiency of the program.