Прежде чем начать, я бы предположил, что это, вероятно, больше подходит для информатики
Я не могу сказать, действительно ли это новый алгоритм сортировки; Я думаю, что для того, чтобы кто-то мог ответить на такой вопрос, ему нужно было бы иметь достаточно всестороннее знание алгоритмов сортировки, поскольку их довольно много.
Я могу продемонстрировать, как сравнивать производительность. Вам нужно сделать что-то похожее на других языках, если вы хотите протестировать их, и это тестирует только первые реализации каждой из них, которые я могу найти в inte rnet.
Чтобы правильно понять скорость алгоритм, который у вас есть, вам, вероятно, понадобится найти способ описать, как он работает в различных обстоятельствах; Я понимаю, что обычно это относительно математическое описание алгоритма; возможно, кто-то с большим знанием информатики мог бы восполнить этот пробел.
Но, несмотря на эти условия, вот что может работать при переполнении стека:
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')