В ходе разработки сложного программного проекта произошел сбой в системе контроля версий. В результате в коде функции heapSort произошли изменения. Известно, что в качестве параметров подается массив целых чисел и размер массива этого массива. В результате выполнения функции должен быть получен отсортированный массив.
Найдите ошибку, которая была внесена в исходный код в результате сбоя.
|
C |
Pascal |
|
void downHeap(int a[],long k,long n) { intnew_elem; long child; new_elem = a[k]; while(k <= n/2) { child = 2*k; if(child<n&&a[child]<a[child+1]) child++; if( new_elem>= a[child] ) break; a[k] = a[child]; k = child; } a[k] = new_elem; } void heapSort(int a[], long size) { long i; int temp; for(i=size/2-1; i >= 0; i--) downHeap(a, i, size-1); for(i=size-1; i > 0; i--) { temp=a[i]; a[i]=a[0]; a[0]=temp; downHeap(a, 0, i); } } |
procedure heapSort (var a:array[0..n] of integer; var n: integer;) var i: integer; temp: integer;
procedure downHeap (var a:array[0..n] of integer; var n: integer; var k: integer); var new_element: integer; child: integer; label 1; begin new_element:=a[k]; while k <= n/2 do begin child:=2*k; if((child<n)&&(a[child]<a[child+1])) then goto 1; a[k]:=a[child]; k:=child; end; 1:a[k]=new_element; end;
begin for i:=n/2-1 downto 0 do downHeap(a,n,i); for i:=n-1 downto 0 do begin temp:=a[i]; a[i]:=a[0]; a[0]:=temp; downHeap(a,0,i) end; end;
|
Пронумеруем все строки алгоритма и структурируем его.
(1)voiddownHeap(int a[], long k, long n)
(2){
(3) intnew_elem;
(4) long child;
(5) new_elem = a[k];
(6) while(k <= n/2)
(7) {
(8) child = 2*k;
(9) if( child < n && a[child] < a[child+1] )
(10) child++;
(11) if(new_elem>= a[child] )
(12) break;
(13) a[k] = a[child];
(14) k = child;
(15) }
(16) a[k] = new_elem;
(17)}
(18)voidheapSort(int a[], long size)
(19){
(20) long i;
(21) int temp;
(22) for(i=size/2-1; i >= 0; i--)
(23) downHeap(a, i, size-1);
(24) for(i=size-1; i > 0; i--)
(25) {
(26) temp=a[i];
(27) a[i]=a[0];
(28) a[0]=temp;
(29)downHeap(a, 0, i);
(30) }
(31)}
Рассматриваемый исходный код представляет собой реализацию алгоритма пирамидальной сортировки.
Алгоритм на первом этапе строит пирамиду, которая имеет следующую структуру. На верху пирамиды находится один элемент. У каждого элемента есть два потомка, которые меньше или равны родителя. Каждая цепочка от вершины до основания имеет длину m или m+1. Построенная пирамида укладывается в массив. Для элемента массива с номеромi потомки имеют индексы 2i+1 и 2i+2, а родитель – целая часть от деление iпополам.
На втором этапе алгоритм заменяет вершину пирамиды (максимальный элемент) на последний элемент в массиве. Далее на всех элементах пирамиды кроме последнего происходит построение пирамиды (первый этап). Затем заменяется вершина вновь построенной пирамиды на второй элемент с конца. Количество таких повторений равно количеству элементов в массиве.
Заметим, что в строке 29 после замены вершины пирамиды на очередной правый элемент происходит перестроение пирамиды с использованием замененного элемента i, что не верно. На некотором шаге получиться ситуацию, когда при применении функции downHeapi-ый элемент переместится в вершину пирамиды, что нарушит сортировку. Для правильной работы алгоритма необходимо перестроить пирамиду для элементов от 0 до i-1.
Правильная реализация с комментариями представлена ниже.
(1)voiddownHeap(int a[], long k, long n)
(2){
// процедура просеивания следующего элемента
// До процедуры: a[k+1]...a[n] - пирамида
// После: a[k]...a[n] - пирамида
(3) intnew_elem;
(4) long child;
(5) new_elem = a[k];
// пока у a[k] есть дети
(6) while(k <= n/2)
(7) {
(8) child = 2*k;
// выбираем большего сына
(9) if( child < n && a[child] < a[child+1] )
(10) child++;
(11) if(new_elem>= a[child] )
(12) break;
// переносим сына наверх
(13) a[k] = a[child];
(14) k = child;
(15) }
(16) a[k] = new_elem;
(17)}
(18)voidheapSort(int a[], long size)
(19){
(20) long i;
(21) int temp;
// строим пирамиду
(22) for(i=size/2-1; i >= 0; i--)
(23) downHeap(a, i, size-1);
// теперьa[0]...a[size-1] пирамида
(24) for(i=size-1; i > 0; i--)
(25) {
// меняем первый с последним
(26) temp=a[i];
(27) a[i]=a[0];
(28) a[0]=temp;
// восстанавливаем пирамидальность a[0]...a[i-1]
(29)downHeap(a, 0, i-1);
(30) }
(31)}
(1)voiddownHeap(int a[], long k, long n)
(2){
// процедура просеивания следующего элемента
// До процедуры: a[k+1]...a[n] - пирамида
// После: a[k]...a[n] - пирамида
(3) intnew_elem;
(4) long child;
(5) new_elem = a[k];
// пока у a[k] есть дети
(6) while(k <= n/2)
(7) {
(8) child = 2*k;
// выбираем большего сына
(9) if( child < n && a[child] < a[child+1] )
(10) child++;
(11) if(new_elem>= a[child] )
(12) break;
// переносим сына наверх
(13) a[k] = a[child];
(14) k = child;
(15) }
(16) a[k] = new_elem;
(17)}
(18)voidheapSort(int a[], long size)
(19){
(20) long i;
(21) int temp;
// строим пирамиду
(22) for(i=size/2-1; i >= 0; i--)
(23) downHeap(a, i, size-1);
// теперьa[0]...a[size-1] пирамида
(24) for(i=size-1; i > 0; i--)
(25) {
// меняем первый с последним
(26) temp=a[i];
(27) a[i]=a[0];
(28) a[0]=temp;
// восстанавливаем пирамидальность a[0]...a[i-1]
(29)downHeap(a, 0, i-1);
(30) }
(31)}