Notes

note
description : "objects of this class represent array sorters"
author : "MP"

class
ARRAY_SORTER

feature -- Sorters


sort (array_to_sort: ARRAY[INTEGER]): ARRAY[INTEGER]
-- Sort array_to_sort into result without side effect using quicksort.
local
array: ARRAY[INTEGER]
i: INTEGER
do
-- Your code here
-- merge sort
create array.make_empty

array.copy(array_to_sort)
quickSort(array,1,array_to_sort.count)

Result := array
end
feature
partition(array : ARRAY[INTEGER]; low : INTEGER; high : INTEGER) : INTEGER
local
pivot, i, j, temp : INTEGER
do
-- choose the rightmost element as pivot
pivot := array[high]
-- pointer for greater element
i := low - 1

-- traverse through all elements
-- compare each element with pivot
from
j := low
until
j >= high
loop
if array[j] <= pivot then

-- If element smaller than pivot is found
-- swap it with the greater element pointed by i
i := i + 1

-- Swapping element at i with element at j
temp := array[i]
array[i] := array[j]
array[j] := temp
end
j := j + 1
end

-- Swap the pivot element with the greater element specified by i
temp := array[high]
array[high] := array[i+1]
array[i+1] := temp

-- Return the position from where partition is done
Result := i + 1

end
feature

quickSort(array : ARRAY[INTEGER]; low : INTEGER; high : INTEGER)
local
pi : INTEGER
do
if low < high then
-- Find pivot element such that
-- element smaller than pivot are on the left
-- element greater than pivot are on the right
pi := partition(array, low, high)
-- Recursive call on the left of pivot
quickSort(array, low, pi - 1)

-- Recursive call on the right of pivot
quickSort(array, pi + 1, high)
end
end


feature --Output

print_array (arr: ARRAY[INTEGER])
-- Pretty print string array
local
i: INTEGER
do
from
i := 1
print("[")
until
i > arr.count
loop
print (arr[i].out)
if (i < arr.count)
then
print(" ")
end
i := i + 1
end
print ("]")
end
end