Сортировка

Sorting - Сортировка

A normal problem with 3d programming, is the sorting algorithm. Either the one you have turns out too slow, or you dont understand it. Now, lets take a look at some of the diffrent kinds of sorting. We will run though sortings, as; bubble, quick and radix sort. There will be examples of how fast the algorithms works and of course the source. Now lets get on with it.

Обычная проблема в 3D программировании, связана с алгоритмом сортировки. Или тот, который Вы имеете, слишком медленный, или Вы, не  понимаете его. Теперь, посмотрим на некоторые из различных видов сортировки. Мы будем рассмотрим несколько методов сортировки, такие как; пузырьковая, быстрая и радикс-сортировка. Привидем пример и исходникик. Приступим.

Bubble sorting

The first algorithm we'll look at is the bubble sort. Bubble sort turns out to be the slowest of almost all sorting algorithms, but the code is rather small, which makes it very easy to remember. The code look like this:

Пузырьковая сортировка

Первый алгоритм, который мы рассмотрим - пузырьковая сортировка. Пузырьковая сортировка, окажется,  самый медленной из почти всех алгоритмов сортировки, но код довольно мал, что делает ее очень простой, чтобы помнить. Код выглядит следующим образом:

for (j=0;j<NUM_ELEMENTS-1;j++)

{

for (k=(i+1);k<NUM_ELEMENTS;k++)

{

if (array[j] < array[k])

{

temp = array[j];

array[j] = array[k];

array[k] = temp;

}

}

}

This routine will place the sorted data in the table called array, which is both destination and source table. This isnt very handy, when hacing to sort data, that are to be kept in the same place, and not moved (e.g face data). But what this routine basicly does, is to start from element number 0, and compare this to every other element in the array. If it finds anything that have a higher value, it replaces the two numbers, so that the first array-element eventually will get the highest value. Then it takes the next number, and the second interloop have become one run-through smaller, since the element which have just been sorted (at position 0) shouldnt be sorted once more. This way, the routine takes an amount of run-throughs of:

Эта программа сортирует данные в таблице называемой массивом, которая является, и приемной и исходной таблице. Этот не очень удобно, когда необходимо сортировать данные, которые должны храниться в том же самом месте, а не перемещаться (например данные экрана). Но что эта программа делает?  Она начинает с нулевого элемента, и сравнивает его с каждым другим элементом в массиве. Если при этом находится элемент, который имеет более большое значение, то переставляются эти два числа, так, чтобы первый элемент таблицы в конечном счете получил самое большое значение. Затем берется следующий элемент по номеру, и второй внутренний цикл становиться на один проход меньше, начиная с элемента, с которого только что сортировали (в позиции 0) чтобы не сортировать еще раз. Этим способом, программа имеет конечное количество просмотров:

n * n - (1 + 2 + 3 + 4 + 5 .. n)

Bit sorting (also called radix-sort)

In bitsort, we have a diffrent way of sorting our array. For a start, we ahve two diffrent tables, one for result and one for source. But this method is a totaly diffrent way of doing sorting. For a start, you dont look at each number, you look at the bits in each number. Now, you run through every element, and sort the numbers into two diffrent arrays. One array hold every number that have the first bit set, and another array hold every number that have the first bit empty. What you do now, it to put the array that holds the number with the first bits empty, and put this array right after the array that holds the numbers with the first bit set, so that you have a complete list once more, with all the numbers. Now you do the same for the next bit and so forth, until you have sorted every bit. This routine is appox. 300 times faster than the bubblesort.

Битовая сортировка ( так же называемая радикс-сортировкой)

В битовой сортировке, мы имеем другой способ сортировки нашего маасива. Для начала, мы имеем две различные таблицы, один для результата и один для источника. Но этот метод - вобщее отличается от способа выполнения сортировки. Для начала, Вы не  рассматриваете каждое число, Вы рассматриваете биты в каждом числе. Теперь, Вы пробегаете каждый элемент, и сортируете числа в две различные таблицы. В одной таблице сохраняете каждое число,  который имеет установленный первый бит, и в другую таблицу, помещаете каждое число, которое имеет первый бит нулевым. Дальше Вы помещаете таблицу, которая содержит числа с первыми нулевыми битами, и помещаете эту таблицу справа после таблицы, которая содержит числа с установленными первыми битами так, чтобы Вы имеете полный список еще раз, со всеми числами. Теперь Вы делаете тот же самое для следующего бита и т.д, пока Вы не отсортировали каждый бит. Эта программа - примерно в 300 раз быстрее, чем пузьрьковая сортировка.

Statics -  Статистика These results have been found on a K6-200, sorting an array of bytes with x components:

Результаты на K6-200:

Bubble sort   : 3825 elements pr. second

Bit sort      : 1294094 elements pr. Second