0

配列を取得し、1000 個の乱数を入力してから、配列を 2 番目の配列にコピーする必要がある並べ替えプログラムを作成しています。その後、プログラムは selectionSort 関数と insertSort 関数を使用することになっています。

しかし、関数を使用するときは、すべてのスワップとキー比較を追跡する必要があります。私はinsertSortのためにそれを行う方法を考え出しました。selectionSort でこれを行う方法がわかりません

これが私のコードです：

 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 のスワップと比較が出力されますが、ソート アルゴリズムが for ループで他の関数を呼び出すため、selectionSort で動作させる方法に慣れていません。任意の入力をいただければ幸いです。

4

1 に答える 1

2

実際には、選択ソートには固定(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
   }   
   ..
 }

ちなみに、挿入ソートでの比較のカウントも完全ではありません。

for (int firstOutOfOrder = 1; firstOutOfOrder < length; firstOutOfOrder++)
{    
   // You miss the count here.
   if (list[firstOutOfOrder] < list[firstOutOfOrder - 1])
于 2012-10-24T00:32:30.843 に答える