Quicksort does not work with array bigger than 100

103
June 05, 2019, at 1:10 PM

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.

Answer 1

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;
    }
READ ALSO
Unable to open JDBC connection for DDL execution docker

Unable to open JDBC connection for DDL execution docker

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

257
import cannot be resolved, even though .jar files are in classpath

import cannot be resolved, even though .jar files are in classpath

I have all thejar files from an external library (Apache Batik) in my classpath

65
Inheriting a remote webdriver syntax

Inheriting a remote webdriver syntax

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...

49