sebinsua · August 16, 2023 16:12 · sebinsua · Aug 15, 2023
diff --git a/in-place-iterative-quicksort.ts b/in-place-iterative-quicksort.ts
 type Slice = [lowIndex: number, highIndex: number];

 function getRandomIntegerInRange([low, high]: Slice): number {
  return Math.floor(Math.random() * (high - low + 1)) + low;
 }

 function createPartitionForSlice([lowIndex, highIndex]: Slice) {
  return function partition(pivotIndex: number, items: number[]): number {
    // Partitioning a slice works like so:
    // - We get the pivot value from the pivot index (in our case, a random index
    //   that was passed in).
    // - We move the pivot value to the end of the slice so it is easier to avoid.
    // - We iterate over the slice, swapping any values less than the pivot value,
    //   so that they are at the beginning of the slice. (Note: they are not sorted.)
    // - Finally, we move the pivot value that we placed at the end of the slice to
    //   the end of the values less than the pivot value (the `nextLowElementIndex`)
    //   and we then return this new pivot index.
    const pivotValue = items[pivotIndex];

    [items[pivotIndex], items[highIndex]] = [
      items[highIndex],
      items[pivotIndex],
    ];

    let nextLowElementIndex = lowIndex;
    for (let i = lowIndex; i < highIndex; i++) {
      if (items[i] < pivotValue) {
        [items[nextLowElementIndex], items[i]] = [
          items[i],
          items[nextLowElementIndex],
        ];
        nextLowElementIndex++;
      }
    }

    const finalPivotIndex = nextLowElementIndex;
    [items[finalPivotIndex], items[highIndex]] = [
      items[highIndex],
      items[finalPivotIndex],
    ];

    return finalPivotIndex;
  };
 }

 // This demonstrates the iterative in-place quicksort algorithm.
 function quicksort(items: number[]): void {
  if (items.length <= 1) {
    return;
  }

  // We start the `stack` with a slice encompassing the entire array.
  const initialSlice: Slice = [0, items.length - 1];
  const stack = [initialSlice];
  while (stack.length > 0) {
    const [lowIndex, highIndex] = stack.pop()!;

    // Our in-place partition function will operate upon a specific slice
    // of the array. We use a higher-order function for expressivity.
    const partition = createPartitionForSlice([lowIndex, highIndex]);

    // In order to avoid worst-case performance (O(n^2)) when an array
    // has already been sorted we randomize the pivot index.
    const pivotIndex = getRandomIntegerInRange([lowIndex, highIndex]);

    // We partition the slice in-place and get the new pivot index
    // that the pivot value is now at after it has been moved.
    //
    // After execution the chosen slice within `items` is partitioned so 
    // that it contains two future slices and the pivot:
    //
    // 1. items[lowIndex..newPivotIndex - 1] contains values less than the pivot value
    // 2. items[newPivotIndex] contains the pivot value
    // 3. items[newPivotIndex + 1..highIndex] contains values greater than the pivot value
    const newPivotIndex = partition(pivotIndex, items);

    // We now push the less-than and greater-than slices onto the stack as long as they
    // contain more than one item.
    //
    // - The slices do not contain the pivot itself since after a partition this is positioned
    //   in its correct, sorted position relative to the entire array.
    // - Slices with one item only are already sorted and therefore not added onto the stack.
    // - Once we no longer have slices in the `stack`, the `items` array is fully sorted.
    if (newPivotIndex - lowIndex > 1) {
      stack.push([lowIndex, newPivotIndex - 1]);
    }

    if (highIndex - newPivotIndex > 1) {
      stack.push([newPivotIndex + 1, highIndex]);
    }
  }
 }

 // Test 1
 const data = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6];

 quicksort(data);

 console.log(data);

 // Test 2
 const data2 = [
  8, 99, 998, 17, 10, 68, 2, 10021, 6, 2, 4, 234, 9, 456, 1, 2, 3, 9, 7, 5, 9,
  3, 6, 5,
 ];

 quicksort(data2);

 console.log(data2);
	type Slice = [lowIndex: number, highIndex: number];

	function getRandomIntegerInRange([low, high]: Slice): number {
	return Math.floor(Math.random() * (high - low + 1)) + low;
	}

	function createPartitionForSlice([lowIndex, highIndex]: Slice) {
	return function partition(pivotIndex: number, items: number[]): number {
	// Partitioning a slice works like so:
	// - We get the pivot value from the pivot index (in our case, a random index
	// that was passed in).
	// - We move the pivot value to the end of the slice so it is easier to avoid.
	// - We iterate over the slice, swapping any values less than the pivot value,
	// so that they are at the beginning of the slice. (Note: they are not sorted.)
	// - Finally, we move the pivot value that we placed at the end of the slice to
	// the end of the values less than the pivot value (the `nextLowElementIndex`)
	// and we then return this new pivot index.
	const pivotValue = items[pivotIndex];

	[items[pivotIndex], items[highIndex]] = [
	items[highIndex],
	items[pivotIndex],
	];

	let nextLowElementIndex = lowIndex;
	for (let i = lowIndex; i < highIndex; i++) {
	if (items[i] < pivotValue) {
	[items[nextLowElementIndex], items[i]] = [
	items[i],
	items[nextLowElementIndex],
	];
	nextLowElementIndex++;
	}
	}

	const finalPivotIndex = nextLowElementIndex;
	[items[finalPivotIndex], items[highIndex]] = [
	items[highIndex],
	items[finalPivotIndex],
	];

	return finalPivotIndex;
	};
	}

	// This demonstrates the iterative in-place quicksort algorithm.
	function quicksort(items: number[]): void {
	if (items.length <= 1) {
	return;
	}

	// We start the `stack` with a slice encompassing the entire array.
	const initialSlice: Slice = [0, items.length - 1];
	const stack = [initialSlice];
	while (stack.length > 0) {
	const [lowIndex, highIndex] = stack.pop()!;

	// Our in-place partition function will operate upon a specific slice
	// of the array. We use a higher-order function for expressivity.
	const partition = createPartitionForSlice([lowIndex, highIndex]);

	// In order to avoid worst-case performance (O(n^2)) when an array
	// has already been sorted we randomize the pivot index.
	const pivotIndex = getRandomIntegerInRange([lowIndex, highIndex]);

	// We partition the slice in-place and get the new pivot index
	// that the pivot value is now at after it has been moved.
	//
	// After execution the chosen slice within `items` is partitioned so
	// that it contains two future slices and the pivot:
	//
	// 1. items[lowIndex..newPivotIndex - 1] contains values less than the pivot value
	// 2. items[newPivotIndex] contains the pivot value
	// 3. items[newPivotIndex + 1..highIndex] contains values greater than the pivot value
	const newPivotIndex = partition(pivotIndex, items);

	// We now push the less-than and greater-than slices onto the stack as long as they
	// contain more than one item.
	//
	// - The slices do not contain the pivot itself since after a partition this is positioned
	// in its correct, sorted position relative to the entire array.
	// - Slices with one item only are already sorted and therefore not added onto the stack.
	// - Once we no longer have slices in the `stack`, the `items` array is fully sorted.
	if (newPivotIndex - lowIndex > 1) {
	stack.push([lowIndex, newPivotIndex - 1]);
	}

	if (highIndex - newPivotIndex > 1) {
	stack.push([newPivotIndex + 1, highIndex]);
	}
	}
	}

	// Test 1
	const data = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6];

	quicksort(data);

	console.log(data);

	// Test 2
	const data2 = [
	8, 99, 998, 17, 10, 68, 2, 10021, 6, 2, 4, 234, 9, 456, 1, 2, 3, 9, 7, 5, 9,
	3, 6, 5,
	];

	quicksort(data2);

	console.log(data2);