What is the implication of ascending/descending sorting algorithm with search algorithm? [closed]-CodePudding

I've noticed a lot tutorial of sorting algo returns an ascending array. Obviously this trickles down to their search algorithm implementation that also takes a sorted ascending array as its input.

Is the ascending requirements for sort/search just as a standard of guideline to learn about algorithmic problem solving?

Why isn't a search algorithm be implemented such that it accepts ascending or descending array?

Is it still safe to say for example an insertion sort algorithm that outputs a descending array will still be an insertion sort? In other words, they are just general methodologies subject to small tweaking for its output?

CodePudding user response：

Sorting algorithms are just a general skeleton for you to work on. You can sort an array in ascending order/ descending order, lexicographically (for strings), etc. based on your need. It will still be called 'insertion sort' or 'merge sort' or whatever you are using.

Generally ascending order is shown on educational platforms because that's the most common or basic. No other reason.

The search algorithm you are talking about is most probably Binary Search. You can perform binary search on a descending array too! You just have to make certain minor changes. You can learn more about it here: https://en.wikipedia.org/wiki/Binary_search_algorithm There's also a page on binary search in descending order (equally fast as the standard): https://www.geeksforgeeks.org/search-an-element-in-a-reverse-sorted-array/

CodePudding user response：

Generally, sorting in reverse isn't super interesting to talk about from an algorithmic perspective. We simply swap some > for < and the problem is obviously symmetric with the ascending order sort.

In my experience, in general, when people say "in order", they mean sorted in ascending order. If someone listed the numbers 5,6,7 i'd say they were in order, and if they listed 7,6,5 i'd say they're in reverse order.

In terms of code, a lot of languages implement a comparator function or interface to handle sorting since the kinds of things being sorted are often more complex than simple primitives (numbers, strings) with obvious sort logic. Since the algorithms all still apply as long as you have a concept of "to the left of" and "to the right of" in a sorted array of elements, it's common to write something like this (JS example):

// Comparator function to sort in ascending order
function sortAscending(a, b) {
  if (a > b) return 1; // return a positive number if a > b
  if (a < b) return -1; // negative if b < a
  return 0; // 0 if b == a
}

// Comparator function to sort in descending order
function sortDescending(a, b) {
  return sortAscending(b, a); // look how easy it is to reverse
}

These functions can be used with (eg) built in array#sort

[1,2,3].sort(sortDescending);

As for

Why isn't a search algorithm be implemented such that it accepts ascending or descending array?

You certainly could. Depending on your algorithm, you may need to check what order the array is in. This introduces a performance and complexity cost that is likely greater than just having consumers sort their array in ascending order. Even if your sort logic is a complete black box, you could just reverse the resulting list.