I have been trying to implement a normal non hybrid quicksort algorithm an d it works for arrays up to about 100 fields in size. I get the exception "stack-overflow" with most of you are probably familiar with. Here is my source code:
import java.util.Arrays;
public class Quicksort {
public int[] zahlenliste;
public Quicksort(int[] zahlenliste) {
sort(zahlenliste);
}
public void sort(int[] zahlenliste) {
if (zahlenliste == null || zahlenliste.length == 0) {
return;
}
this.zahlenliste = zahlenliste;
quickSort(0, zahlenliste.length - 1);
}
public void quickSort(int begin, int end) {
if (begin >= end) {
return;
}
int lower = begin;
int higher = end;
// Choose a pivot
// int pivot = zahlenliste[lower + (higher - lower) / 2];
int pivot = zahlenliste[lower + (higher - lower) / 2];
while (lower <= higher) {
while (zahlenliste[lower] < pivot) {
lower++;
}
while (zahlenliste[higher] > pivot) {
higher--;
}
if (lower < higher) {
swap(zahlenliste, lower, higher);
}
lower++;
higher--;
}
if (begin < higher) {
quickSort(begin, lower);
}
if (lower < end) {
quickSort(lower, end);
}
}
public static int[] swap(int[] zahlenliste, int begin, int end) {
int temp = zahlenliste[begin];
zahlenliste[begin] = zahlenliste[end];
zahlenliste[end] = temp;
return zahlenliste;
}
}
I know there are quicksort implementations where you choose a more fitting pivot by the median-three method or use insertion sort with lists smaller than 10. However I want to implement all of those an compare them on huge arrays. So it would be nice if anyone had a solution to get the simple quicksort to sort bigger arrays.
Fixes noted in comments
public void quickSort(int begin, int end) {
if (begin >= end) {
return;
}
int lower = begin;
int higher = end;
int pivot = zahlenliste[lower + (higher - lower) / 2];
while (lower <= higher) {
while (zahlenliste[lower] < pivot) {
lower++;
}
while (zahlenliste[higher] > pivot) {
higher--;
}
if (lower <= higher) { // fix
swap(zahlenliste, lower, higher);
lower++; // fix
higher--; // fix
}
}
if (begin < lower-1) { // fix
quickSort(begin, lower-1); // fix
}
if (lower < end) {
quickSort(lower, end);
}
}
// fix (void)
public void swap(int[] zahlenliste, int begin, int end) {
int temp = zahlenliste[begin];
zahlenliste[begin] = zahlenliste[end];
zahlenliste[end] = temp;
}
Displaying Dynamic placeholder content on Textbox in ReactJS
Extracting Parameters from Redirect URI - QuickBooks API / Python
How to check if a function is running in worker thread in node?
How to take column from two table in whereExists clause in laravel 5.5
Cannot publish new release to Google Play because of Sensitive app permissions
I have a problem with my docker-compose file, it is causing issues with connectionThe most weird think is that I am able to connect to the database from my localhost, but not in the container
I have all thejar files from an external library (Apache Batik) in my classpath
I want to inherit the remotewebdriver from my BaseTest class so all my tests in another class can inherit the webdriverCurrently I only have it implemented in my 2nd class, I can do this quite easily if I am creating the tests locally, but we're utilizing...