A new sorting algorithm or a rediscovery?

Question

I'm a novice programmer who just started learning JavaScript. While I was reading about array sorting, I came across QuickSort and looked into its algorithm. Then I thought I could come up with my own 'algorithm'.

My solution works like this. It starts by looking for the smallest and largest values and swaps them with the corner values simultaneously. It then runs recursively until both ends are equal or pass each other.

So, is this a new algorithm or a rediscovery?

This is my version of a sorting algorithm. My question is :

1. Do you know of any other sorting algorithm that works like this?

2. how can I test it's speed vis-a-vis quicksort, bubble sort...?

'use strict';

//  +   Name : CornerSort function for sorting arrays                          +
//  +   Author : Kedyr                                                         +
//  +   Date : Jan 15 , 2020                                                   +
//  +   Description : The corner sort function is my first shot at sorting     +
//  +               algorithms.After looking into the quick sort algorithm     +
//  +               i tried to come up with my own sorting logic.It works      +
//  +               by finding the lowest and highest values in an array       +
//  +               and then replacing these values with the corner values.    +
//  +               These process continues recursively until all values are   +
//  +               correctly sorted.Now , from what i can see i believe it    +
//  +               to be a stable sorting algorithm.I haven't tested its      +
//  +               sorting speed and would love it if some one did that.      +
//  +               That is , if it is not an already known algorithm which    +
//  +               I haven't come across yet.Whatever the case is , I am      +
//  +               going to elaborately discuss my 'new' discovery step by    +
//  +               step in the comments . So please bear with me .            +
//  +               For the geniuses who created this algorith before me ,     +
//  +               (if there are any), I bow down to you dear masters.        +
//  +               please forgive my insolence. You know I wouldn't do it     +
//  +               intentionally . It is just that genius minds think         +
//  +               alike . :)                                                 +
//  ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

function cornerSort(array, startIndex = 0, endIndex = array.length - 1) {
  // These checks if the function is already ordered .
  if (checkOrder(array, startIndex, endIndex)) {
    return;
  }
  // the lowest and highest values.initialised to corner values.
  let lowest = array[startIndex],
    highest = array[endIndex];
  // Indices for the lowest and highest numbers in each recursion. 
  let lowIndex = startIndex,
    highIndex = endIndex;
  let temp;
  if (startIndex >= endIndex) {
    return;
  }
  for (let i = startIndex; i <= endIndex; i++) {
    if (array[i] >= highest) {
      //'or-equal-to' is added to ensure the sorting doesn't change the
      //order of equal numbers.Thus , a stable sorting algorithm.
      highest = array[i];
      highIndex = i;
    }
    if (array[i] < lowest) {
      lowest = array[i];
      lowIndex = i;
    }
  }
  // A PRECAUTION 'IF' : for when the highest number is at the beginning of the array.
  if (highIndex == startIndex) {
    highIndex = lowIndex;
  }
  // The opposite case , lowest number at the end of array ; doesn't cause any issues.
  if (lowIndex != startIndex) {
    temp = array[startIndex];
    array[startIndex] = array[lowIndex];
    array[lowIndex] = temp;
  }
  if (endIndex != highIndex) {
    temp = array[endIndex];
    array[endIndex] = array[highIndex];
    array[highIndex] = temp;
  }
  cornerSort(array, ++startIndex, --endIndex);
  return array;
}

// The CHECKORDER function checks if the array is actually sorted so as to avoid
// unnecessary rounds of recursion.
function checkOrder(array, startIndex, endIndex) {
  let unsortedCount = 0; // count of cases where array[i] > array[i+1].
  for (let i = startIndex; i <= endIndex; i++) {
    if (array[i] > array[i + 1]) {
      unsortedCount++;
    }
  }
  if (!unsortedCount) {
    return true;
  }
  return false;
}
//..............................................................................

Answer 1

It's certainly not impossible to invent a genuinely new sorting algorithm, since there are so many different possible ways to sort. However, your algorithm exists: it is called double-ended selection sort.

Selection sort works by iteratively selecting the smallest element in the unsorted part of the array, and swapping it into place. Your algorithm is a variation of selection sort because it also selects the largest element in the unsorted part of the array and swaps that into place in the same iteration of the outer loop. This means the unsorted part is a middle segment rather than an end segment of the array.

Your implementation is also quite a lot more complicated than it needs to be: here's a simplified version which should be very slightly more efficient due to the else if in the inner loop. An element cannot be both lower than lowest and higher than highest. Since we're scanning for both the lowest and highest elements, it's also possible to detect when the "unsorted" part of the array is constant (i.e. all its values are the same) and break early.

