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

Содержимое удалено Содержимое добавлено
Нет описания правки
Строка 312:
if(i < high) qSort(A, i, high);
}
}
</source>
 
=== Java без рекурсии, с использованием стека ===
 
пошаговый алгоритм с возможностью вывода на экран текущего действия
 
<source>
import java.awt.Color;
import java.awt.Graphics;
import java.util.Arrays;
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);
}
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();
step = 0;
break;
case 0:// находим опорный элемент
middle = (range.low + range.high) >> 1;/*range.low + (range.high - range.low) / 2;*/
opora = a[middle];
i = range.low; j = range.high;
step = 1;
break;
case 1://ишем слева элемент больше опорного
while (a[i] < opora) {
i++;
}
temp1 = a[i];
step = 2;
break;
case 2://ишем справа элемент меньше опорного
while (a[j] > opora) {
j--;
}
temp2 = a[j];
step = 3;
break;
case 3://меняем местами
if (i <= j) {//меняем местами
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
if (i <= j){
step = 1;
} else {
step = 4;
}
break;
case 4://разделить массив на 2 части
if(i < middle) {// правая часть больше
if (i < range.high) { // если в ней больше 1 элемента - нужно сортировать, отправляем в стек
stack.push(new ArrRange(i, range.high));
}
range.high = j; // следующая итерация разделения будет работать с левой частью
}
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;
break;
}
}
public void draw(Graphics g) {
int h = 30, w = 30;
int 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);
}
 
g.setColor(new Color(0, 0, 0));
g.drawString("temp1: " + temp1, l, 160);
g.drawString("temp2: " + temp2, l, 180);
g.drawString("opora: " + opora, l, 200);
String s = "";
switch(drawStep) {
case -1:
s = "начинаем сортировку";
break;
case 0:
s = "находим опорный элемент";
break;
case 1:
s = "ишем слева элемент больше опорного";
break;
case 2:
s = "ишем справа элемент меньше опорного";
break;
case 3:
s = "меняем местами";
break;
case 4:
s = "разделяем массив на 2 части";
break;
case 5:
s = "закончили сортировку";
break;
}
g.drawString("Действие: " + s, l, 50);
drawStep = step;
}
}
</source>