1
\$\begingroup\$

Never being good in "algorithming", I'm now trying to improve the situation a bit.

An algorithm below is the attempt to home brew yet another quicksort. This time, specifically with a "last-element" pivot selection strategy. Is there anything, I can improve better here?

Priorities

  1. Readability first. If it's not readable, it's broken.
  2. Performance. Yes, it's compiled into JavaScript. Yes, JavaScript is "slow". Point is, this code is just an exercise and will never get into production. Said that, I don't want it to be unnecessary inefficient.

Code

I really don't like sorting an array of primitive type element. Instead, I use Element<TKey> which is a key-value object, where the key is used to sort the array by it. Please assume the code is correct (as CR requires it). At least, the tests are green on 52 data inputs ranging from 0 to 99 elements.

import { Compare, SortableArray, swap } from '../sorting-env';

export function quicksort<T>(data: SortableArray<T>, lowIndex: number, highIndex: number, compare: Compare<T>): void {
  if (lowIndex < highIndex) {
    const pivotIndex = partition(data, lowIndex, highIndex, compare);
    quicksort(data, lowIndex, pivotIndex - 1, compare);
    quicksort(data, pivotIndex + 1, highIndex, compare);
  }
}

export function partition<T>(data: SortableArray<T>, lowIndex: number, highIndex: number, compare: Compare<T>): number {
  const originalPivotIndex = highIndex;
  const pivotValue = data[originalPivotIndex];
  let insertionIndex = lowIndex - 1;
  for (let index = lowIndex; index < highIndex; index++) {
    if (compare(data[index], pivotValue) < 0) {
      insertionIndex++;
      swap(data, index, insertionIndex);
    }
  }
  const newPivotIndex = insertionIndex + 1;
  swap(data, originalPivotIndex, newPivotIndex);
  return newPivotIndex;
}

The "helpers" are defined as following:

/** Function to compare two keys.
 * @returns A negative number if first operand is "less" than the second;
 * 0 if operands are "equal";
 * or a positive number otherwise.
 */
export type Compare<TKey> = (a: Element<TKey>, b: Element<TKey>) => number;

/** Represents an element in a sortable collection. */
export class Element<TKey> {
  /** The key to sort by. */
  key: TKey;
  /** Some value held by the element, related to the key. */
  value: any;
}

/** Represents an array which elements can be sorted by key. */
export type SortableArray<TKey> = Element<TKey>[];

/**
 * Swaps two elements in an array by indices (swapping happens in-place).
 * @param array Array which elements are being swapped.
 * @param index1 Index of first element to swap.
 * @param index2 Index of second element to swap.
 */
export function swap<T>(array: SortableArray<T>, index1: number, index2: number): void {
  const temporary = array[index1];
  array[index1] = array[index2];
  array[index2] = temporary;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I gave answering this a shot but didn't really see anything to improve. The only thing I can think to mention is that swap could be done with [ array[index1], array[index2] ] = [ array[index2], array[index1] ] -- and I'm not entirely sure this is a good idea. \$\endgroup\$ – Gerrit0 Oct 27 '17 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.