I received this question in a test, and I would like to know which paths to take.
I have an array of n distinct integers, A = [a0, a1, ..., an-1]. I can exchange any two array elements any number of times. How to calculate the smallest number of permutations needed to sort elements incrementally?
There are several ordering algorithms , but the main one among them is quick sort .
It consists of defining one of the list elements as a pivot element. In the example below, element 3 is considered as pivot, being represented by the black risk. The purpose is to organize all the elements that are inferior to the pivot to its left and all that are superior to its right. Thus, at the end, the pivot element will already be in its final position. Then, the same logic is executed recursively for the elements on the left and for the elements on the right, defining new pivot elements.
The logic executed is as follows:
To the right of the pivot, from the end to the beginning, the first element that is less than the same element is swapped, exchanging its positions. In this case, the first element less than 3 is 1.
To the left of the pivot, from the beginning to the end, the first element that is superior to the pivot is exchanged for its positions. In this case, the first element greater than 3 is 5.
The check of step 1 is repeated, finding the value 2, swapping the positions again.
The check of step 2 is repeated, finding the value 4, swapping the positions again.
The pivot element will be in its final position, so the algorithm for the vectors [1, 2] and [4, 5] is repeated separately, until the vector is completely ordered.
li> 
def quick_sort(vector):
# Se o vetor tiver comprimento 1, terminou a ordenação:
if len(vector) <= 1:
return vector
else:
return quick_sort([x for x in vector[1:] if x < vector[0]]) + \ # Ordena o vetor a esquerda
[vector[0]] + \ # Elemento pivô na posição final
quick_sort([x for x in vector[1:] if x>=vector[0]]) # Ordena o vetor a direita
See working at Repl.it
As the question originated from a test / proof, I believe that prior knowledge about sorting algorithms was expected, so to respond, I can take as a reference that Quick Sort is already the most efficient algorithm and the one that requires the least permutations during the ordering, it is enough that I calculate the number of permutations that such an algorithm will make to determine the minimum possible.
Considering a generic vector, the worst case happens when the pivot is the largest or smallest element and the vector is previously ordered inversely. That is, the worst case occurs when the sub-vectors are unbalanced: one with size n-1 and another 0, being n the size of the vector. Therefore, the number of comparisons and permutations made on each sub-vector will be n-1 for the left vector and 0 on the right. In the second iteration, the vectors will have sizes n-2 and 1, so there will be n-2 comparisons to the total. This continues until the array is sorted, so the total comparisons / permutations will be equal to:
Thebestcaseoccurswhenthepivotelementdividesthevectorintoequalsizes,therebeingn/2comparisonsineachsub-vector,sothetotalisequalto:
Sources:
Anderson has previously referred to a very powerful algorithm for organizing an array is QuickSort . The algorithm consists of fixing a position of the array and comparing the value relative to that position with the others and when we arrive at the last position n-1 , we do not need to make any comparison anymore.
Important: The array starts from position 0 and ends at position n-1, ie if we declare an array of size 5, we will not go through position 5 of the array because it does not exist, let's go to position 4 ( n-1 )
I will try to write the algorithm in Portuguese, but below is the algorithm in Java:
Inteiro [5] vetor := {16, 7, -9, 4, 13};
Inteiro auxiliar :=0;
Inteiro i := 0;
Inteiro b :=0;
Para (i:=0 até vetor.tamanho-1) faça{
---- Para (b:= i+1 até vetor.tamanho -2) faça {
-------- Se ( vetor [ i ] > vetor [ i+1] ) {
-------- auxiliar := vetor [ i ];
-------- vetor [ i ] := vetor [ i+1 ];
-------- vetor [ i+1] := auxiliar;
-------- }
----}
}
Example in Java:
I hope I have helped ...