Подскажите пожалуйста, что не так в написанном мной методе быстрой сортировки?
Сразу признаюсь, код не гуглила (оно и видно) - написала, узнав основной принцип быстрой сортировки. Гуглить не хочу, хочу разобраться в причине того, почему не работает то, что есть.
Как мне кажется, ошибка скрывается где-то на этапе, когда я объединяю массив чисел меньших, чем базовое (less), с базовым числом (basecase), и с массивом чисел больших, чем базовое (greater).
Приведу пример запуска:
Ввод:
6
5
8
9
7
Так как размер массива превышает 1, запускается сортировка:
Вывод:
Это массив чисел меньших, чем базовое
[5]
Это массив чисел больших, чем базовое
[8, 9, 7]
Метод определил числа меньшие, чем 6 (принятое как базовое), и большие, чем базовое, и записал их в отдельные массивы - less и greater.
Далее по отношению к массивам less и greater применяется тот же самый метод quicksort.
Так как массив less состоит всего из одного элемента, метод просто сохраняет его без изменений. Так как в массиве greater содержится больше одного элемента, для него применяется сортировка.
Вывод:
Это массив чисел меньших, чем базовое
[7]
Это массив чисел больших, чем базовое
[9]
Это объединенный массив
[7, 8, 9]
Базовое число - 8. Метод нашел массив чисел меньших, чем базовое (7), и больших, чем базовое (9). Объединил их в один новый массив, поставив между ними само базовое число - [7, 8, 9].
Внимание на последнюю строку - сортировка для данного массива отработала, расставив числа в нужном порядке. Как мне кажется, результат данной сортировки, согласно коду, должен был записаться в новый массив result и заменить им массив greater.
Так как обработка закончилась, результат обработки изначальных less и greater объединяется в общий массив.
Вывод:
Это объединенный массив
[5, 6, 8, 9, 7]
И вот тут получается, что при объединении массива less, базового числа, и массива greater результат сортировки данных массивов не был использован. Метод просто вернул массивы less и greater так, как они были определены на второй и четвертой строке вывода. При этом массивы less и greater как будто не были отсортированы вовсе
Еще раз прошу помощи( Не понимаю, почему метод quicksort не использует результат сортировки массивов less и greater
package com.javarush.task.task06.task0622;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
/*
Числа по возрастанию
Задача: Написать программу, которая вводит с клавиатуры 5 чисел и выводит их в возрастающем порядке.
Пример ввода:
3
2
15
6
17
Пример вывода:
2
3
6
15
17
Требования:
1. Программа должна считывать 5 чисел с клавиатуры.
2. Программа должна выводить 5 чисел, каждое с новой строки.
3. Выведенные числа должны быть отсортированы по возрастанию.
*/
public class Solution {
public static void main(String[] args) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
ArrayList<Integer> Array = new ArrayList<Integer>();
for (int i = 0; i < 5; i++) {
Array.add(Integer.parseInt(reader.readLine()));
}
ArrayList<Integer> newArray = quicksort(Array);
for (int j = 0; j < newArray.size(); j++) {
System.out.println(newArray.get(j));
}
}
public static ArrayList<Integer> quicksort(ArrayList<Integer>list) {
if (list.size() < 2)
{return list;}
else
{
int basecase = list.get(0);
ArrayList<Integer> less = new ArrayList<Integer>();
for (int a = 1; a < list.size(); a++) {
if (list.get(a) <= basecase) {
less.add(list.get(a));
}
}
System.out.println("Это массив чисел меньших, чем базовое");
System.out.println(less.toString());
ArrayList<Integer> greater = new ArrayList<Integer>();
for (int b = 1; b < list.size(); b++) {
if (list.get(b) > basecase) {
greater.add(list.get(b));
}
}
System.out.println("Это массив чисел больших, чем базовое");
System.out.println(greater.toString());
quicksort(less);
quicksort(greater);
ArrayList<Integer> result = new ArrayList<>();
for (int d = 0; d < less.size(); d++)
{ result.add(less.get(d));}
result.add(list.get(0));
for (int e = 0; e < greater.size(); e++)
{result.add(greater.get(e));}
System.out.println("Это объединенный массив");
System.out.println(result.toString());
return result;
}
}
}