What would be the optimal solution to the following problem : Given a list of values (fe : numbers ranging from 0-14) how would you sort them by using only swap operations (fe : swapping the 0-th and the 9-th element in the list) your goal is to find the solution with the least swaps.
Thank you in advance
What you're searching for is a sorting algorithm.
https://brilliant.org/wiki/sorting-algorithms/
A good one is "QuickSort" combined with a simpler sorting algorithm like "BubbleSort"
Ted-Ed also have a good video on the topic: https://www.youtube.com/watch?v=WaNLJf8xzC4
Probably the best way to find the answer to this question is to open your favorite search engine and put the title to your question there. You will find many results, including:
Read through these and find the algorithms that only use the swapping of elements to do the sorting (since that is your requirement). You can also read about the performance of the algorithms as well (since that was another part of the requirement).
Note that some will perform faster than others depending on how large and how sorted the array is.
Another way to figure this out is to ask yourself, "What do the professionals do?". Which will likely lead you to reading the documentation for the Array.Sort Method, which is the built-in mechanism that most of us use if we need to quickly sort an array. Here you will find the following information:
Remarks
This method uses the introspective sort (introsort) algorithm as follows:
- If the partition size is fewer than 16 elements, it uses an insertion sort algorithm.
- If the number of partitions exceeds 2 * LogN, where N is the range of the input array, it uses a Heapsort algorithm.
- Otherwise, it uses a Quicksort algorithm.
So now we see that, for small partitions (like your example with 15 elements), the pros use insertion sort.
Assuming the values are 0 to n-1 for an array of size n, here is a an algorithm with O(n) time complexity, and it should be the optimal algorithm for minimizing swaps. Every swap will place at least one value (sometimes both) in it's proper location.
// the values of A[] range from 0 to n-1
void sort(int A[], int n)
{
for(int i = 0; i < n; i++)
while(A[i] != i)
swap(A[i], A[A[i]]);
}
For a more generic solution and assuming that only the swaps used to sort the original array are counted, generate an array of indices to the array to be sorted, sort the array of indices according to the array to be sorted (using any sort algorithm), then use the above algorithm to sort the original array and the array of indices at the same time. Using C++ to describe this, and using a lambda compare for this example:
void sort(int A[], int n)
{
// generate indices I[]
int *I = new int[n];
for(int i = 0; i < n; i++)
I[i] = i;
// sort I according to A
std::sort(I, I+n,
[&A](int i, int j)
{return A[i] < A[j];});
// sort A and I according to I using swaps
for(int i = 0; i < n; i++){
while(I[i] != i){
std::swap(I[i], I[I[i]]);
std::swap(A[i], A[A[i]]); // only this swap is counted
}
}
delete[] I;
}
For languages without the equivalent of a lambda commpare, a custom sort function can be used. Sorting is accomplished undoing the "cycles" in the array with O(n) time complexity. Every permutation of an array can be considered as a series of cycles. Value is really the order for the element, but in this case the ordering and value are the same:
index 0 1 2 3 4 5 6 7
value 6 3 1 2 4 0 7 5
The cycles are the "paths" to follow a chain of values, start with index 0, which has a value of 6, then go to index 6 which has a value of 7 and repeat the process until the cycle completes back at index 0. Repeat for the rest of the array. For this example, the cycles are:
0->6 6->7 7->5 5->0
1->3 3->2 2->1
4->4
Following the algorithm shown above the swaps are:
swap(a[0],a[6]) // puts 6 into place
swap(a[0],a[7]) // puts 7 into place
swap(a[0],a[5]) // puts 0 and 5 into place
swap(a[1],a[3]) // puts 3 into place
swap(a[1],a[2]) // puts 1 and 2 into place
// done
Link to the more practical example of sorting multiple arrays according to one of them. In this example, the cycles are done using a series of moves instead of swaps:
Sorting two arrays based on one with standard library (copy steps avoided)
