-- A V Peterson  05-2001
-- AVP minor mods  05-2002

class MY_SORTER
-- various array sorting routines

feature
   
   thing_sort(a : ARRAY[INTEGER]) is
      require
	 a /= Void
      local
	 i : INTEGER
	 temp : INTEGER
      do
	 from
	    i := a.lower
	 until
	    i = a.upper - 1
	 loop
	    if (a.item(i) > a.item(i+1)) then
	       temp := a.item(i)
	       a.put(a.item(i+1), i)
	       a.put(temp, i+1)
	       i := a.lower
	    end
	    i:=i+1
	 end
      end -- thing_sort
   
   selection_sort(a : ARRAY[INTEGER]) is
      require 
	 a /= Void      
      local
	 i : INTEGER
	 small_i : INTEGER
      do
--       io.put_string("Selection sort"); io.put_new_line
	 from
	    i := a.lower
	 until
	    i = a.upper
	 loop
            small_i := smallest_index_in_range(a, i, a.upper)
	    a.swap(i, small_i)
            -- Uncomment this print_array call to check your work in Lab10
--          print_array(a, a.lower, a.upper)
	    i := i + 1
	 end -- loop
      ensure
	 is_sorted(a, a.lower, a.upper)
      end -- selection_sort

   smallest_index_in_range(a : ARRAY[INTEGER]; lo, hi : INTEGER) : INTEGER is
   -- return the index of the smallest value in a in the index range lo to hi
      require 
	 a /= Void 
      local
         j : INTEGER
         small_j : INTEGER
         small_val : INTEGER
      do
--       io.put_string("smallest_index_in_range"); io.put_new_line
         from 
            small_j := lo
            small_val := a.item(lo)
            j := lo + 1
         until
            j > hi
         loop
            if a.item(j) < small_val then
               small_val := a.item(j)
               small_j := j
            end -- if
            j := j + 1
         end -- loop
         Result := small_j
      end -- smallest_index_in_range

   bubble_sort(a : ARRAY[INTEGER]) is
      require 
	 a /= Void      
      local
	 i : INTEGER
	 top : INTEGER
	 interchanged : BOOLEAN
      do
--       io.put_string("Bubble sort"); io.put_new_line
	 from
	    interchanged := true
	    top := a.upper
	 until 
	    (not interchanged)
	 loop
	    from
	       i := a.lower
	       interchanged := false
	    until
	       i = top
	    loop
	       if a.item(i) > a.item(i+1) then
		  a.swap(i, i+1)
		  interchanged := true
	       end -- if
	       i := i + 1
	    end -- loop
            -- Uncomment this print_array call to check your work
--          print_array(a, a.lower, a.upper)
	    top := top - 1
	 end -- loop
      ensure
	 is_sorted(a, a.lower, a.upper)
      end -- bubble_sort
   
   gap_sort(a : ARRAY[INTEGER]) is
      require 
	 a /= Void      
      local
	 i, j : INTEGER
	 top, gap : INTEGER
	 interchanged : BOOLEAN
	 shrink_factor : REAL
      do
	 shrink_factor := 1.3
	 from
	    interchanged := true
	    gap := a.count
	 until 
	    (not interchanged) and gap = 1
	 loop
	    gap := (gap/shrink_factor).truncated_to_integer
	    if gap = 0 then gap := 1 end
	    top := a.upper - gap
	    from
	       i := a.lower - 1
	       interchanged := false
	    until
	       i = top
	    loop
	       i := i + 1
	       j := i + gap
	       if a.item(i) > a.item(j) then
		  a.swap(i, j)
		  interchanged := true
	       end -- if
	    end -- loop
            -- Uncomment this print_array call to check your work
--          print_array(a, a.lower, a.upper)
         end -- loop
      ensure
	 is_sorted(a, a.lower, a.upper)
      end -- gap_sort
   
  
   insertion_sort(a : ARRAY[INTEGER]) is
      require 
	 a /= Void      
      local
	 i, j : INTEGER
	 temp : INTEGER
      do
--       io.put_string("Insertion sort"); io.put_new_line
	 from
	    i := a.lower + 1
	 until
	    i > a.upper
	 loop
	    temp := a.item(i)
	    from
	       j := i
	    until
	       (j = a.lower) or else (a.item(j-1) <= temp)
	    loop
	       j := j - 1
	       a.put(a.item(j), j+1)
	    end -- loop
	    a.put(temp, j)
            -- Uncomment this print_array call to check your work
