D
D
Den4_x2019-08-06 13:56:29
Java
Den4_x, 2019-08-06 13:56:29

What is wrong here (quicksort algorithm)?

package practice;

import java.util.Arrays;
import java.util.Random;

public class Practice {

    public static void main(String[] args) {
        int[] array = {1, 0, 5, 100, 7, 32, 8, 40, 9, 1, 10};
        System.out.println(Arrays.toString(array));

        QuickSort.quickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }
}

class QuickSort {

    public static void quickSort(int[] array, int low, int high) {
        Random rand = new Random();

        int L = low;
        int R = high;
        int diff = high - low;

        //Взяли произвольнй эл-нт из рандомного index-а данного массива
        int separator = array[low + rand.nextInt(diff + 1)];//[low;high] на ОТРЕЗКЕ!!!

        //Параметры введены корректно?
        if (low >= high) {
            return;
        }

        while (L <= R) {
            while (array[L] < separator) {
                ++L;
            }
            while (array[R] > separator) {
                --R;
            }

            if (L <= R) {
                swap(array, L, R);
                ++L;
                --R;
            }

        }

        quickSort(array, low, R);
        quickSort(array, L, high);
    }

    public static void swap(int[] array, int x, int y) {
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }
}

Only 1 out of 10 works, only the variations work, and everything else writes an error, why?

Answer the question

In order to leave comments, you need to log in

1 answer(s)
V
Viktor Malkov, 2019-08-06
@Den4_x

check low <= high must be at the beginning

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question