The Sapphire move tutor is in fallarbor town just left of the contest hall. But for your scenario, it looks like you would want to got to the move deleter, which is located in lilycove city, to the right of the lilycove department store.
ANSWER TO EDIT: Wild luvdiscs often hold heart scales, so by catching one and removing its item (if it has one) is a way to obtain heartscales. Also, they are often found in rocks, either in the ocean or near it. Using the item finder is also a good way to find heart scales, wich as earlier stated are found in rocks in the ocean and next to it. To get you started I know that there is a heartscale on the East beach of slateport city. I do not have a list of hearstcale locations as I'm not sure there is one.