Aktív témák

• #25 Terminus_ aktív tag

  2004-10-13 05:05:00 #25

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Terminus_

  aktív tag

  Ez Perlben van, de elég jól kommentezett.
  
  #!/usr/local/bin/perl
  
  
  # A test array
  @sort_array = (4,7,12,3,15,28,1,3,44,13,18);
  
  # Get the ball rolling
  &do_merge_sort(@sort_array, $#sort_array);
  
  #print out the results.
  $end_result = join('', '',@sort_array);
  print $end_result.'' '';
  exit;
  
  sub do_merge_sort {
  &merge_sort(shift, 0, shift);
  }
  
  # Merge sort expects 3 parameters
  # A reference to an array
  # A start index of where to start sorting
  # An end index of where to stop sorting
  sub merge_sort {
  my ($array_ref, $start_index, $end_index) = @_;
  # Only do merge sort if there's a 1 element or greater sized array. No use for empty arrays.
  if ($start_index <; $end_index) {
  # Calculate the middle of the array
  my $mid_index = int(($start_index + $end_index) / 2);
  # Call the merge sort on the left half of the array
  &merge_sort($array_ref, $start_index, $mid_index);
  # Call merge sort on the right half of the array
  &merge_sort($array_ref, $mid_index+1, $end_index);
  # Merge these two arrays together since they will be in order by now
  &merge($array_ref, $start_index, $end_index);
  }
  }
  
  sub merge {
  my ($array_ref, $start_index, $end_index) = @_;
  # calculate the middle of the array
  my $right_index = int(($start_index + $end_index) / 2) + 1;
  my $max_val = $end_index;
  my $left_index = $start_index;
  # While we don't exceed the bounds of the merge keep going.
  while ($right_index <;= $max_val && $left_index <;= $max_val) {
  # If the current item in the right array is bigger than the current
  # item in the left array, we need to move the right item to the current
  # position in the left array and shift the left array to the right by
  # one.
  if ($array_ref->;[$right_index] <; $array_ref->;[$left_index]) {
  # Store the right index value that needs to be brought to the front
  my $tmp = $array_ref->;[$right_index];
  # Shift the left array over by 1 to the right to make room for the
  # smaller value
  for ($i = $right_index; $i >;= $left_index; $i--) {
  $array_ref->;[$i] = $array_ref->;[$i-1];
  }
  # Swap in the value and change where the array indexes are located
  $array_ref->;[$left_index] = $tmp;
  $left_index++;
  $right_index++;
  } else {
  # If the left item is greater than the right item you don't need to
  # do any swapping since it's already keeping the sort order correct
  # just make sure that the left index doesn't catch up to the right
  # index or you're already done sorting this level!
  $left_index++;
  if ($left_index >;= $right_index) { return; }
  }
  }
  }
  
  
  
  Kár, hogy a struktúráltságát elvesztette :(
  
  
  [Szerkesztve]

  -

Aktív témák