kernel/common/array.rb
# In-place non-recursive sort between the given indexes using a block.
In-place non-recursive sort between the given indexes using a block.
In - place non - recursive sort between the given indexes using a block .
def qsort_block!(block)
    stack = []
    left_end, right_end = @start, (@total - 1)
    while true
      left, right = left_end, (right_end - 1)   
      eqls_left, eqls_right = (left_end - 1), right_end
      middle = left_end + ((right_end - left_end) / 2)
      low, mid, hi = @tuple.at(left_end), @tuple.at(middle), @tuple.at(right_end)
      segment_size = right_end - left_end
      if segment_size > 1000 and block.call(low, mid) == 1 and block.call(mid, hi) == 1
        semi_left = @tuple.at(left_end + ((middle - left_end) / 2))
        semi_right = @tuple.at(middle + ((right_end - middle) / 2))
        if block.call(low, semi_left) == 1 and block.call(semi_left, mid) == 1 and
           block.call(mid, semi_right) == 1 and block.call(semi_right, hi) == 1
          r = segment_size / 4
          while r > 0
            @tuple.swap(rand(segment_size), rand(segment_size))
            r -= 1
          end
          middle += (right_end - middle) / 2
        end
      end
      @tuple.swap(left_end, right_end)  if block.call(hi, low)  < 0
      @tuple.swap(left_end, middle)     if block.call(mid, low) < 0
      @tuple.swap(middle, right_end)    if block.call(hi, mid)  < 0
      pivot = @tuple.at(middle)
      @tuple.swap(right_end, middle)  
      while true
        while left < right_end
          case block.call(@tuple.at(left), pivot)
          when -1
            left += 1
          when 0
            @tuple.swap(left, (eqls_left += 1))
            left += 1
          else
            break
          end
        end
        while right > left_end
          case block.call(@tuple.at(right), pivot)
          when 1
            right -= 1
          when 0
            @tuple.swap(right, (eqls_right -= 1))
            right -= 1
          else
            break
          end
        end
        break if left >= right
        @tuple.swap(left, right)
      end
      @tuple.swap(left, right_end)
      left, right = (left - 1), (left + 1)
      while eqls_left >= left_end
        @tuple.swap(eqls_left, left)
        left -= 1
        eqls_left -= 1
      end
      unless right >= right_end
        while eqls_right < right_end and right < right_end
          @tuple.swap(eqls_right, right)
          right += 1
          eqls_right += 1
        end
      end
      left_size, right_size = (left - left_end), (right_end - right)
      if left_size < ISORT_THRESHOLD
        isort_block! left_end, left, block
        if right_size < ISORT_THRESHOLD
          isort_block! right, right_end, block
          break if stack.empty?       
          left_end, right_end = stack.pop
        else
          left_end = right
        end
      elsif right_size < ISORT_THRESHOLD
        isort_block! right, right_end, block
        right_end = left
      else
        if left_size > right_size
          stack.push [left_end, left]
          left_end = right
        else
          stack.push [right, right_end]
          right_end = left
        end
      end
    end
  end
def qsort_block! ( block ) stack = [ ] left_end , right_end = @start , ( @total - 1 ) while true left , right = left_end , ( right_end - 1 ) eqls_left , eqls_right = ( left_end - 1 ) , right_end middle = left_end + ( ( right_end - left_end ) / 2 ) low , mid , hi = @tuple . at ( left_end ) , @tuple . at ( middle ) , @tuple . at ( right_end ) segment_size = right_end - left_end if segment_size > 1000 and block . call ( low , mid ) == 1 and block . call ( mid , hi ) == 1 semi_left = @tuple . at ( left_end + ( ( middle - left_end ) / 2 ) ) semi_right = @tuple . at ( middle + ( ( right_end - middle ) / 2 ) ) if block . call ( low , semi_left ) == 1 and block . call ( semi_left , mid ) == 1 and block . call ( mid , semi_right ) == 1 and block . call ( semi_right , hi ) == 1 r = segment_size / 4 while r > 0 @tuple . swap ( rand ( segment_size ) , rand ( segment_size ) ) r -= 1 end middle += ( right_end - middle ) / 2 end end @tuple . swap ( left_end , right_end ) if block . call ( hi , low ) < 0 @tuple . swap ( left_end , middle ) if block . call ( mid , low ) < 0 @tuple . swap ( middle , right_end ) if block . call ( hi , mid ) < 0 pivot = @tuple . at ( middle ) @tuple . swap ( right_end , middle ) while true while left < right_end case block . call ( @tuple . at ( left ) , pivot ) when - 1 left += 1 when 0 @tuple . swap ( left , ( eqls_left += 1 ) ) left += 1 else break end end while right > left_end case block . call ( @tuple . at ( right ) , pivot ) when 1 right -= 1 when 0 @tuple . swap ( right , ( eqls_right -= 1 ) ) right -= 1 else break end end break if left >= right @tuple . swap ( left , right ) end @tuple . swap ( left , right_end ) left , right = ( left - 1 ) , ( left + 1 ) while eqls_left >= left_end @tuple . swap ( eqls_left , left ) left -= 1 eqls_left -= 1 end unless right >= right_end while eqls_right < right_end and right < right_end @tuple . swap ( eqls_right , right ) right += 1 eqls_right += 1 end end left_size , right_size = ( left - left_end ) , ( right_end - right ) if left_size < ISORT_THRESHOLD isort_block! left_end , left , block if right_size < ISORT_THRESHOLD isort_block! right , right_end , block break if stack . empty? left_end , right_end = stack . pop else left_end = right end elsif right_size < ISORT_THRESHOLD isort_block! right , right_end , block right_end = left else if left_size > right_size stack . push [ left_end , left ] left_end = right else stack . push [ right , right_end ] right_end = left end end end end
In-place non-recursive sort between the given indexes using a block.
In - place non - recursive sort between the given indexes using a block .
# Stack stores the indexes that still need sorting # We are either processing a 'new' partition or one that # was saved to stack earlier. # Leave room for pivot # Choose pivot from median # CAUTION: This is NOT the same as #qsort! # "Heuristic" for reverse-sorted # These can be reordered which may help with sorting randomly # distributed elements at the cost of presorted. Be sure to # mark down the correct order though.. # Known position to help partition three ways # Partition # Move pivot back to the middle # Move the stashed == pivot elements back to the middle # Continue processing the now smaller partitions or if # done with this segment, restore a stored one from the # stack until nothing remains either way. # Insertion sort is faster at anywhere below 7-9 elements # We can restore next saved if both of these are getting sorted # Completely done, no stored ones left either # Save whichever is the larger partition and do the smaller first
block
<not_specific>