Реализации алгоритмов/Сортировка/Быстрая: различия между версиями
Содержимое удалено Содержимое добавлено
Строка 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)
}▼
stack = new Stack<ArrRange>();
stack.push(new ArrRange(0, a.length - 1));
}
int step = -1; // текущий шаг
int drawStep = -1; // текущий шаг для вывода сообщения
int temp1 = -1
int middle = -1; // середина массива
int opora; // опорный элемент
int i, j;
ArrRange range;
public void NextStep()
{
switch (step)
case -1:▼
range = stack.pop();▼
▲ case 0:// находим опорный элемент
middle = (range.low + range.high) >> 1; opora = a[middle];
i = range.low; j = range.high;
step = 1;
break;
case 1:
while (a[i] < opora) temp1 = a[i];
step = 2;
break;
case 2:
while (a[j] > opora) temp2 = a[j];
step = 3;
break;
int temp = a[i]; a[i] =
i++;
step = i <= j ? 1 :
▲ if (i <= j){
step = 1;▼
} else {▼
step = 4;▼
▲ }
break;
case 4:▼
if(i < middle) {// правая часть больше▼
if(i < middle)
if (i < range.high) { // если в ней больше 1 элемента - нужно сортировать, отправляем в стек▼
stack.push(new ArrRange(i, range.high));▼
range.high = j; // следующая итерация разделения будет работать с левой частью▼
}
else {// левая часть больше▼
stack.push(new ArrRange(range.low, j));▼
}▼
range.low = i; // следующая итерация разделения будет работать с правой частью▼
▲ }
step = 0;▼
else
step = (range.low < range.high) ? 0 : (stack.size() > 0) ? -1 : 5;
break;
}
}
public void draw (Graphics g)
{
int h = 30, w = 30, l = 50;
for (int i = 0; i < size; 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 0: s = "находим опорный элемент"; break;
▲ s = "ишем слева элемент больше опорного";
▲ s = "меняем местами";
▲ case 4:
▲ s = "разделяем массив на 2 части";
▲ s = "закончили сортировку";
}
g.drawString("Действие: " + s, l, 50);
|