Created
June 4, 2018 20:35
-
-
Save lucasheriques/66d135790a7f9b1546eb3f87ab4e66ab to your computer and use it in GitHub Desktop.
QuickSort implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class QuickSort { | |
/* | |
Pega o último elemento como pivô, e coloca ele seu em lugar correto, | |
com todos os elementos menores à esquerda, e os maiores à direita. | |
*/ | |
private int partition(int arr[], int low, int high) { | |
int pivot = arr[high]; | |
int i = (low - 1); | |
for (int j = low; j < high; j++) { | |
if (arr[j] <= pivot) { | |
i++; | |
// swap arr[i] and arr[j] | |
int temp = arr[i]; | |
arr[i] = arr[j]; | |
arr[j] = temp; | |
} | |
} | |
int temp = arr[i + 1]; | |
arr[i + 1] = arr[high]; | |
arr[high] = temp; | |
return i + 1; | |
} | |
/* | |
A principal função que implementa o QuickSort, | |
arr[] --> array que será ordenada, | |
low --> índice de começo, | |
high --> índice final | |
*/ | |
private void sort(int arr[], int low, int high) { | |
if (low < high) { | |
/* pi is partitioning index, arr[pi] is | |
now at right place */ | |
int pi = partition(arr, low, high); | |
// Recursively sort elements before | |
// partition and after partition | |
sort(arr, low, pi - 1); | |
sort(arr, pi + 1, high); | |
} | |
} | |
/* Utilitário para imprimir Arrays */ | |
private static void printArray(int arr[]) { | |
int n = arr.length; | |
for (int i = 0; i < n; ++i) | |
System.out.print(arr[i] + " "); | |
System.out.println(); | |
} | |
public static void main(String args[]) { | |
int arr[] = {10, 7, 8, 9, 1, 5}; | |
int n = arr.length; | |
QuickSort ob = new QuickSort(); | |
ob.sort(arr, 0, n - 1); | |
System.out.println("sorted array"); | |
printArray(arr); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment