Skip to content

Using randomize partition to avoid the basically ordered sequences #786

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 2 commits into from
Jul 6, 2019
Merged

Using randomize partition to avoid the basically ordered sequences #786

Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
7cd8552
Using randomize partition to avoid the basically ordered sequences
CN-GuoZiyang Jul 6, 2019
0821df8
Update QuickSort.java
CN-GuoZiyang Jul 6, 2019
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
19 changes: 17 additions & 2 deletions Sorts/QuickSort.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -33,12 +33,27 @@ public <T extends Comparable<T>> T[] sort(T[] array) {

private static <T extends Comparable<T>> void doSort(T[] array, int left, int right) {
if (left < right) {
int pivot = partition(array, left, right);
int pivot = randomPartition(array, left, right);
doSort(array, left, pivot - 1);
doSort(array, pivot, right);
}
}

/**
* Ramdomize the array to avoid the basically ordered sequences
*
* @param array The array to be sorted
* @param left The first index of an array
* @param right The last index of an array
* @return the partition index of the array
*/

private static <T extends Comparable<T>> int randomPartition(T[] array, int left, int right) {
int randomIndex = left + (int)(Math.random()*(right - left + 1));
swap(array, randomIndex, right);
return partition(array, left, right);
}

/**
* This method finds the partition index for an array
*
Expand Down Expand Up @@ -75,7 +90,7 @@ public static void main(String[] args) {
Integer[] array = {3, 4, 1, 32, 0, 1, 5, 12, 2, 5, 7, 8, 9, 2, 44, 111, 5};

QuickSort quickSort = new QuickSort();
// quickSort.sort(array);
quickSort.sort(array);

//Output => 0 1 1 2 2 3 4 5 5 5 7 8 9 12 32 44 111
print(array);
Expand Down