Check to See If an Array Is Already Sorted

Check array in JS - is list sorted?

var str = ["1,2,3,4,5", "1,2,8,9,9", "1,2,2,3,2"];

for (var i in str){

    var list = str[i].split(',').map(Number);

    console.log(list);

    var isSorted = true;

    for(var j = 0 ; j < list.length - 1 ; j++){

        if(list[j] > list[j+1]) {

            isSorted = false;

            break;

        }

    }

    console.log(isSorted);

}

Check to see if an array is already sorted?

It looks like a generic abstraction, let's open Enumerable:

module Enumerable
  def sorted?
    each_cons(2).all? { |a, b| (a <=> b) <= 0 }
  end
end

[["a", 3], ["b", 53],["c", 2]].sorted? #=> true

Notice that we have to write (a <=> b) <= 0 instead of a <= b because there are classes that support <=> but not the comparator operators (i.e. Array), since they do not include the module Comparable.

You also said you'd like to have the ability "to check for order based on some arbitrary parameter":

module Enumerable  
  def sorted_by?
    each_cons(2).all? { |a, b| ((yield a) <=> (yield b)) <= 0 }    
  end
end

[["a", 3], ["b", 1], ["c", 2]].sorted_by? { |k, v| v } #=> false

Using lazy enumerables (Ruby >= 2.1), we can reuse Enumerable#sorted?:

module Enumerable  
  def sorted_by?(&block)
    lazy.map(&block).sorted?
  end
end

How to Check if an array is already sorted in php

Here, you can try with this code:

<?php

$sort = array(
    0 => 50,
    1 => 100,
    2 => 150
);

$default = $sort;
sort($sort);

$flag = true;
foreach($sort as $key=>$value)
    if($value!=$default[$key])
        $flag = false;  

if($flag)
    echo "Already sorted";  
else
    echo "Not Already sorted";  
?>

Fastest way to check if an array is sorted

You will have to visit each element of the array to see if anything is unsorted.

Your O(n) approach is about as fast as it gets, without any special knowledge about the likely state of the array.

Your code specifically tests if the array is sorted with smaller values at lower indices. If that is not what you intend, your if becomes slightly more complex. Your code comment does suggest that is what you're after.

If you were to have special knowledge of the probable state (say, you know it's generally sorted but new data might be added to the end), you can optimize the order in which you visit array elements to allow the test to fail faster when the array is unsorted.

You can leverage knowledge of the hardware architecture to check multiple parts of the array in parallel by partitioning the array, first comparing the boundaries of the partition (fail fast check) and then running one array partition per core on a separate thread (no more than 1 thread per CPU core). Note though that if a array partition is much smaller than the size of a cache line, the threads will tend to compete with each other for access to the memory containing the array. Multithreading will only be very efficient for fairly large arrays.

Need to check if array is sorted using a function in C

For starters the function should be declared like

int Is_Sorted( const int* A, size_t n );

that is at least the first parameter should have the qualifier const because the passed array is not being changed within the function.

The variables tempcr and tempdcr were not initialized and have indeterminate values. So the function has undefined behavior. You have to initialize them like

int tempcr = 0, tempdcr = 0;

There is no sense to continue iterations of the loop if it is already known that the array is unsorted because it is inefficient.

Moreover the function has a logical bug.

Consider the array { 0, 0, -1 }

In this case in the first iteration of the loop the variable tempcr will be increased due to the if statement

if (A[i]<=A[i+1]){
    tempcr++;
}else if (A[i]>=A[i+1]){
tempdcr++;
}

But in the second iteration of the loop the variable tempdcr will be increased.

So the function will report that the array is unsorted though it is sorted in the descending order.

I would define the function the following way

int is_sorted( const int a[], size_t n )
{
    size_t ascending = 0, descending = 0;

    for (size_t i = 1; ( ascending == 0 || descending == 0 ) && i < n; i++)
    {
        if ( a[i-1] < a[i] ) ++ascending;
        else if ( a[i] < a[i-1] ) ++descending;
    }

    return descending == 0 ? 1 : ( ascending == 0 ? -1 : 0 );
}

If the passed array has all elements equal each other then the function considers it as sorted in the ascending order.

As pointed @chux - Reinstate Monica in his answer instead of counting elements you can use the corresponding variables as boolean objects. In this case the function can look like

int is_sorted1( const int a[], size_t n )
{
    int ascending = 0, descending = 0;

    for (size_t i = 1; ( ascending == 0 || descending == 0 ) && i < n; i++)
    {
        if ( a[i-1] < a[i] ) ascending = 1;
        else if ( a[i] < a[i-1] ) descending = 1;
    }

    return descending == 0 ? 1 : ( ascending == 0 ? -1 : 0 );
}

How to continuous check if array is sorted after removes/adds/updates of elements

Here's the logic of nondecreasing (duplicate it with a twist for nonincreasing).

Keep track of the number of adjacent pairs x, y such that x > y, i.e., decreasing pairs. The list is nondecreasing if and only if this number is zero.

To insert b between a and c (a, c => a, b, c):

num_decreasing_pairs -= a > c
num_decreasing_pairs += a > b
num_decreasing_pairs += b > c

To remove b between a and c (a, b, c => a, c):

num_decreasing_pairs -= a > b
num_decreasing_pairs -= b > c
num_decreasing_pairs += a > c

To update b1 to b2 between a and c (a, b1, c => a, b2, c):

num_decreasing_pairs -= a > b1
num_decreasing_pairs -= b1 > c
num_decreasing_pairs += a > b2
num_decreasing_pairs += b2 > c

All of these statements should be guarded by ifs that check that the examined elements are present (edge cases).

Pythonic way to check if a list is sorted or not

Here is a one liner:

all(l[i] <= l[i+1] for i in range(len(l) - 1))

If using Python 2, use xrange instead of range.

For reverse=True, use >= instead of <=.

Check if Array is sorted in Log(N)

To check if an array is sorted with no previous knowledge, you need to look at all elements at least once, so O(n) is the minimum.

---

Related Topics