--          print_array(a, a.lower, a.upper)
            i := i + 1
	 end -- loop
      ensure
	 is_sorted(a, a.lower, a.upper)
      end -- insertion_sort
   
   quick_sort(a : ARRAY[INTEGER]) is
      require 
	 a /= Void      
      local
      do
--       io.put_string("Quick sort"); io.put_new_line
	 qs(a, a.lower, a.upper)
      ensure
	 is_sorted(a, a.lower, a.upper)
      end -- quick_sort
   
   qs(a : ARRAY[INTEGER]; lo, hi : INTEGER) is
   -- Quick sort is a recursive 'divide and conquer' algorithm
      local
	 pivot : INTEGER
	 i, j : INTEGER
	 mid : INTEGER
      do
	 if (hi - lo) > 0 then
--	    print_array(a, lo, hi)
	    mid := (lo + hi)//2
	    pivot := a.item(mid)
	    a.swap(lo, mid)
	    from
	       i := lo
	       j := hi
	    until
	       i = j
	    loop
	       from
	       until
		  (i = j) or (a.item(j) < pivot)
	       loop
		  j := j - 1
	       end -- loop
	       a.put(a.item(j), i)
	       from
	       until
		  (i = j) or (a.item(i) > pivot)
	       loop
		  i := i + 1
	       end -- loop
	       a.put(a.item(i), j)
	    end -- loop
	    a.put(pivot, i)
            -- uncomment next line to see whole array
            -- print_array(a, a.lower, a.upper)
            -- uncomment next line to see current part of array
	    -- print_array(a, lo, hi)

            if i > lo + 1 then
   	       qs(a, lo, i-1)
	    end -- if
	    if i < hi - 1 then
	       qs(a, i+1, hi)
	    end -- if
	    
	 end -- if
	 
      end -- qs 	 
   
   heap_sort(a : ARRAY[INTEGER]) is
      require
	 a /= Void and then a.lower = 1
      local
	 i : INTEGER
      do
	 -- make heap
	 from
	    i := a.lower + 1
	 until
	    i > a.upper
	 loop
	    sift_up(a, i)
	    i := i + 1
	 end -- loop
	 
	 -- sort heap
	 from
	    i := a.upper
	 until
	    i = a.lower
	 loop
	    sift_down(a, i)
	    i := i - 1
	 end -- loop
      end -- heap_sort	 
   
   sift_up(a : ARRAY[INTEGER]; index : INTEGER) is
      local
	 i : INTEGER
	 nextval : INTEGER
      do
	 nextval := a.item(index)
	 from
	    i := index
	 until
	    (i = 1) or else (nextval <= a.item(i//2))
	 loop
	    a.put(a.item(i//2), i)
	    i := i//2
	 end -- loop
	 a.put(nextval, i)
      end -- sift_up
   
   sift_down(a : ARRAY[INTEGER]; index : INTEGER) is
      local
	 i, big_i : INTEGER
	 val : INTEGER
	 finished : BOOLEAN
      do
	 val := a.item(index)
	 a.put(a.item(1), index)
	 from
	    i := 1
	    finished := false
	 until
	    (2*i >= index) or else finished
	 loop
	    big_i := 2*i
	    if (index > 2*i+1) and then (a.item(2*i+1) > a.item(2*i)) then
	       big_i := 2*i+1
	    end -- if
	    if (val < a.item(big_i)) then
	       a.put(a.item(big_i), i)
	       i := big_i
	    else
	       finished := true
	    end -- if
	 end -- loop
	 a.put(val, i)
      end -- sift_down
   
   is_sorted(a : ARRAY[INTEGER]; lo, hi : INTEGER) : BOOLEAN is
   -- Return true if a is sorted in the index range lo to hi; false otherwise
      local
	 i : INTEGER
      do
	 from
	    i := lo + 1
	 until
	    (i > hi) or else (a.item(i) < a.item(i-1))
	 loop
	    i := i + 1
	 end -- loop
	 if (i > hi) then Result := true
	 else Result := false
	 end --if
      end -- is_sorted
   
   print_array(a : ARRAY[INTEGER]; lo, hi : INTEGER) is
   -- Print the array a in the index range lo to hi
      local
	 i : INTEGER
      do
	 from
	    i := lo
	 until
	    i > hi
	 loop
	    io.put_integer_format(a.item(i), 6)
	    if i\\10 = 0 then io.put_new_line end -- if
	    i := i + 1
	 end -- loop
	 io.put_new_line
      end -- print_array
   
end  -- class MY_SORTER