function doubleEndedSelectionSort(arr) {
    for(var i = 0, j = arr.length - 1; i < j; i++, j--) {
        var minIdx = i, maxIdx = i;
        var lowest = arr[minIdx], highest = arr[maxIdx];
        for(var k = i + 1; k <= j; k++) {
            var value = arr[k];
            if(value < lowest) {
                minIdx = k;
                lowest = value;
            } else if(value > highest) {
                maxIdx = k;
                highest = value;
            }
        }
        if(minIdx === maxIdx) { break; } // the "unsorted" part of the array is constant
        var iValue = arr[i], jValue = arr[j];
        arr[minIdx] = iValue;
        arr[i] = lowest;
        arr[maxIdx] = jValue;
        arr[j] = highest;
    }
}

Regarding performance, the time complexity of the algorithm is the same as selection sort's O(n²), because it still has nested loops which iterate O(n) times each. In your implementation, the outer loop is replaced with recursion, but it still recurses O(n) times, so the effect is the same. That means for large enough inputs it will perform worse than O(n log n) sorting algorithms such as quicksort, merge sort, or heap sort.

Answer 2

Before I start, I'd suggest that this is probably more appropriate for computer science

I can't really say whether or not this is a new sorting algorithm; I think for someone to answer such a question they'd need to have a fairly comprehensive knowledge of sorting algorithms, as there are quite a few.

What I can demonstrate is how to compare performance. You'd need to do something similar in other languages, if you want to test those, and this only tests the first implementations of each I could find on the internet.

To properly understand the speed of the algorithm you have, you'd probably need to find a way to describe how it performs in different circumstances; I understand this normally involves a relatively mathematical description of the algorithm; perhaps someone with more computer science knowledge could fill in that gap.

But, despite those provisos, here's something that can work in stack overflow:

function cornerSort(array, startIndex = 0, endIndex = array.length - 1) {
  // These checks if the function is already ordered .
  if (checkOrder(array, startIndex, endIndex)) {
    return;
  }
  // the lowest and highest values.initialised to corner values.
  let lowest = array[startIndex],
    highest = array[endIndex];
  // Indices for the lowest and highest numbers in each recursion. 
  let lowIndex = startIndex,
    highIndex = endIndex;
  let temp;
  if (startIndex >= endIndex) {
    return;
  }
  for (let i = startIndex; i <= endIndex; i++) {
    if (array[i] >= highest) {
      //'or-equal-to' is added to ensure the sorting doesn't change the
      //order of equal numbers.Thus , a stable sorting algorithm.
      highest = array[i];
      highIndex = i;
    }
    if (array[i] < lowest) {
      lowest = array[i];
      lowIndex = i;
    }
  }
  // A PRECAUTION 'IF' : for when the highest number is at the beginning of the array.
  if (highIndex == startIndex) {
    highIndex = lowIndex;
  }
  // The opposite case , lowest number at the end of array ; doesn't cause any issues.
  if (lowIndex != startIndex) {
    temp = array[startIndex];
    array[startIndex] = array[lowIndex];
    array[lowIndex] = temp;
  }
  if (endIndex != highIndex) {
    temp = array[endIndex];
    array[endIndex] = array[highIndex];
    array[highIndex] = temp;
  }
  cornerSort(array, ++startIndex, --endIndex);
  return array;
}

// The CHECKORDER function checks if the array is actually sorted so as to avoid
// unnecessary rounds of recursion.
function checkOrder(array, startIndex, endIndex) {
  let unsortedCount = 0; // count of cases where array[i] > array[i+1].
  for (let i = startIndex; i <= endIndex; i++) {
    if (array[i] > array[i + 1]) {
      unsortedCount++;
    }
  }
  if (!unsortedCount) {
    return true;
  }
  return false;
}

function bubbleSort(a) {
    var swapped;
    do {
        swapped = false;
        for (var i=0; i < a.length-1; i++) {
            if (a[i] > a[i+1]) {
                var temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                swapped = true;
            }
        }
    } while (swapped);
}

function swap(items, leftIndex, rightIndex){
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}
function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], //middle element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //sawpping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}


const testData = [...Array(10000).keys()].map(x => Math.random() * 1000)

console.time('corner')
const x = cornerSort(testData);
console.timeEnd('corner')

console.time('bubble')
const y = bubbleSort(testData);
console.timeEnd('bubble')

console.time('quick')
const z = quickSort(testData);
console.timeEnd('quick')