Quick Sort

let map = [];

let count = 0; // 交換回数

let sorted = false;

​

let width = 420;

let height = 400;

let list_length = 30;

​

// p5js

function setup() {

  createCanvas(width, height);

  // フーレームレートを1/1secにする

  frameRate(3);

  background(color(212, 236, 234));

  // 描画を繰り返さない。

  ini();

}

​

// 初期化

function ini() {

  let array = [];

  map = [];

  count = 0;

  sorted = false;

​

  length = parseInt(list_length);

​

​

  // 配列の初期化

  for (let i = 0; i < list_length; i++) {

    array.push(i + 1);

  }

  array = listShuffle(array);

​

  let pivot = Math.floor((array.length - 1) / 2);

  let pivot_height = array[pivot];

  record(null, null, 0, length - 1, pivot_height, array);

​

  // 先に交換順序を計算しておく。

  sorted = quickSort(0, array.length - 1, array);

  // ソート完了

  record(null, null, -100, 0, -10000, array);

}

​

​

let swither = 0;

function draw() {

  if (sorted && count < map.length) {

    // canvasを更新

    background(color(212, 236, 234));

    let m = map[count];

    drawRnage(m.range);

    drawBar(m.array, m.pivot_height, m.swap);

    drawHeight(m.range, m.pivot_height);

    count++;

  }

}

​

// 再描画

function restart() {

  ini();

}

​

// 配列をシャッフル

function listShuffle(array) {

  for (let i = array.length - 1; i >= 0; i--) {

    let rand = Math.floor(Math.random() * (i + 1));

    // 配列の数値を入れ替える

    [array[i], array[rand]] = [array[rand], array[i]]

  }

  return array;

}

​

​

​

// 比較する高さを描画

function drawHeight(range, height) {

  const grid_pixel = 10;

  const margin_left = 4;

  const y = 350 - (grid_pixel * height) + 5;

  let left = (grid_pixel + margin_left) * range.srart + 2;

  let width = (grid_pixel + margin_left) * (range.end - range.srart + 1);

​

  stroke(126);

  line(left, y, left + width, y);

}

​

// 走査範囲を表示

function drawRnage(range) {

  const grid_pixel = 10;

  const margin_left = 4;

​

  // gray

  let left = (grid_pixel + margin_left) * range.srart + 2;

  const under = 20;

  let width = (grid_pixel + margin_left) * (range.end - range.srart + 1);

  let height = 360;

​

  stroke(222, 246, 244);

  fill(color(222, 246, 244));

  rect(left, under, width, height);

}

​

// バーを表示

function drawBar(array, pivot_height, swap) {

  const under = 350;

  const grid_pixel = 10;

  const margin_left = 4;

​

  for (let i = 0; i < array.length; i++) {

    // gray

    let left = (grid_pixel + margin_left) * i + 2;

    let height = grid_pixel * array[i];

​

    // 枠線の色

    stroke(0, 0, 0);

    if (array[i] === pivot_height) {

      // 基準値の色　バーの色

      fill(color(191, 164, 65));

    } else if (i === swap.left) {

      // 左交換の色　バーの色

      fill(color(65, 156, 192));

    } else if (i === swap.right) {

      // 右交換の色　バーの色

      fill(color(191, 65, 155));

    } else {

      // バーの色

      fill(color(237, 235, 213));

    }

    rect(left, under - height, grid_pixel, height);

    fill(color(50, 50, 50));

    rect(left, under - height, grid_pixel, grid_pixel);

  }

}

​

​

​

// クイックソート

function quickSort(start, end, array) {

  if (end - start < 2) {

    // 1. 走査する配列長が0か１の場合戻る。

    return;

  }

​

  // console.log(start, end);

  // 2. 走査する範囲の中央の要素をピボットとして選ぶ。

  let pivot = Math.floor((start + end) / 2);

  let pivot_height = array[pivot];

  // 走査範囲の左と右端を渡す

  let left = start;

  let right = end;

​

​

  while (left < right) {

    // 3. ピボットと比べ、大きい要素は左へ小さい要素は右へ交換する。

    while (array[left] < pivot_height) left++; // 左側の基準値より大きい位置まで移動

    while (array[right] > pivot_height) right--; // 右側の基準値より小さい位置まで移動

​

    if (left < right) {

      // 交換を記録する

      record(left, right, start, end, pivot_height, array);

      // leftがrightを超えていない場合、leftとrightを交換

      swap(left, right, array);

    } else {

      //leftがrightを超えたら走査範囲の比較を止める

      break;

    }

  }

​

  // 4. 左右２つに配列を分割してこの関数を再帰的に繰り返す。

  quickSort(start, left - 1, array);

  quickSort(right, end, array);

​

  return true;

}

​

​

// 配列の要素を交換する

function swap(left, right, array) {

  let tmp = array[left];

  array[left] = array[right];

  array[right] = tmp;

}

​

// 交換を記録する

function record(left, right, start, end, pivot_height, array) {

  map.push(

    {

      array: array.concat(), // コピーして渡す

      pivot_height: pivot_height, // 比較している高さ

      range: { // 走査範囲

        srart: start,

        end: end,

      },

      swap: {  // 交換記録

        left: left,

        right: right

      }

    });

}