I made a topic earlier about quicksort, now i’m onto mergesort and it’s way harder because of the nature of it’s temporary arrays.
What we were talking about on the other topic ended up becoming this code.
It fails if you try to use B command when it’s already at the start, is screws up the order, but it’s serviceable and o gotta move on to mergesort.
I’m trying some ideas now, i’ll post them soon.
import java.lang.*;
int pos = 0;
int dir = 0;
int largura = 20;
//int[] arr = {5,8,15,20,17,14,55,100,11,5,6,67,8,4,12,13,1,47,5,27,38,5,7,50,47,84,9,33,41};
//int[] arr = {60,20,45,100,5,80};
int[] arr;
int[] base;
ArrayList<TrocaPos> solution = new ArrayList<TrocaPos> ();
void setup() {
size(1000, 800);
textSize(16);
textAlign(CENTER, CENTER);
arr = numeros(width /largura, 0, height - 60);
base = numeros(width /largura, 0, height - 60);
arrayCopy(arr, base);
//quickSortIterative(arr, 0, arr.length - 1);
QuickSort(arr, 0, arr.length - 1);
arrayCopy(base, arr);
}
class TrocaPos {
int t0, t1;
TrocaPos(int t0, int t1) {
this.t0 = t0;
this.t1 = t1;
}
}
int[] numeros(int n, int low, int high) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = (int)(low + random(1)*(high-low));
return a;
}
void draw() {
background(250);
fill(0);
text("F = Forward P = Pause R = Reverse V = volta um passo B = vai um passo", 0, height-60, width, 45);
text(pos, 15,15);
stroke(50, 50, 100);
fill(200, 200, 250);
for (int i = 0; i < arr.length; i++){
rect(i * largura, height-50-arr[i], largura, arr[i]);
}
switch (dir) {
case 1: Forward(); break;
case -1: reverso(); break;
case 2: if(pos>0){pos--;ForwardStep();}break;
case -2: if(pos < solution.size()){reversoS();pos++;}break;
}
}
void keyTyped() {
switch(key) {
case 'f': dir = 1; break;
case 'r': dir = -1; break;
case 'p': dir = 0; break;
case 'v': dir = 2; break;
case 'b': dir = -2; break;
}
}
int corta(int p[], int low, int high){
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
solution.add(new TrocaPos(j, i));
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
solution.add(new TrocaPos( i+1, high));
return i + 1;
}
void QuickSort(int arr[], int low, int high)
{
if (low < high) {
int pi = corta(arr, low, high);
QuickSort(arr, low, pi - 1);
QuickSort(arr, pi + 1, high);
}
}
void Forward() {
if (pos < solution.size()) {
TrocaPos sw = solution.get(pos);
int temp = arr[sw.t0];
arr[sw.t0] = arr[sw.t1];
arr[sw.t1] = temp;
pos++;
}
}
void reverso() {
if (pos > 0) {
pos--;
TrocaPos sw =solution.get(pos);
int temp = arr[sw.t0];
arr[sw.t0] = arr[sw.t1];
arr[sw.t1] = temp;
}
}
void ForwardStep() {
if (pos < solution.size()) {
TrocaPos sw = solution.get(pos);
int temp = arr[sw.t0];
arr[sw.t0] = arr[sw.t1];
arr[sw.t1] = temp;
}
dir = 0;
}
void reversoS() {
if (pos > 0) {
TrocaPos sw =solution.get(pos);
int temp = arr[sw.t0];
arr[sw.t0] = arr[sw.t1];
arr[sw.t1] = temp;
}
dir = 0;
}
/*
void quickSortIterative(int arr[], int l, int h)
{
int[] stack = new int[h - l + 1];
int top = -1;
// push initial values of l and h to stack
stack[++top] = l;
stack[++top] = h;
// Keep popping from stack while is not empty
while (top >= 0) {
// Pop h and l
h = stack[top--];
l = stack[top--];
// Set pivot element at its correct larguraition
// in sorted array
int p = corta(arr, l, h);
// If there are elements on left side of pivot,
// then push left side to stack
if (p - 1 > l) {
stack[++top] = l;
stack[++top] = p - 1;
}
// If there are elements on right side of pivot,
// then push right side to stack
if (p + 1 < h) {
stack[++top] = p + 1;
stack[++top] = h;
}
}
}
*/