実装したソートたち

sort.js

// == ユーティリティ ==

/*
 * 配列の要素を入れ替える
 *
 * @param {Array} data 要素を入れ替える配列
 * @param {Number} i,j 入れ替える要素の添字
 */
function swap(data, i, j) {
  var
  x = data[i];
  data[i] = data[j];
  data[j] = x;
}

// == ソートの実装 ==

/**
 * バブルソート
 *
 * @param {Array} data ソートされる配列（破壊的に変更される）
 * @param {Function} cmp 比較関数（a > bのときは正の数、a == bのときは 0 、a < bのときは負の数）
 * @return {Array} ソートされた配列
 */
function bubbleSort(data, cmp) {
  var
  len = data.length, end, i, m;

  for (end = len - 1; end > 0; end -= m) {
    m = 1;
    for (i = 0; i < end; i++) {
      if (cmp(data[i], data[i + 1]) > 0) {
        swap(data, i, i + 1);
        m = 1;
      } else {
        m += 1;
      }
    }
  }

  return data;
}

/**
 * シェーカーソート
 *
 * @param {Array} data ソートされる配列（破壊的に変更される）
 * @param {Function} cmp 比較関数（a > bのときは正の数、a == bのときは 0 、a < bのときは負の数）
 * @return {Array} ソートされた配列
 */
function shakerSort(data, cmp) {
  var
  len = data.length,
  begin = 0, end = len - 1, next, i;

  for (;;) {
    // 順方向の走査
    next = begin;
    for (i = begin; i < end; i++) {
      if (cmp(data[i], data[i + 1]) > 0) {
        swap(data, i, i + 1);
        next = i;
      }
    }
    end = next;
    if (begin === end) break;

    // 逆方向の走査
    next = end;
    for (i = end; i > begin; i--) {
      if (cmp(data[i - 1], data[i]) > 0) {
        swap(data, i - 1, i);
        next = i;
      }
    }
    begin = next;
    if (begin === end) break;
  }

  return data;
}

/**
 * コムソート
 *
 * @param {Array} data ソートされる配列（破壊的に変更される）
 * @param {Function} cmp 比較関数（a > bのときは正の数、a == bのときは 0 、a < bのときは負の数）
 * @return {Array} ソートされた配列
 */
function combSort(data, cmp) {
  var
  len = data.length,
  h = ~~(len / 1.3),
  swaps, i;

  for (;;) {
    swaps = 0;
    for (i = 0; i + h < len; i++) {
      if (cmp(data[i], data[i + h]) > 0) {
        swap(data, i, i + h);
        swaps += 1;
      }
    }

    if (h === 1) {
      if (swaps === 0) break;
    } else {
      h = ~~(h / 1.3);
    }
  }

  return data;
}

/**
 * ノームソート
 *
 * @param {Array} data ソートされる配列（破壊的に変更される）
 * @param {Function} cmp 比較関数（a > bのときは正の数、a == bのときは 0 、a < bのときは負の数）
 * @return {Array} ソートされた配列
 */
function gnomeSort(data, cmp) {
  var
  len = data.length, i;

  for (i = 1; i < len; ) {
    if (cmp(data[i - 1], data[i]) > 0) {
      swap(data, i - 1, i);
      i -= 1;
      if (i === 0) {
        i += 2;
      }
    } else {
      i += 1;
    }
  }

  return data;
}

/**
 * 選択ソート
 *
 * @param {Array} data ソートされる配列（破壊的に変更される）
 * @param {Function} cmp 比較関数（a > bのときは正の数、a == bのときは 0 、a < bのときは負の数）
 * @return {Array} ソートされた配列
 */
function selectionSort(data, cmp) {
  var
  len = data.length, i, j, min;

  for (i = 0; i < len - 1; i++) {
    min = i;
    for (j = i + 1; j < len; j++) {
      if (cmp(data[min], data[j]) > 0) {
        min = j;
      }
    }
    swap(data, i, min);
  }

  return data;
}

/**
 * 挿入ソート
 *
 * @param {Array} data ソートされる配列（破壊的に変更される）
 * @param {Function} cmp 比較関数（a > bのときは正の数、a == bのときは 0 、a < bのときは負の数）
 * @return {Array} ソートされた配列
 */
function insertSort(data, cmp) {
  var
  len = data.length, tmp, i, j;

  for (i = 1; i < len; i++) {
    tmp = data[i];
    if (cmp(data[i - 1], tmp) > 0) {
      j = i;
      do {
        data[j] = data[j - 1];
        j -= 1;
      } while (j > 0 && cmp(data[j - 1], tmp) > 0);
      data[j] = tmp;
    }
  }

  return data;
}

/**
 * シェルソート
 *
 * @param {Array} data ソートされる配列（破壊的に変更される）
 * @param {Function} cmp 比較関数（a > bのときは正の数、a == bのときは 0 、a < bのときは負の数）
 * @return {Array} ソートされた配列
 */
function shellSort(data, cmp) {
  var
  len = data.length, tmp, h, i, j;

  for (h = len / 2; h >= 1; h = ~~(h / 2)) {
    for (i = 0; i < h; i++) {
      for (j = i + h; j < len; j += h) {
        tmp = data[j];
        if (cmp(data[j - h], tmp) > 0) {
          k = j;
          do {
            data[k] = data[k - h];
            k -= h; } while (k > 0 && cmp(data[k - h], tmp) > 0);
          data[k] = tmp;
        }
      }
    }
  }

  return data;
}

