CODEWITHSUNDEEP
phparrayssorting
Abbasi
Abbasi

Reputation: 125

Check if the array can be sorted with a single swap of 2 elements

I am trying to write a function that will check if the array can be sorted with a single swap of the values in the array.

For example: array(1,3,5,3,7) must return true, but array(1,3,5,3,4) must return false.

I tried the following code below, but I'm stuck with it: 

$noOfIterations = 0;

for($x = 0; $x < count($a)-2; $x++) {

    if($a[$x] > $a[$x+1]) {
        $noOfIterations ++;
    }

}

return $noOfIterations >1; 

// The below solution helped as well.

//$arr = [1, 3, 5, 3, 7];  //[1, 3, 5, 3, 4]
$arr = [1, 3, 5, 3, 4];
$sortedArr = $arr;
sort($sortedArr);
print_r(array_intersect_assoc($arr,$sortedArr));

Upvotes: 5

Views: 2457

Answers (5)

glowy
glowy

Reputation: 1

My answer in php.

function oneSwap($A){

  $count=count($A);
  $swaps=0;
  $curr_max = 0;
  $res = false;
  for($i = 0; $i <= $count; $i++) {
    if(isset($A[$i+1])){
      if(($A[$i] >= $A[$i + 1]) && $curr_max >= $A[$i+1]){
        $swaps++;
      }

      if($A[$i] >= $A[$i +1]){
          $curr_max = $A[$i];
      }
    }

  }

  if(($swaps == 1) || ($swaps == 0 && $curr_max ==0)){
    $res = true;
    echo $res;
  } 
} 

oneSwap([3,1,2,8]);
oneSwap([1,2,3]);
oneSwap([1,5,3,3,7]);
oneSwap([3,2,1,8]);
oneSwap([2,1,1,2]);

Upvotes: 0

Rizier123
Rizier123

Reputation: 59681

This should work for you:

(Here I first make a copy of the original array to then sort() it. After this I loop through both arrays with array_map() and look how many position has changed. With array_filter() I sort the elements out where no position has changed. Then you can simply check if 2 or more position has changed and print either FALSE or TRUE)

<?php

    $arr = [1, 3, 5, 3, 7];  //[1, 3, 5, 3, 4]
    $sortedArr = $arr;
    sort($sortedArr);

    $filtered = array_filter(
        array_map(function($v1, $v2){
            return ($v1 == $v2 ?FALSE:TRUE);
        }, $arr, $sortedArr)
    );

    var_dump(count($filtered) > 2 ? FALSE : TRUE);

?>

output:

TRUE  //FALSE

Upvotes: 6

RisingSun
RisingSun

Reputation: 1733

If you really wanna do it with a loop, you can do it with a double loop comparing each value to one another. You need to get a little creative with the comparing. From what I see, your code succeeds on the first array but fails on the second. It fails on the second one because you are only checking 2 adjacent entries and 3 is always less than 4. Or you can keep track of the largest number and count how many numbers are less than that value past it. Also make sure to add to the count if you encounter another bigger value. Hope all this makes sense.

Upvotes: 1

Misunderstood
Misunderstood

Reputation: 5665

What if array is sorted and no swap is needed?

It might help if I knew Why.

Try this, it works for your two example arrays.

function swap($array){
  $prev = 0;
  $count = 0;
  foreach($array as $val){
    if($val < $prev){
       $count++;
    }
    else{
      $prev = $val;
    }
  }
  if($count < 2){return(true);}else{return(false);}
}

Upvotes: 0

Mark Baker
Mark Baker

Reputation: 212412

Execute the sort, then compare the original array with the sorted array using array_intersect_assoc().... if the difference is more than two elements, then the answer is 'no'

Upvotes: 3

Related Questions