Array sort integer

Benchmark created on March 10, 2023

Description

Setup

function sortOneLoopAlgorithm(arr)
{
 
    // Finding the length of array 'arr'
        let length = arr.length;
   
        // Sorting using a single loop
        for (let j = 0; j < length - 1; j++) {
   
            // Checking the condition for two
            // simultaneous elements of the array
            if (arr[j] > arr[j + 1]) {
   
                // Swapping the elements.
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
   
                // updating the value of j = -1
                // so after getting updated for j++
                // in the loop it becomes 0 and
                // the loop begins from the start.
                j = -1;
            }
        }
   
        return arr;
}
Array.prototype.sortOneLoopAlgorithm = function ()
{
 
 let arr = this
    // Finding the length of array 'arr'
        let length = arr.length;
   
        // Sorting using a single loop
        for (let j = 0; j < length - 1; j++) {
   
            // Checking the condition for two
            // simultaneous elements of the array
            if (arr[j] > arr[j + 1]) {
   
                // Swapping the elements.
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
   
                // updating the value of j = -1
                // so after getting updated for j++
                // in the loop it becomes 0 and
                // the loop begins from the start.
                j = -1;
            }
        }
   
        return arr;
}
function jsMethod (arr) {
	return arr.sort((a, b ) => a-b)
}
function jsMethod2 (arr) {
	return arr.sort((a, b ) => a > b ? 1 : -1)
}
function radixSort(arr) {
  // Determine the maximum number of digits in the input array
  const getMaxDigits = (arr) => {
    let maxDigits = 0;
    for (let i = 0; i < arr.length; i++) {
      maxDigits = Math.max(maxDigits, Math.floor(Math.log10(arr[i])) + 1);
    }
    return maxDigits;
  };
  
  // Sort the input array based on the digit at the given exponent
  const countingSort = (arr, exp) => {
    const count = new Array(10).fill(0);
    const output = new Array(arr.length);
    
    for (let i = 0; i < arr.length; i++) {
      const digit = Math.floor((arr[i] / exp) % 10);
      count[digit]++;
    }
    
    for (let i = 1; i < 10; i++) {
      count[i] += count[i - 1];
    }
    
    for (let i = arr.length - 1; i >= 0; i--) {
      const digit = Math.floor((arr[i] / exp) % 10);
      output[count[digit] - 1] = arr[i];
      count[digit]--;
    }
    
    for (let i = 0; i < arr.length; i++) {
      arr[i] = output[i];
    }
  };
  
  // Sort the input array using radix sort
  const maxDigits = getMaxDigits(arr);
  let exp = 1;
  
  for (let i = 0; i < maxDigits; i++) {
    countingSort(arr, exp);
    exp *= 10;
  }
  
  return arr;
}
function countingSort(arr) {
  // Find the range of values in the input array
  const minVal = Math.min(...arr);
  const maxVal = Math.max(...arr);
  const count = new Array(maxVal - minVal + 1).fill(0);
  
  // Count the number of occurrences of each value in the input array
  for (let i = 0; i < arr.length; i++) {
    count[arr[i] - minVal]++;
  }
  
  // Calculate the cumulative sum of the counts
  for (let i = 1; i < count.length; i++) {
    count[i] += count[i - 1];
  }
  
  // Sort the input array using the count array
  const output = new Array(arr.length);
  
  for (let i = arr.length - 1; i >= 0; i--) {
    const index = count[arr[i] - minVal] - 1;
    output[index] = arr[i];
    count[arr[i] - minVal]--;
  }
  
  // Copy the sorted elements back to the original array
  for (let i = 0; i < arr.length; i++) {
    arr[i] = output[i];
  }
  
  return arr;
}

const numArr = [1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10]

Test runner

// arr.sort((a, b ) => a-b)
jsMethod(numArr)

// arr.sort((a, b ) => a > b ? 1 : -1)
jsMethod2(numArr)

// Our sort algorithm running just 1 loop
sortOneLoopAlgorithm(numArr)

// Our sort algorithm running just 1 loop
numArr.sortOneLoopAlgorithm()

// One of the best integer sort algorithm
radixSort(numArr)

// One of the best integer sort algorithm
countingSort(numArr)

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published on March 10, 2023