配列が昇順または降順にソートされているか調べる

Question

配列が昇順または降順にソートされているか調べる
例えば、int a[]={1,2,3,4,5}は昇順にソートされていることは明らか。どうやって明らかでない配列に対してそのことを確認する？

int main(void) {int a[]={1,2,3,4,5},b[]={-2,4,3,-3,5};}

Comments

[takasima20]

ソートかけて置換が発生しなかったらok てのは?

[YT0014]

前提条件を明示してください。
ない場合は、ソートされていない場合、及び、要素が1以下の場合、全要素が同一値の場合の仕様を検討する必要があります。

[fana]

> 例えば、int a[]={1,2,3,4,5}は昇順にソートされていることは明らか

「明らか」とか言ってるけども，あなたはどうやって「ソートされている」と 判断/判定 したというのか？
それが「ソートされているか否かを調べる方法」足り得るのでは？

Answer 1

配列の最初から最後までスキャンして、昇順、降順をチェックしましょう。

Answer 2

要素数Nの配列:a[N]に対し

• N=1なら ソートされている。
• 任意の i = 1, 2, 3 ... N-1 (N>1) に対し a[i-1] <= a[i] であれば 昇順でソートされている。
• 任意の i = 1, 2, 3 ... N-1 (N>1) に対し a[i-1] >= a[i] であれば 降順でソートされている。

Answer 3

order は、昇順なら 1、降順なら -1、どちらでもなければ 0 を返す関数です。

#include <stdio.h>

int order(int a[], int n)
{
	int ascend = 0, descend = 0;
	for (int i = 1; i < n; i++) {
		if (a[i-1] < a[i]) ascend = 1;
		if (a[i-1] > a[i]) descend = 1;
		if (ascend && descend) return 0;
	}
	return descend ? -1 : ascend;
}
		
int main(void)
{
	int a[] = {1,2,3,4,5}, b[] = {-2,4,3,-3,5};
	int c[] = {9,8,7,6,5}, d[] = {3,3,3,3,3}, e[] = {7};
	printf("%d\n", order(a, 5));
	printf("%d\n", order(b, 5));
	printf("%d\n", order(c, 5));
	printf("%d\n", order(d, 5));
	printf("%d\n", order(e, 1));
}

実行結果

1
0
-1
0
0

追記
全部同じ値の時は 0 を、昇順と降順の両方阿ある時は 2 を返すようにするには
for文の中の return 0; を return 2; にすればよいでしょう。

追記2
昇順でも降順でもどちらでもいいし、値が全部同じでもソートされているとして 1を返すなら、
for文の中の return 0; はそのままで、最後を return 1; にすればよいでしょう。

Answer 4

配列がソートされているかどうかを判定する関数is_sorted()を書いてみた。
引数は標準ライブラリ関数qsort()と同一である。
なお、nmembが1以下のときはソートされているとみなす。

int is_sorted(
	void *base,
	size_t nmemb,
	size_t size,
	int (*compar)(const void *, const void *))
{
	if (nmemb){
		for (const char *p = (const char *)base; --nmemb; p += size){
			if (compar(p, p + size) > 0){
				return 0;
			}
		}
	}

	return 1;
}

---

2021/12/26 追記
kazuma-sさん 2021/12/25 23:07 のコメントを受け、上記の関数is_sorted()を元に
配列が昇順/降順かを判定する関数is_monotonic()を書いてみた。
この関数は、配列が昇順または全ての値が等しければ1を、降順であれば-1を、そうでなければ0を返す。
なお、nmembが1以下のときは1を返す。

int is_monotonic(
	void *base,
	size_t nmemb,
	size_t size,
	int (*compar)(const void *, const void *))
{
	int order = 0;

	if (nmemb < 2){
		return 1;
	}

	for (const char *p = (const char *)base; --nmemb; p += size){
		int comparison_result = compar(p, p + size);

		if ((order < 0 && comparison_result > 0)
		 || (order > 0 && comparison_result < 0)){
			return 0;
		}

		if (order == 0){
			order = comparison_result;
		}
	}

	if (order < 0){
		return -1;
	}

	return 1;
}

Comments

[kazuma-s]

降順にソートされている場合 0 を返しますね。

[shsh_]

はい。仕様です。