Lily’s Homework

Lily’s homework

Problem Statement

Whenever George asks Lily to hang out, she’s busy doing homework. George wants to help her finish it faster, but he’s in over his head! Can you help George understand Lily’s homework so she can hang out with him?

Consider an array of n distinct integers, arr= [a[0], a[1],…,a[n-1]]. George can swap any two elements of the array any number of times. An array is beautiful if the sum of |a[i] — a[i-1]| among 0 < i < n is minimal.

Given the array arr, determine and return the minimum number of swaps that should be performed in order to make the array beautiful.

Considerations

Let’s not get distracted by irrelevant details and try to find where the problem is and focus all undivided attention to it.

The minimum swaps to sort an array problem is an algorithmic problem that asks for the minimum number of swaps required to sort an array of elements.

Swaps

A swap is an operation that exchanges the positions of two elements in an array.

Graphs

The problem can be solved by first visualizing the array as a graph. In this graph, each node represents an element in the array, and there is an edge between two nodes if the corresponding elements are not in their correct order. The minimum number of swaps required to sort the array is then equal to the number of cycles in this graph.

Cycle

A cycle in a graph is a path that starts and ends at the same node, and does not visit any node more than once. In the context of the minimum swaps to sort an array problem, a cycle represents a group of elements that are in the wrong order, but can be sorted by swapping two elements in the group.

The algorithm

The algorithm is based on Amila Rukshan but it deviates a bit in order to make the algorithm clear and concise.

1. The function lilysHomework first defines two functions: ascendingOrder and descendingOrder. These functions are used to sort the array in ascending and descending order, respectively.
2. The function then calls the calculateSwaps function twice, once with the array sorted in ascending order and once with the array sorted in descending order.
3. The calculateSwaps function takes two arguments: the array to be sorted and the sorting function. The function first makes a copy of the array.
4. The function then sorts the copy of the array using the sorting function.
5. The function then creates a map that maps each element in the array to its correct position.
6. The function then creates an array of boolean values, where each value indicates whether the corresponding element in the array has been visited.
7. The function then loops over the original array.
8. For each element in the array, the function checks if the element has been visited. If the element has not been visited, the function starts a cycle.
9. The function loops over the array until it finds a visited element. For each element in the loop, the function marks the element as visited and increases the cycle size.
10. When the function reaches a visited element, it stops the loop and adds the cycle size to the number of swaps.
11. The function returns the number of swaps.

The minimum swaps to sort an array

Calculate swaps

Resources

Google Bard conversation help me to write and give me a draf to put my ideas together