CODEWITHSUNDEEP
algorithmsorting
bits
bits

Reputation: 1705

Why do algorithms text book uses "nondecreasing" instead of "increasing" to mention sorted array?

Is there any particular reason? or it's just the preference of author? For example here's the Kruskal algorithm from CLRS:

Kruskal's algorithm

Upvotes: 8

Views: 5366

Answers (3)

vipin maurya
vipin maurya

Reputation: 1

The term "nondecreasing" is used in the context of a sorted array to allow for repeated values. In a sorted array, the elements are arranged in ascending order, but there may be repeated elements.

Using the term "increasing" to describe a sorted array implies that the elements are strictly increasing, meaning that there are no repeated values. However, this is not always the case in a sorted array. For example, the array [1, 2, 2, 3, 4] is sorted, but it is not strictly increasing.

Therefore, the term "nondecreasing" is used to describe a sorted array where the elements may remain the same or increase. This term is more general and inclusive than "increasing" and accurately describes the properties of a sorted array, whether or not it contains repeated values.

Upvotes: -1

James Hirschorn
James Hirschorn

Reputation: 8026

Nondecreasing is a strictly weaker requirement. If the algorithm said 'increasing' instead of 'nondecreasing' it would be impossible to order the edges if they had any repeated weights.

Note that I am interpreting increasing as x(n) < x(n + 1), i.e. as strictly increasing.

Upvotes: 1

Simeon Visser
Simeon Visser

Reputation: 122496

Nondecreasing means that the values could stay the same - they don't decrease but they could increase or stay the same.

The values 1, 1, 1, 2 are in nondecreasing order but 1, 2, 3, 4 are increasing.

Upvotes: 30

Related Questions