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.- 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.
- 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 - 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 - 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(n2)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.
Complexidade do Espaço
A complexidade do espaço para quicksort é O(log n).
Aplicativos Quicksort
Quicksort é implementado quando
- a linguagem de programação é boa para recursão
- a complexidade do tempo importa
- a complexidade do espaço importa
