Algoritmo QuickSort

Neste tutorial, você aprenderá como funciona o quicksort. Além disso, você encontrará exemplos funcionais de classificação rápida em C, C ++ Python e Java.

Quicksort é um algoritmo baseado na abordagem dividir e conquistar em que o array é dividido em submatrizes e esses subarrays são chamados recursivamente para classificar os elementos.

Como funciona o QuickSort?

Um elemento pivô é escolhido na matriz. Você pode escolher qualquer elemento da matriz como o elemento pivô.
Aqui, tomamos o mais à direita (ou seja, o último elemento) do array como o elemento pivô. Selecione um elemento pivô
Os elementos menores que o elemento pivô são colocados à esquerda e os elementos maiores que o elemento pivô são colocados à direita. Coloque todos os elementos menores à esquerda e os maiores à direita do elemento pivô.
A disposição acima é obtida pelas etapas a seguir.
1. Um ponteiro é fixado no elemento pivô. O elemento pivô é comparado com os elementos que começam no primeiro índice. Se o elemento maior do que o elemento pivô for alcançado, um segundo ponteiro é definido para esse elemento.
2. Agora, o elemento pivô é comparado com os outros elementos (um terceiro ponteiro). Se um elemento menor do que o elemento pivô for atingido, o elemento menor será trocado pelo elemento maior encontrado anteriormente. Comparação do elemento pivô com outros elementos
3. O processo continua até que o penúltimo elemento seja alcançado.
  Finalmente, o elemento pivô é trocado pelo segundo ponteiro. Troca o elemento pivô com o segundo ponteiro
4. Agora, as subpartes esquerda e direita desse elemento pivô são usadas para processamento posterior nas etapas abaixo.
Os elementos do pivô são novamente escolhidos para as subpartes esquerda e direita separadamente. Dentro dessas subpartes, os elementos do pivô são colocados em sua posição correta. Em seguida, a etapa 2 é repetida. Selecione o elemento pivô de em cada metade e coloque no lugar correto usando recursão
As subpartes são novamente divididas em subpartes menores até que cada subparte seja formada por um único elemento.
Neste ponto, a matriz já está classificada.

Quicksort usa recursão para classificar as sub-partes.

Com base na abordagem Dividir para conquistar, o algoritmo de classificação rápida pode ser explicado como:

Divide
A matriz é dividida em subpartes, tendo o pivô como ponto de partição. Os elementos menores que o pivô são colocados à esquerda do pivô e os elementos maiores que o pivô são colocados à direita.
Conquistar
As subpartes esquerda e direita são novamente particionadas usando o, selecionando elementos de pivô para elas. Isso pode ser alcançado passando recursivamente as subpartes para o algoritmo.
Combinar
Esta etapa não desempenha um papel significativo no quicksort. O array já está classificado no final da etapa de conquista.

Você pode entender o funcionamento do quicksort com a ajuda das ilustrações abaixo.

Classificando os elementos à esquerda do pivô usando recursão

Classificando os elementos à direita do pivô usando recursão

Algoritmo de classificação rápida

 quickSort (matriz, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- partição (matriz, leftmostIndex, rightmostIndex) quickSort (matriz, leftmostIndex, pivotIndex) quickSort (matriz, pivotIndex <- partição (matriz, leftmostIndex, rightmostIndex) quickSort (matriz, leftmostIndex, pivotIndex) quickSort (matriz, pivotIndex + 1, partição mais à direita) ) definir rightmostIndex como pivotIndex storeIndex <- leftmostIndex - 1 para i <- leftmostIndex + 1 para rightmostIndex if element (i) <pivotElement trocar elemento (i) e elemento (storeIndex) storeIndex ++ trocar pivotElement e elemento (storeIndex + 1) retornar storeIndex + 1

Exemplos de Python, Java e C / C ++

Python Java C C +

 # Quick sort in Python # Function to partition the array on the basis of pivot element def partition(array, low, high): # Select the pivot element pivot = array(high) i = low - 1 # Put the elements smaller than pivot on the left and greater #than pivot on the right of pivot for j in range(low, high): if array(j) <= pivot: i = i + 1 (array(i), array(j)) = (array(j), array(i)) (array(i + 1), array(high)) = (array(high), array(i + 1)) return i + 1 def quickSort(array, low, high): if low < high: # Select pivot position and put all the elements smaller # than pivot on left and greater than pivot on right pi = partition(array, low, high) # Sort the elements on the left of pivot quickSort(array, low, pi - 1) # Sort the elements on the right of pivot quickSort(array, pi + 1, high) data = (8, 7, 2, 1, 0, 9, 6) size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data)

 // Quick sort in Java import java.util.Arrays; class QuickSort ( // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left and // greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; int temp = array(i); array(i) = array(j); array(j) = temp; ) ) int temp = array(i + 1); array(i + 1) = array(high); array(high) = temp; return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code public static void main(String args()) ( int() data = ( 8, 7, 2, 1, 0, 9, 6 ); int size = data.length; QuickSort qs = new QuickSort(); qs.quickSort(data, 0, size - 1); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Quick sort in C #include // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Function to print eklements of an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (8, 7, 2, 1, 0, 9, 6); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); printf("Sorted array in ascending order: "); printArray(data, n); )

 // Quick sort in C++ #include using namespace std; // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to print eklements of an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) printArray(array, 7); cout << "… "; swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code int main() ( int data() = (8, 7, 6, 1, 0, 9, 2); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); cout << "Sorted array in ascending order: "; printArray(data, n); )

Complexidade Quicksort

Complexidades de tempo

Pior Caso Complexidade (Big-O) : ocorre quando o elemento pivô escolhido é o maior ou o menor elemento. Essa condição leva ao caso em que o elemento pivô encontra-se em uma extremidade extrema da matriz classificada. Uma submatriz está sempre vazia e outra submatriz contém elementos. Portanto, quicksort é chamado apenas nesta submatriz. No entanto, o algoritmo de classificação rápida tem melhor desempenho para pivôs dispersos.O(n²)
n - 1
Best Case Complexity (Big-omega) : O(n*log n)
ocorre quando o elemento pivô é sempre o elemento do meio ou próximo ao elemento do meio.
Complexidade média do caso (Big-theta) : O(n*log n)
ocorre quando as condições acima não ocorrem.