ソート関連アルゴリズム-2

  
  
  
  

   
   
   
   
void Disp2(int iarr[], int length) 
   
   
   
   
{ 
   
   
   
   
    for(int loop1 = 0; loop1 < length; ++loop1) 
   
   
   
   
        cout<<iarr[loop1]<<' '; 
   
   
   
   
    cout<<endl; 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
 
   
   
   
   
void InsertSort2(int iarr[], int length) 
   
   
   
   
{ 
   
   
   
   
    int loop1 = 0, loop2 = 0, temp = 0; 
   
   
   
   
     
   
   
   
   
    for(loop1 = 1; loop1 < length; ++loop1) 
   
   
   
   
    { 
   
   
   
   
        temp  = iarr[loop1]; 
   
   
   
   
        loop2 = loop1 - 1; 
   
   
   
   
        while(loop2 >= 0)        
   
   
   
   
            if(iarr[loop2] > temp) 
   
   
   
   
            {    iarr[loop2 + 1] = iarr[loop2]; --loop2;} 
   
   
   
   
            else break; 
   
   
   
   
         
   
   
   
   
        iarr[loop2 + 1] = temp; 
   
   
   
   
    } 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
void ShellSort2(int iarr[], int length) 
   
   
   
   
{ 
   
   
   
   
    int loop1 = 0, loop2 = 0, temp = 0,gap = length / 2; 
   
   
   
   
 
   
   
   
   
    while(gap > 0) 
   
   
   
   
    { 
   
   
   
   
        for(loop1 = gap; loop1 < length; ++loop1) 
   
   
   
   
        { 
   
   
   
   
            temp  = iarr[loop1]; 
   
   
   
   
            loop2 = loop1 - gap; 
   
   
   
   
            while(loop2 >= 0 && iarr[loop2] > temp) 
   
   
   
   
            { 
   
   
   
   
                iarr[loop2 + gap] = iarr[loop2]; 
   
   
   
   
                loop2 = loop2 - gap; 
   
   
   
   
            } 
   
   
   
   
            iarr[loop2 + gap] = temp; 
   
   
   
   
        } 
   
   
   
   
        gap = gap / 2; 
   
   
   
   
    } 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
void SelectSort2(int iarr[], int length) 
   
   
   
   
{ 
   
   
   
   
    int loop1 = 0, loop2 = 0, temp = 0, tempval = 0; 
   
   
   
   
     
   
   
   
   
    for(loop1 = 0; loop1 < length; ++loop1) 
   
   
   
   
    { 
   
   
   
   
        temp = loop1; 
   
   
   
   
        for(loop2 = loop1 + 1; loop2 < length; ++loop2) 
   
   
   
   
        { 
   
   
   
   
            if(iarr[loop2] < iarr[temp]) 
   
   
   
   
                temp = loop2; 
   
   
   
   
        } 
   
   
   
   
        if(temp != loop1) 
   
   
   
   
        { 
   
   
   
   
            tempval = iarr[temp]; 
   
   
   
   
            iarr[temp] = iarr[loop1]; 
   
   
   
   
            iarr[loop1] = tempval; 
   
   
   
   
        } 
   
   
   
   
    } 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
 
   
   
   
   
 
   
   
   
   
void Sift2(int iarr[], int low, int high) 
   
   
   
   
{ 
   
   
   
   
    int lowval = low, highval = high, temp = 0,  ivar1 = 0; 
   
   
   
   
     
   
   
   
   
    temp  = iarr[lowval]; 
   
   
   
   
    while(lowval <= highval)                             //         lowval <= highval，        lowval * 2 <= highval    ，             
   
   
   
   
    {        
   
   
   
   
        ivar1 = lowval * 2; 
   
   
   
   
        if(ivar1 > highval) break;                      //        
   
   
   
   
        if( ivar1 + 1 <= highval && iarr[ivar1] < iarr[ivar1 + 1]) 
   
   
   
   
            ++ivar1; 
   
   
   
   
        if(temp < iarr[ivar1]) 
   
   
   
   
        { 
   
   
   
   
            iarr[lowval] = iarr[ivar1]; 
   
   
   
   
            lowval = ivar1; 
   
   
   
   
        }else                
   
   
   
   
            break;       
   
   
   
   
    } 
   
   
   
   
    iarr[lowval] = temp; 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
void Sift3(int iarr[], int low, int high) 
   
   
   
   
{ 
   
   
   
   
    int lvar = 0, hvar = 0, tempvar = 0, temp = 0; 
   
   
   
   
 
   
   
   
   
    lvar = low, tempvar = lvar * 2;  hvar = high;  temp = iarr[low]; 
   
   
   
   
    while(tempvar <= hvar) 
   
   
   
   
    { 
   
   
   
   
        if(tempvar + 1 <= hvar && iarr[tempvar] < iarr[tempvar + 1]) 
   
   
   
   
            ++tempvar; 
   
   
   
   
        if(temp < iarr[tempvar]) 
   
   
   
   
        { 
   
   
   
   
            iarr[lvar] = iarr[tempvar]; 
   
   
   
   
            lvar = tempvar; 
   
   
   
   
            tempvar = lvar * 2; 
   
   
   
   
        }else break; 
   
   
   
   
    } 
   
   
   
   
    iarr[lvar] = temp; 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
void HeapSort22(int iarr[], int length) 
   
   
   
   
{ 
   
   
   
   
    int loop1 = 0, loop2 = 0, temp = 0; 
   
   
   
   
 
   
   
   
   
    for(loop1 = length / 2; loop1 > 0; --loop1) 
   
   
   
   
        Sift3(iarr, loop1, length); 
   
   
   
   
    for(loop1 = length; loop1 > 1; --loop1) 
   
   
   
   
    { 
   
   
   
   
        temp = iarr[loop1]; 
   
   
   
   
        iarr[loop1] = iarr[1]; 
   
   
   
   
        iarr[1] = temp; 
   
   
   
   
        Sift3(iarr, 1, loop1 - 1); 
   
   
   
   
    } 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
void BubbleSort2(int iarr[], int length) 
   
   
   
   
{ 
   
   
   
   
    int loop1 = 0, loop2 = 0, temp = 0, exchange = 0; 
   
   
   
   
 
   
   
   
   
    for(loop1 = 0; loop1 < length; ++loop1) 
   
   
   
   
    {   exchange = 0; 
   
   
   
   
        for(loop2 = length -1; loop2 > loop1; --loop2) 
   
   
   
   
        { 
   
   
   
   
            if(iarr[loop2] < iarr[loop2 - 1]) 
   
   
   
   
            { 
   
   
   
   
                temp = iarr[loop2]; 
   
   
   
   
                iarr[loop2] = iarr[loop2 - 1]; 
   
   
   
   
                iarr[loop2 -1] = temp; 
   
   
   
   
                exchange = 1; 
   
   
   
   
            } 
   
   
   
   
        } 
   
   
   
   
        if(exchange == 0) return; 
   
   
   
   
    } 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
void QuickSort22(int iarr[], int begin, int end) 
   
   
   
   
{ 
   
   
   
   
    int loop1 = 0, loop2 = 0, temp = 0; 
   
   
   
   
    temp = iarr[begin]; 
   
   
   
   
 
   
   
   
   
    loop1 = begin; loop2 = end; 
   
   
   
   
    if(begin >= end) return; 
   
   
   
   
    while(loop1 < loop2) 
   
   
   
   
    { 
   
   
   
   
        while(loop2 > loop1 && iarr[loop2] > temp) 
   
   
   
   
            --loop2; 
   
   
   
   
        if(loop2 > loop1) 
   
   
   
   
        { 
   
   
   
   
            iarr[loop1] = iarr[loop2]; 
   
   
   
   
            ++loop1; 
   
   
   
   
        } 
   
   
   
   
        while(loop1 < loop2 && iarr[loop1] < temp) 
   
   
   
   
            ++loop1; 
   
   
   
   
        if(loop1 < loop2) 
   
   
   
   
        { 
   
   
   
   
            iarr[loop2] = iarr[loop1]; 
   
   
   
   
            --loop2; 
   
   
   
   
        } 
   
   
   
   
    } 
   
   
   
   
    iarr[loop1] = temp; 
   
   
   
   
    QuickSort22(iarr, begin, loop1 -1); 
   
   
   
   
    QuickSort22(iarr, loop1 + 1,end); 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
 
   
   
   
   
 
   
   
   
   
void Merge2(int iarr[],int begin, int mid, int end) 
   
   
   
   
{ 
   
   
   
   
    int loop1 = begin, loop2 = mid + 1, temp = 0, index = 0; 
   
   
   
   
    int tempiarr[30]; 
   
   
   
   
 
   
   
   
   
    while(loop1 <= mid && loop2 <= end) 
   
   
   
   
    { 
   
   
   
   
        if(iarr[loop1] > iarr[loop2]) 
   
   
   
   
        { 
   
   
   
   
            tempiarr[index] = iarr[loop2]; 
   
   
   
   
            ++index;    ++loop2; 
   
   
   
   
        }else if(iarr[loop1] < iarr[loop2]) 
   
   
   
   
        { 
   
   
   
   
            tempiarr[index] = iarr[loop1]; 
   
   
   
   
            ++index;    ++loop1; 
   
   
   
   
        }else 
   
   
   
   
        { 
   
   
   
   
            tempiarr[index] = iarr[loop1]; 
   
   
   
   
            ++index;    ++loop1; 
   
   
   
   
            tempiarr[index] = iarr[loop2]; 
   
   
   
   
            ++index;    ++loop2; 
   
   
   
   
        } 
   
   
   
   
    } 
   
   
   
   
    while(loop1 <= mid) 
   
   
   
   
    { 
   
   
   
   
        tempiarr[index] = iarr[loop1]; 
   
   
   
   
        ++index;   ++loop1; 
   
   
   
   
    } 
   
   
   
   
    while(loop2 <= end) 
   
   
   
   
    { 
   
   
   
   
        tempiarr[index] = iarr[loop2]; 
   
   
   
   
        ++index;   ++loop2; 
   
   
   
   
    } 
   
   
   
   
    for(loop1 = 0; loop1 < index; ++loop1) 
   
   
   
   
        iarr[loop1] = tempiarr[loop1];       
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
void MergePass2(int iarr[], int len, int length) 
   
   
   
   
{ 
   
   
   
   
    int ivar = 0; 
   
   
   
   
    for(ivar = 0; ivar + len * 2 - 1 <= length; ivar = ivar + 2 * len) 
   
   
   
   
    { 
   
   
   
   
        Merge2(iarr, ivar, ivar + len - 1, ivar + 2 * len - 1); 
   
   
   
   
         
   
   
   
   
    } 
   
   
   
   
    if(ivar + len - 1 < length) 
   
   
   
   
    { 
   
   
   
   
        Merge2(iarr, ivar, ivar + len -1, length); 
   
   
   
   
    } 
   
   
   
   
} 
   
   
   
   
 
   
   
   
   
void MergeSort2(int iarr[], int length) 
   
   
   
   
{ 
   
   
   
   
    int len = 1; 
   
   
   
   
    for(len = 1; len <= length; len = 2 * len) 
   
   
   
   
    {   MergePass2(iarr, len, length );  } 
   
   
   
   
} 
  
  
  
  
 

   
   
   
   

    
    
    
    
void main() 
    
    
    
    
{ 
    
    
    
    
    Node *nodes = NULL; 
    
    
    
    
    int iarr[16] = {1,18,7,30,9,15,99,36,9,12,25,11,2,16,17,10}; 
    
    
    
    
    char carr[10][4] = {"123","345","568","126","455","987","356","678","387","438"}; 
    
    
    
    
//  Disp(iarr,6); 
    
    
    
    
//  InsertSort(iarr,6); 
    
    
    
    
//  ShellSort(iarr,6); 
    
    
    
    
     
    
    
    
    
/*  CreateList(nodes,iarr,6); 
    
    
    
    
    Disp(nodes);    
    
    
    
    
    InsertSort2(nodes); 
    
    
    
    
    Disp(nodes);*/ 
    
    
    
    
//  Disp(carr,10); 
    
    
    
    
//  SelectSort2(iarr,6); 
    
    
    
    
//  HeapSort2(iarr,7); 
    
    
    
    
//  BubbleSort(iarr,8); 
    
    
    
    
//  QuickSort(iarr,0,8); 
    
    
    
    
//  DBubble2 (iarr,10); 
    
    
    
    
//  QuickSort2(iarr,0,12); 
    
    
    
    
//  Partition(iarr,0,11);                   
    
    
    
    
//  MergeSort(iarr,14); 
    
    
    
    
//  RadixSort(carr,10,3); 
    
    
    
    
//  Disp(carr,10); 
    
    
    
    
      
    
    
    
    
  
    
    
    
    
//  cout<<"is small heap: "<<isSmallHeap(iarr,7)<<endl; 
    
    
    
    
 
    
    
    
    
    Disp2(iarr,16); 
    
    
    
    
//  InsertSort2(iarr,15); 
    
    
    
    
//  ShellSort2(iarr,15); 
    
    
    
    
//  SelectSort2(iarr,15); 
    
    
    
    
//  HeapSort22(iarr,14); 
    
    
    
    
//  BubbleSort2(iarr,15); 
    
    
    
    
//  QuickSort22(iarr, 0, 15); 
    
    
    
    
    MergeSort(iarr,15); 
    
    
    
    
  
    
    
    
    
    Disp2(iarr,16); 
    
    
    
    
}