Calculate minimum number of permutations to sort

Question

I received this question in a test, and I would like to know which ways to go.

I have an array of distinct n integers, A = [A0, a1, ..., an-1]. I can swap any two elements of the array any number of times. How to calculate the smallest number of permutations needed to order elements in an increasing way?

Answer 1

There are several sorting algorithms, but the main among them is the Quick Sort.

It consists of defining one of the elements of the list as a pivot element. In the example below, it is considered the element 3 as pivot, being represented by the black risk. The purpose is to organize all the elements that are inferior to the pivot to your left and all those that are superior to your right. Thus, at the end, the pivot element will already be in its final position. After, the same logic is executed recursively for the elements on the left and for the elements on the right, defining new pivot elements.

The executed logic is as follows:

1. From the end to the beginning, the first element is checked to the right of the pivot by exchanging its positions. In this case, the first item below 3 is 1.

2. From the beginning to the end, the first element that is superior to it is verified at the left of the pivot, exchanging its positions. In this case, the first item exceeding 3 is 5.

3. Repeat the check of step 1, finding the value 2, swapping the positions again.

4. Repeat the check of step 2, finding the value 4, swapping the positions again.

5. The pivot element will be in its final position, then repeat the algorithm for the vectors [1, 2] and [4, 5] separately, until the vector is completely ordered.

Quick Sort in Python

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 on Repl.it}

---

Minimum of permutations

Given that the question originated from a test/proof, I believe that the prior knowledge about the sorting algorithms was expected, thus, to answer, I can take as reference that the Quick Sort is already the most efficient algorithm and the one that requires less permutations during sorting, so I just calculate the number of permutations that such an algorithm will do to determine the minimum possible.

Considering a generic vector, the worst case occurs 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 in each sub-vector will be n-1 for the left vector and 0 from 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. So it continues until the vector is ordered, so the total of comparisons/permutations will be equal to:

The best case occurs when the pivot element divides the vector into equal sizes, with n/2 comparisons on each sub-vector, so the total is equal to:

Sources:

• Quicksort - Wikipedia
• Quicksort - UFMG

Answer 2

According to the Anderson referenced previously a very effective algorithm for organizing an array is the Quicksort. The algorithm consists of Fix an array position and compare the value for that position with the others and when we arrived at the last position n-1, no longer need to make any comparison.

Important: the array starts from position 0 and ends at position n-1, that is, if we declare an array of size 5, we will not go through position 5 of the array as it does not exist, we 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’ve helped...