CODEWITHSUNDEEP
arraysalgorithmperlmath
Sumit
Sumit

Reputation: 2023

Reducing time complexity in Perl arrays

I am having a array 

[3, 1, 2, 5, 4, 6]

I want to sort ( Changed sort to arranging in a certain pattern) this as : Move to right and replace the index with next highest integer on right side. Say in this array 3 is replaced by 5, 1 is replaced by 2 and so on..

I want the output as 

[5, 2, 5, 6, 6, 6]

Algorithm :

  1. Start a forloop. It will iterate till last element
  2. Starting from first index it will match with next index and compare the value
  3. If second index is less than first then move to third index
  4. If not change the first index with second index
  5. Try with all the indexes

It is a normal algorithm. But the time complexity is n*n. (No exactly n*n).

Is there a way to reduce the complexity. Because in case of large arrays, it would be very slow. Can somebody provide me algorithm for time complexity n.

Adding code

use strict;
use warnings;

my @arr1 = qw/3 1 2 5 4 6/;
my @arr2;
my ($j, $i);
for($i = 0; $i <= $#arr1; $i++) {
    $j = $i;
    while ( $j < $#arr1) {
        if ( $arr1[$i] < $arr1[$j+1]) {
            push @arr2,$arr1[$j+1];
            last;
        } 
        if ($i == $#arr1) {
            push @arr2,$arr1[$j];
        }
        $j++;
    }

}
push @arr2, $arr1[$#arr1];   ## Pushing the last array index

print @arr2;

Output:

525666

Upvotes: 0

Views: 304

Answers (3)

amon
amon

Reputation: 57600

Your current algorithm can touch one position multiple times, which is inefficient. By the power of recursion, we could do better. Imagine a function that performs your sort until it finds a number higher than some $n:

[3, 1, 2, 5, 4, 6] # start here
#^
[3, 1, 2, 5, 4, 6] # look at next number. It's smaller, so we recurse
#^--^
[3, 1, 2, 5, 4, 6] # in recursion: look at next number, replace
#^  ^--^
#|__|
[3, 2, 2, 5, 4, 6] # return new index. It's smaller, so we recurse
#^     ^
#|_____|
[3, 2, 2, 5, 4, 6] # in recursion: look at next number, replace
#^     ^--^
#|_____|
[3, 2, 5, 5, 4, 6] # return new index
#^        ^
#|________|
[3, 2, 5, 5, 4, 6] # It's larger, so we replace and go to new index
#^--------^
[5, 2, 5, 5, 4, 6] # Look at next number. It's smaller, so we recurse
#         ^--^
[5, 2, 5, 5, 4, 6] # In recursion: replace
#         ^  ^--^
#         |__|
[5, 2, 5, 5, 6, 6] # return new index
#         ^     ^
#         |_____|
[5, 2, 5, 5, 6, 6] # It's larger, so we replace. Go to new index
#         ^-----^
[5, 2, 5, 6, 6, 6] # Done!

The difficult part is to write a function that does this. As we want to write a recursive function, we have to think backwards:

  • [] – empty array (no indices left) sorts to itself
  • [6] – array with single element left sorts to that element
  • [4, 6] → [6, 6] – if the element at the next index is larger, copy it over and the new index is at the next element
  • [5, 4, ...] – if the next element is smaller, recurse at that index.

Example implementation:

sub weird_sort {
  my ($array, $start, $return) = @_;
  $start //= 0;
  my $next = $start + 1;

  while ($next <= $#$array) {
    # check if one is larger
    if ($array->[$start] < $array->[$next]) {
      $array->[$start] = $array->[$next];
      return $next if $return;  # return index to higher levels so that they
                                # can check whether the $next elem is larger.
      $start = $next;
      $next  = $start + 1;
    }
    else {
      $next = weird_sort($array, $next, 1);
    }
  }

  return $next;
}

# called in-place like
weird_sort(\@array);

The next step would be to remove the recursion:

sub weird_sort {
  my ($array) = @_;
  my ($start, $next) = (0, 1);

  my @stack;

  while ($next <= $#$array) {
    # check if one is larger
    if ($array->[$start] < $array->[$next]) {
      $array->[$start] = $array->[$next];
      ($start, $next) = @stack ? (pop(@stack), $next) : ($next, $next + 1);
    }
    else {
      push @stack, $start;
      ($start, $next) = ($next, $next + 1);
    }
  }
}

This seems to work for simple cases, but I'm not entirely certain that this is a general solution.

Upvotes: 5

Vorsprung
Vorsprung

Reputation: 34307

By not using a new array for the reordered data your existing algorithm goes faster. With the test program below on my laptop this is about 60% faster with 1 million elements mildly randomized

use strict;
use warnings;

#my @arr1 = qw/3 1 2 5 4 6/;
my @arr1= ( 1 .. 1000000 );
for (@arr1) { my $r1=rand($#arr1); my $r2=rand($#arr1); @arr1[$r1,$r2]=@arr1[$r2,$r1] }
my @arr2;
my ($j, $i);
for($i = 0; $i <= $#arr1; $i++) {
    $j = $i;
    while ( $j < $#arr1) {
        if ( $arr1[$i] < $arr1[$j+1]) {
            $arr1[$i] = $arr1[$j+1];
            last;
        } 
        $j++;
    }

}

#print @arr1;

Upvotes: 1

That Robin
That Robin

Reputation: 85

I don't think it is N*N complexity. The average distance to a larger value does not increase as the array grows, so your complexity increases at the rate of N not N*N. Why don't you post some code? If it is taking a long time to evaluate, perhaps you have an error in your implementation.

Upvotes: 1

Related Questions