Есть ли у такого рода сортировки имя?

Question

Я написал / использовал этот вид сортировки.Мне просто интересно, имеет ли оно какое-либо имя или оно похоже на любой из существующих алгоритмов сортировки.Кстати, это даже эффективно / достойно или не очень?

int s = 20;

int unsorted_array[s];

//(adding numbers to unsorted_array)
//We assume that every number is different to avoid any difficulties.

int i, i2, pos;
int sorted_array[s];

//!!! sorting algo starts here:

for(i=0; i<s; i++){
   pos = 0;
   for(i2=0; i2<s; i2++){

      if(unsorted_array[i] > unsorted_array[i2]){
         pos += 1;
      }
   }

   sorted_array[pos] = unsorted_array[i];

}

Так что вы думаете?это медленнее / быстрее, чем другие виды сортировки?Я еще учусь.спасибо за любые ответы!

Answer 1

Это медленнее / быстрее, чем другие методы сортировки?

Давайте проанализируем сложность времени этой функции .Как много работы потребуется для увеличения размера несортированного списка?

Важной частью являются циклы.Они скажут нам, сколько раз вам нужно сделать это, и вот что важно.Ваши циклы можно разбить на это:

for(1 to s){
   for(1 to s){
       do that thing
   }
}

Для каждого элемента он должен перепроверить каждый элемент.Если есть 2 предмета, это значит, что вы делаете это 4 раза.3 предмета, 9 раз.4 предмета, 16 раз.Мы говорим, что временная сложность равна n^2 (n - это условное обозначение размера), потому что при увеличении размера число шагов возводится в квадрат.Это означает, что время, которое требуется, будет расти экспоненциально с увеличением размера.На 10 предметов это занимает 100 раз.На 100 предметов уходит 10000.На 1000 это занимает 1 000 000.Если возможно, следует избегать n^2.

Большинство алгоритмов сортировки могут выполнять свою работу за n * log(n) или квазилинейное время.По мере увеличения размера время будет увеличиваться на n * log(n).Это быстрее, чем линейный, но медленнее, чем экспоненциальный.log(n) часто является натуральным логарифмом или ln(n).На 10 предметов это займет около 23 раз.100 около 460. При 1000 около 6900. Так что ваш алгоритм медленнее.

Алгоритмы выше n * log(n) растут настолько быстро, что необходимо искажать вертикальшкала времени, чтобы осмысленно разместить их на одном графике с более эффективными алгоритмами.

Как вы можете догадаться, для большого количества элементов важнее иметь более эффективный алгоритм, чем выполнять его быстрее.Алгоритм n^2, который делает вещь в 100 раз быстрее, чем n log n, потеряет около 600 предметов.

n^2 = 100 n * ln(n)
n = 100 ln(n)
n / ln(n) = 100

Answer 2

Мне кажется, что это своего рода обратный выбор.Сортировка выбора скажет "какой элемент находится в позиции 0?"а затем найти этот элемент.Ваш вид, кажется, говорит: «Куда идет элемент, находящийся в данный момент в позиции 0?», Что является одинаково действительным вопросом.

С точки зрения сложности, это определенно O(n^2), что ставит его в один ряд сдругие «неэффективные» схемы, такие как вставка, выделение, всплывающее окно и т. д., и ставят их ниже более сложных «лучших», таких как слияние или быстрое.Основное беспокойство, которое я имею в виду, заключается в том, что вы фактически повторяете n^2 раз, тогда как алгоритмы, такие как вставка или выделение, могут обходиться без n (n + 1) / 2 (треугольные числа, а не квадратные), что является той же сложностьюкласс, но меньшее число в целом.Кроме того, ваша сортировка требует от нас создания нового массива в памяти, в то время как многие из существующих (вставка и выбор, в частности, поскольку они своего рода близки к вашему) могут выполняться в постоянном пространстве без выделения какого-либобольше массивов.

Answer 3

Это работает, находя, для каждого элемента в массиве, количество элементов меньше его.Это эквивалентно нахождению его окончательной позиции.

Это медленный O(n*n) (есть приличные алгоритмы O(n*lg(n))).Но существует множество O(n*n) алгоритмов сортировки, поэтому вы находитесь в хорошей компании.

Он также работает только с уникальными значениями, что является довольно серьезным ограничением.

Это также требуетвторой массив для копирования, в который большинство алгоритмов сортировки этого не делают, это еще один минус.

С другой стороны, он делает ноль свопов и только очень небольшое количество фактических копий (точно ninfact), что в некоторых случаях может быть хорошей вещью, но это довольно незначительный плюс.