Фрагмент программы quicksort (УМК ВМК)
Описание файла
Файл "Фрагмент программы quicksort" внутри архива находится в папке "УМК ВМК". Документ из архива "УМК ВМК", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "Фрагмент программы quicksort"
Текст из документа "Фрагмент программы quicksort"
Фрагмент программы quicksort(a, m, j) на языке C.
{ int i, j; int v, x; if (n <= m) return; /* Начало фрагмента */ i = m - 1; j = n; v = a[n]; while (1) { do i = i + 1; while (a[i] < v); do j = j - 1; while (a[j] > v); | if (i >= j) break; /* Обмен a[i], a[j] */ x = a[i]; a[i] = a[j]; a[j] = x; } /* Обмен a[i], a[n] */ x = a[i]; a[i] = a[n]; a[n] = x; /* Конец фрагмента */ quicksort(a,m,j); quicksort(a,i+1,n); } |
Внутреннее представление выделенного фрагмента (НББ – начало базового блока; номера инструкций добавлены для ссылок).
(1) | i = m-1 НББ | (16) | t7 = 4*i |
(2) | j = n | (17) | t8 = 4*j |
(3) | tl = 4*n | (18) | t9 = a[t8] |
(4) | v = a[tl] | (19) | a[t7] = t9 |
(5) | L1: i = i+1 НББ | (20) | t10 = 4*j |
(6) | t2 - 4*i | (21) | a[t10] = x |
(7) | t3 = a[t2] | (22) | goto L1 |
(8) | if t3<v goto L1 | (23) | L3: t11 = 4*i |
(9) | L2: j = j-1 НББ | (24) | x = a[t11] НББ |
(10) | t4 = 4*j | (25) | t12 = 4*i |
(11) | t5 - a[t4] | (26) | t13 = 4*n |
(12) | if t5>v goto L2 | (27) | t14 = a[t13] |
(13) | if i>=j goto L3 НББ | (28) | a[t12] = tl4 |
(14) | t6 = 4*i НББ | (29) | t15 = 4*n |
(15) | x = a[t6] | (30) | a[t15] = x |
Базовые блоки: A