【アルゴリズム導論】c++実装スタックソート

1633 ワード

スタック・ソートの手順は説明されません.コードは次のとおりです.
void Build_Max_Heap(int array_list[] ,const int array_size,const int index);
bool HeapSort(int array_list[],const int array_size);
int main()
{
	const int size = 10;
	int array_list [] ={16,14,10,8,7,9,3,2,4,1};
	HeapSort(array_list,size);
	
	return 0;
}
bool HeapSort(int array_list[],const int array_size)
{
	if(array_size < 0)
	{
		return false;
	}
	for(int i=0;i<array_size;i++)
	{
		for(int j = ((array_size - i)/2-1);j>=0;j--)
		{
			Build_Max_Heap(array_list,array_size - i,j);
		}
		int tmp = array_list[0];
		array_list[0] = array_list[array_size -1 - i];
		array_list[array_size -1 - i] = tmp;
		std::cout<<"Sorted:"<<i+1<<"\t";
		for(int i=0;i<array_size;i++)
		{
			std::cout<<array_list[i]<<"\t";
		}
		std::cout<<std::endl;
	}
	return true;
}
/*     */
void Build_Max_Heap(int array_list[] ,const int array_size,const int index)
{
	int left_index = 2*index + 1;
	int right_index = 2*index + 2;
	int largest = index;
	if((right_index < array_size) )
	{/*       ,             ,           */
		if((array_list[left_index] < array_list[right_index]))
		{
			largest = right_index;
		}
		else
		{
			largest = left_index;
		}
	}
	else
	{
		if(left_index < array_size)
		{
			largest = left_index;
		}
	}
	if((array_list[index] < array_list[largest]) && (largest != index))
	{
		int tmp = array_list[index];
		array_list[index] = array_list[largest];
		array_list[largest] = tmp;
		/*           ,             */
		Build_Max_Heap(array_list,array_size,largest);
	}
}