Реализации алгоритмов/Сортировка/Быстрая: различия между версиями

Содержимое удалено Содержимое добавлено
Строка 405:
import java.util.Stack;
 
class ArrRange
{
// структура для хранения индексов границ массива
public int low, high;
public ArrRange(int from, int to){
{
this.low = from;
this.high = to;
}
}
 
public class QuickSorter
{
// Задаем размер массива
final static int size = 10;
// Объявляем массив
int[] a;
// Стек для хранения индексов начала и конца массива
Stack<ArrRange> stack;
 
QuickSorter () {
{
a = new int[size];
for (int i = 0; i < size; i++) a[i] = (int) {(Math.random() * 100);
a[i] = (int) (Math.random() * 100);
}
stack = new Stack<ArrRange>();
stack.push(new ArrRange(0, a.length - 1));
}
 
int step = -1; // текущий шаг
int drawStep = -1; // текущий шаг для вывода сообщения
int temp1 = -1; int, temp2 = -1; // текущие переставляемые элементы
int middle = -1; // середина массива
int opora; // опорный элемент
int i, j;
ArrRange range;
 
public void NextStep() {
{
switch (step) {
case -1:
}{
range = stack.pop();
case -1: range = stack.pop(); step = 0; break;
case 0:// находим опорный элемент
break;
case -10:
case 0:// находим опорный элемент
middle = (range.low + range.high) >> 1; opora = a[middle];
opora = a[middle];
i = range.low; j = range.high;
step = 1;
break;
case 1:// ишем слева элемент больше опорного
case 1:
while (a[i] < opora) {i++;
i++;
}
temp1 = a[i];
step = 2;
break;
case 2:// ишем справа элемент меньше опорного
case 2:
while (a[j] > opora) {j--;
j--;
}
temp2 = a[j];
step = 3;
break;
case 3:// меняем местами
ifcase (i <= j) {3:
if (i <= j){
int temp = a[i];
}{
a[i] = a[j];
int temp = a[i]; a[i] = a[j]; a[j] = temp;
i++;
i++j--;
j--;}
step = i <= j ? 1 : }4;
if (i <= j){
step = 1;
} else {
step = 4;
}
break;
case 4:// разделить массив на 2 части
case 4:
if(i < middle) {// правая часть больше
if(i < middle)
if (i < range.high) { // если в ней больше 1 элемента - нужно сортировать, отправляем в стек
}{
stack.push(new ArrRange(i, range.high));
} /*
if(i < middle) {// правая часть больше:
range.high = j; // следующая итерация разделения будет работать с левой частью
if (i < range.high) { // если в ней больше 1 элемента - нужно сортировать, отправляем в стек
range.high = j; // следующая итерация разделения будет работать с левой частью
} else {*/
if (i < range.high) stack.push (new ArrRange(i, range.high));
steprange.high = 1j;
}
else {// левая часть больше
if (j > range.low) {
stack.push(new ArrRange(range.low, j));
}
range.low = i; // следующая итерация разделения будет работать с правой частью
}
if(range.low < range.high)
step = 0;
else if (stack.size() > 0)
step = -1;
else
step = 5; {
step = 4;/*
else {// левая часть больше:
range.low = i; // следующая итерация разделения будет работать с правой частью
step = 0;*/
if (j > range.low) stack.push(new ArrRange(range.low, j));
range.low = stack.pop()i;
}
step = (range.low < range.high) ? 0 : (stack.size() > 0) ? -1 : 5;
break;
}
}
public void draw (Graphics g) {
{
int h = 30, w = 30;
int h = 30, w = 30, l = 50;
for (int i = 0; i < size; i++i) {
{
g.setColor(new Color(0, 0, 0));
g.clearRect(l + i * h, 100, w, h);
g.drawRect (l + i * h, 100, w, h);
g.drawString(a[i] + "", l + i * h + 7, 105 + h / 2);
}
Строка 517 ⟶ 519 :
g.drawString("opora: " + opora, l, 200);
String s = "";
switch (drawStep) {
{
case -1:
case -1: s = "начинаем сортировку"; break;
case 0: s = "находим опорный элемент"; break;
break;
case 1: s = "ишем слева элемент больше опорного"; break;
case 0:
case 2: s = "находимишем опорныйсправа элемент меньше опорного"; break;
case 3: s = "меняем местами"; break;
break;
case 4: s = "разделяем массив на 2 части"; break;
case 1:
case 5: s = "закончили сортировку"; break;
s = "ишем слева элемент больше опорного";
break;
case 2:
s = "ишем справа элемент меньше опорного";
break;
case 3:
s = "меняем местами";
break;
case 4:
s = "разделяем массив на 2 части";
break;
case 5:
s = "закончили сортировку";
break;
}
g.drawString("Действие: " + s, l, 50);