/**
 * マージソート
 *
 * @param {Array} data ソートされる配列
 * @param {Function} cmp 比較関数（a > bのときは正の数、a == bのときは 0 、a < bのときは負の数）
 * @return {Array} ソートされた配列
 */
function mergeSort(data, cmp) {
  var
  len = data.length, result, half, left, right, i, j;

  if (len === 1) return data;
  else if (len === 2) {
    if (cmp(data[0], data[1]) > 0) {
      swap(data, 0, 1);
    }
    return data;
  }

  half = ~~(len / 2);
  left = mergeSort(data.slice(0, half), cmp);
  right = mergeSort(data.slice(half, len), cmp);

  result = new Array(len);

  i = j = k = 0;
  while (i < left.length && j < right.length) {
    if (i >= left.length) {
      result[k++] = right[j++];
    } else if (j >= right.length) {
      result[k++] = left[i++];
    } else if (cmp(left[i], right[j]) <= 0) {
      result[k++] = left[i++];
    } else {
      result[k++] = right[j++];
    }
  }

  return result;
}

/**
 * ヒープソート
 *
 * @param {Array} data ソートされる配列（破壊的に変更される）
 * @param {Function} cmp 比較関数（a > bのときは正の数、a == bのときは 0 、a < bのときは負の数）
 * @return {Array} ソートされた配列
 */
function heapSort(data, cmp) {
  var
  len = data.length,
  i = 0, n, m, tmp, l, r;

  while (++i < len) {

    n = i;
    while (n > 0) {
      m = ~~((n + 1) / 2 - 1);
      if (cmp(data[m], data[n]) < 0) {
        swap(data, m, n);
      } else {
        break;
      }
      n = m;
    }
  }

  while (--i > 0) {
    swap(data, 0, i);

    n = i;
    m = 0;
    tmp = 0;
    for (;;) {
      l = (m + 1) * 2 - 1;
      r = (m + 1) * 2;
      if (l >= n) break;
      if (cmp(data[l], data[tmp]) > 0) {
        tmp = l;
      }
      if (r < n && cmp(data[r], data[tmp]) > 0) {
        tmp = r;
      }
      swap(data, tmp, m);
      if (tmp === m) break;

      m = tmp;
    }
  }

  return data;
}

/**
 * クイックソート
 *
 * @param {Array} data ソートされる配列（破壊的に変更される）
 * @param {Function} cmp 比較関数（a > bのときは正の数、a == bのときは 0 、a < bのときは負の数）
 * @return {Array} ソートされた配列
 */
function quickSort(data, cmp) {
  if (data.length <= 1) return data;

  var
  pivot = data[~~(data.length / 2)];
  return [].concat(
    quickSort(data.filter(function (x) { return cmp(x, pivot) < 0; }), cmp),
    data.filter(function (x) { return cmp(x, pivot) === 0; }),
    quickSort(data.filter(function (x) { return cmp(x, pivot) > 0; }), cmp));
}

/**
 * 
 * 奇遇転地ソート
 *
 * @param {Array} data ソートされる配列（破壊的に変更される）
 * @param {Function} cmp 比較関数（a > bのときは正の数、a == bのときは 0 、a < bのときは負の数）
 * @return {Array} ソートされた配列
 */
function oddEvenSort(data, cmp) {
  var
  len = data.length,
  i, flag = true;

  while (flag) {
    flag = false;
    for (i = 0; i < len-1; i += 2) {
      if (cmp(data[i], data[i+1]) > 0) {
        swap(data, i, i+1);
        flag = true;
      }
    }

    for (i = 1; i < len - 1; i += 2) {
      if (cmp(data[i], data[i+1]) > 0) {
        swap(data, i, i+1);
        flag = true;
      }
    }
  }

  return data;
}

// == テスト ==

function cmp(a, b) {
  return a - b;
}

function randomArray(len) {
  var
  data = [], i;

  for (i = 0; i < len; i++) {
    data.push(~~(Math.random() * 1000));
  }

  return data;
}

function check(data) {
  var
  i = 0,
  len = data.length;
  for (i = 0; i < len-1; i++) {
    if (data[i] > data[i+1]) {
      return false;
    }
  }
  return true;
}

function test(sort, maxLen) {
  var
  len,
  i, iter = 10,
  aveTime, maxTime, minTime, time, data;

  for (len = 10; len <= maxLen; len *= 10) {
    console.log("Case %d:", len);
    aveTime = 0;
    maxTime = 0;
    minTime = Number.MAX_VALUE;
    for (i = 0; i < iter; i++) {
      data = randomArray(len);
      time = process.hrtime();
      data = sort(data, cmp);
      time = process.hrtime(time);
      time = (time[0] * 1e9 + time[1]) / 1000 / 1000 / 1000;
      aveTime += time / iter;
      maxTime = Math.max(maxTime, time);
      minTime = Math.min(minTime, time);
      if (!check(data)) {
        console.log("fail!");
        console.log(data);
        return;
      }
    }
    console.log("ok!");
    console.log("  time:");
    console.log("    average: %ds", aveTime);
    console.log("    maximum: %ds", maxTime);
    console.log("    minimum: %ds", minTime);
  }
}