【アルゴリズム導論】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);
}
}