记录掉期和比较

Question

我在写一个排序程序，需要一个数组，填充1000个随机数，然后将数组复制到第二个数组中。之后，该程序应该使用selectionSort函数和insertSort函数。

但是当我使用函数时，我应该跟踪所有的交换和关键比较。我已经想出了如何为insertSort做到这一点。我无法弄清楚如何为选择排序

这里做，这是我的代码：

template <class elemType> 
void selectionSort(elemType list[], int length) 
{ 
    int loc, minIndex; 
int swaps =0; 

    for (loc = 0; loc < length; loc++) 
    { 
    minIndex = minLocation(list, loc, length - 1); 

    swap(list, loc, minIndex); 

    } 
cout<<"swaps = "<<swaps<<endl; 
    } //end selectionSort 

template <class elemType> 
void swap(elemType list[], int first, int second) 
{ 
elemType temp; 
    temp = list[first]; 
    list[first] = list[second]; 
    list[second] = temp; 
    } //end swap 

template <class elemType> 
int minLocation(elemType list[], int first, int last) 
{ 
    int loc, minIndex;  
    minIndex = first; 

    for (loc = first + 1; loc <= last; loc++) 
    { if (list[loc] < list[minIndex]) 
     minIndex = loc; 

} 

    return minIndex; 
    } //end minLocation 

    template <class elemType> 
    void insertionSort(elemType list[], int length) 
    { 
int swaps = 0; 
int comp = 0; 

    for (int firstOutOfOrder = 1; firstOutOfOrder < length; 
          firstOutOfOrder++) 
    if (list[firstOutOfOrder] < list[firstOutOfOrder - 1]) 
    { 
     elemType temp = list[firstOutOfOrder]; 
     int location = firstOutOfOrder; 

     do 
     { 
      list[location] = list[location - 1]; 
      location--; 
      comp +=1; 
     } while(location > 0 && list[location - 1] > temp); 

     list[location] = temp; 
     swaps +=1; 
    } 

cout<<"swaps = "<<swaps<<endl; 
cout<<"comps = "<<comp<<endl; 
    } //end insertionSort 

#include<iostream> 
#include <ctime> 
#include <cstdlib> 
#include "searchSortAlgorithms.h" 

using namespace std; 

int main(){ 
//generate a new random set each time 

srand(time(0)); 

int a[1000] = {0}; 
int b[1000] = {0}; 

for(int i= 0; i<1000; i++) 
{ 
    a[i] = rand()% 1000; 
    b[i] = a[i]; 
} 


insertionSort(a, 1000); 
selectionSort(b, 1000); 

    return 0; 
} 

的互换和比较打印出的inertionSort，但我不熟悉我将如何得到它一起工作selectionSort自排序算法调用for循环中的其他函数。 任何输入将不胜感激。

Answer 1

其实，您的选择种类有一个固定数量的比较(length * (length-1)/2)和交换(length)。

。如果你想算来，

// Count variables can be defined in main(), and passed through 
// to swap(), minLocation(). 
template <class elemType> 
void swap(elemType list[], int first, int second) 
{ 
    // Count swap here 
} 

template <class elemType> 
int minLocation(elemType list[], int first, int last) 
{ 
    .. 
    for (loc = first + 1; loc <= last; loc++) 
    { 
     // Count comparation here 
    } 
    .. 
} 

顺便说一句，你在插入排序comparations的计数是不完整的要么。

for (int firstOutOfOrder = 1; firstOutOfOrder < length; firstOutOfOrder++) 
{  
    // You miss the count here. 
    if (list[firstOutOfOrder] < list[firstOutOfOrder - 1])