February 14th, 2009

with Cat The Cat

Про пузырьковую сортировку.

Вот сортировка пузырьком:
void bubble_sort(int *arr,int len) {
    int i,j;
    for (i=0;i < len-1;i++)
        for (j=0;j < len-1-i;j++) {
            if (arr[j] > arr[j+1]) {
                int t = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = t;
            }
        }
} /* bubble_sort */
Каждая итерация зависит от предыдущей в обеих циклах.

Зависит умеренно хитро:
(0,3)
  |
(0,2) - (1,2)
  |   /   |
(0,1) - (1,1) - (2,1)
  |   /   |   /   |
(0,0) - (1,0) - (2,0) - (3,0)
Выход (i,j) влияет на входы (i,j+1), (i+1,j) и (i+1,j+1).

А что будет, если перебирать индексы так, чтобы их сумма была постоянна? Вот так:
- итерация 0: (0,0),
- итерация 1: (0,1), (1,0),
- итерация 2: (0,2), (1,1), (2,0),
- итерация 3: (0,3), (1,2), (2,1) и (3,0).

Внезапно исчезает зависимость между итерациями внутреннего цикла - от (i,j) зависят (i+(0|1),j+(0|1)), а их сумма всегда больше текущей и, значит, они принадлежат следующей итерации.

Получается, что части внутреннего цикла могут быть выполнены параллельно.

Как это формализовать, не знаю. ;)

В принципе, это перекошивание циклов (loop skewing). Но как догадаться, в какую сторону наклонять...