Skip to content

Instantly share code, notes, and snippets.

@devgioele
Created December 14, 2020 11:39
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save devgioele/4f9d822098e400b9276f86014f21eb2c to your computer and use it in GitHub Desktop.
Hoare and Lomuto Algorithms
int partitionLomuto(int[] A) {
int l = 0, r = A.length - 1;
int p = A[r];
int ll = l - 1;
for (int bu = l; bu < r; bu++) {
if (A[bu] <= p) {
ll++;
swap(A, ll, bu);
}
}
swap(A, ll + 1, r);
return ll;
}
int partitionHoare(int[] A) {
int p = A[A.length - 1];
int l = -1, r = A.length;
while (true) {
do l++; while (A[l] < p);
do r--; while (A[r] > p);
if (l >= r)
break;
swap(A, l, r);
}
return l;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment