那些有额外时间的人..排序问题 [英] Fot those with extra time.. sorting question
问题描述
运行它我在第一次运行时看到，当插入排序为ZERO时，冒泡和选择排序都有9
排序计数。有了一个排序列表，这个
对于所有人来说应该是零吗？
另外bsort和Ssort也有相同的排序计数......也不是他们
有所不同？
下面的源和数据文件。
谢谢
Trent
#include< iostream>
#include< fstream>
#include< iomanip>
using namespace std;
void bubbleSort（int * array，const int，int&）; //函数原型
void selectionSort（int *，const int，int&）;
void insertionSort（int *，const int，int&）;
void swap（int *，int *）;
void print（int * array，int size，int * bubbleSort，int * selectionSort，int
* insertionSort，int bcount，int scount，int icount）;
// print（& numArray，arraySize，& bsort，& ssort，& isort，
bsortCounter，sSortCounter，iSortCounter）;
ifstream inFile;
ofstream outFile;
int main（ ）
{
const int arraySize = 10;
int numArray [arraySize];
int bsort [arraySize];
int bsortCounter = 0;
int isort [arraySize];
int iSortCounter = 0;
int ssort [arraySize];
int sSortCounter = 0;
//每种排序需要数组和计数器（并行数组）
inFile.open（" input.txt"）; //打开输入文件
if（！inFile）
{
cerr<< 错误打开文件 <<结束;
系统（暂停）;
返回-1;
}
for（int i = 0; i< 5; i ++）
{
for（int j = 0; j< arraySize; j ++）
{
inFile> numArray [j];
bsort [j] = numArray [j];
isort [j] = numArray [j ];
ssort [j] = numArray [j];
}
cout<< endl;
bubbleSort（bsort，arraySize，bsortCounter）; //调用排序函数
selectionSort（ssort，arraySize，sSortCounter）;
insertionSort（isort，arraySize，iSortCounter）;
print（numArray，arraySize，bsort，ssort，isort，bsortCounter，sSortCounter，
iSortCounter）; \
}
cout<<结束;
系统（暂停）;
inFile.close（）; //关闭文件
outFile。 close（）;
返回0;
}
//下面的功能
void bubbleSort（int * array，const int size，int& count）
{
int i，pass;
for（pass = 0; pass< size - 1; pass ++）//通行证数量
count = count + 1;
for（ i = 0; i< size - 1; i ++）//一次传递
if（array [i] array [i + 1]）//一次比较
{
swap（array [i]，array [i + 1]）;
}
} //结束bubble sort函数
void selectionSort（int * array，const int size，int& count）
{
int i，j，tmp ;
for（i = 0; i< size - 1; i ++）
{
tmp = i;
count = count + 1;
for（j = i + 1; j< size; j ++）
if（array [j]< array [ tmp]）
tmp = j;
swap（array [i]，ar射线[TMP]）; //调用swap函数
}
} //选择排序函数结束
void insertionSort（int * array，const int size，int& count）
{
int tmp，i;
for（int j = 1; j< size; j ++ ）
{
tmp = array [j];
i = j-1;
while（array [array] i]> tmp&& i> = 0）
{
count = count +1;
array [i + 1 ] = array [i];
i - ;
}
array [i + 1] = tmp;
}
}
void print（int * array，int size，int * bubbleSort，int * selectionSort，int
* insertionSort ，int bcount，int scount，int icount）
{
cout<< "未排序列表冒泡排序选择排序插入
已排序 << endl;
for（int k = 0; k< size; k ++）
cout<< setw（15）<< array [k]<< setw（16）<< bubbleSort [k]<< setw（20）<<
selectionSort [k]<< setw（19）<< insertionSort [k]<< endl;
cout<< endl<< 数字： << setw（23）<< bcount<< setw（20）<< scount
<< setw（19）<< icount<< endl;
} //打印功能结束
void swap（int * element1，int * element2）
{
int tmp = * element1;
* element1 = * element2;
* element2 = tmp;
}
----------------------
数据输入文件
----------------------
231
678
850
999
1050
1222
1325
1444
1600
1900
1900
1600
1444
1325
1222
1050
999
850
678
231
231
1444
850
999
678
1222
1050
1325
1600
1900
1050
999
850
678
231
1222
1325
1444
1600
1900
231
850
999
1050
1222
1325
1444
1600
1900
678
哦..我忘了..结果有：
未排序列表冒泡排序选择排序插入排序
231 231 231 231
678 678 678 678
850 850 850
999 999 999 999
1050 1050 1050 1050
1222 1222 1222 1222
$ b $ 1325 1325 1325 1325
1444 1444 1444 1444
1600 1600 1600 1600
1900 19001900 1900
编号：9 9 0
未排序列表冒泡排序选择排序插入排序
1900 231 231 231
1600 678 678 678
1444 850 850 850
1325 999 999 999
1222 1050 1050 1050
1050 1222 1222 1222
999 1325 1325 1325
850 1444 1444 1444
678 1600 1600 1600
231 1900 1900 1900
编号：18 18 45
未排序列表泡泡排序选择排序插入排序
231 231 231 231
1444 678 678 678
850 850 850 850
999 999 999 999
678 1050 1050 1050
1222 1222 1222 1222
1050 1325 1325 1325
1325 1444 1444 1444
1600 1600 1600 1600
1900 1900 1900 1900
编号： 27 27 54
未排序列表冒泡排序选择排序插入排序
1050 231 231 231
999 678 678 678
850 850 850 850
678 999 999 999
231 1050 1050 1050
1222 1222 1222 1222
1325 1325 1325 1325
1444 1444 1444 1444
1600 1600 1600 1600
1900 1900 1900 1900
编号：36 36 64
未排序列表冒泡排序选择排序插入排序
231 231 231 231
850 678 678 678
999 850 850 850
$ b $ 1050 999 999 999
1222 1050 1050 1050
1325 1222 1222 1222
1444 1325 1325 1325
1600 1444 1444 1444
1900 1600 1600 1600
678 1900 1900 1900
：45 45 72
按任意键继续。 。 。
Trent写道：
运行这个我看到第一次运行时，泡泡和选择排序都有
9排序计数，而插入排序有零。有一个排序列表，应该
这对所有人来说都是零？
我猜你的ZERO意味着零？然后请停止尖叫。不。您的
算法仅对排序列表中的插入排序给出零。
此外，bsort和Ssort具有相同的排序计数还有......不会有什么价值？b $ b他们有点不同？
for（int i = 0; i< size-1; ++ i）{
count = count + 1;
}
应始终为计数提供相同的答案，只要大小保持相同的
。
请注意，不同排序算法的工作方式与该组不同。
下面的源和数据文件。
谢谢
Trent
#include< iostream>
#include< fstream>
#include< iomanip>
using namespace std;
void bubbleSort（int * array，const int ，int&）; //函数原型
void selectionSort（int *，const int，int&）;
void insertionSort（int *，const int，int&）;
void swap（int *，int *）;
std :: swap有什么问题？
void print（int * array， int size，int * bubbleSort，int * selectionSort，int
* insertionSort，int bcount，int scount，int icount）;
// print（& numArray，arraySize ，& bsort，& ssort，& isort，
bsortCounter，sSortCounter，iSortCounter）;
ifstream inFile;
ofstream outFile;
使这些全球化的任何特殊原因？
>
int main（）
{
const int arraySize = 10;
int numArray [arraySize];
int bsort [arraySize];
int bsortCounter = 0;
int isort [arraySize];
int iSortCounter = 0;
int ssort [arraySize];
int sSortCounter = 0;
//每种排序需要数组和计数器（并行数组）
inFile.open（" input.txt"）; //打开输入文件
if（！inFile）
{
cerr<< 错误打开文件 << endl;
system（暂停）;
我的计算机上没有暂停程序。发布到此列表时，请
不要依赖外部程序。
返回-1;
从main返回只有三个可移植值：
0，EXIT_SUCCESS或EXIT_FAILURE。
这两个名称是来自< cstdlib>的宏。每个其他值都有实现定义的结果。
}
for（int i = 0; i< 5; i ++）
{
for（int j = 0; j< arraySize; j ++）
{
inFile> numArray [j];
if（！（inFile> numArray [j]））{/ * handle * /}
即使你确实打开了文件，你知道它包含了你想要的东西，读它可能会失败。
bsort [j] = numArray [j];
isort [j] = numArray [j];
ssort [j] = numArray [j];
}
cout<< endl;
bubbleSort（bsort，arraySize，bsortCounter）; //调用排序函数
selectionSort（ssort，arraySize，sSortCounter）;
insertionSort（isort，arraySize，iSortCounter）;
print（numArray，arraySize，bsort，ssort，isort，bsortCounter，sSortCounter，
iSortCounter）; \
}
cout<<结束;
系统（暂停）;
inFile.close（）; //关闭文件
outFile。 close（）;
返回0;
}
//下面的功能
void bubbleSort（int * array，const int size，int& count）
{
int i，pass;
for（pass = 0; pass< size - 1; pass ++）//传递次数
count = count + 1;
a）为什么不计算++计数或计算++？
b）计数总是增加1倍。
>
for（i = 0; i< size - 1; i ++）//一次传递
通常，这将是
for（i = 0; i< size - （pass + 1）; i ++）
你应该找出原因。
if（array [i] array [i + 1]）//一个比较
{
swap（array [i]，array [i + 1]）;
这不可能调用你的交换函数。我的理论是，如果实际编译了这个实际编译，你就是调用std :: swap：允许使用标准头文件b / b
包含另一个，并且因为你说使用命名空间性病;"它可能实际上是_use_任何名称空间std的成员。你通常应该避免使用命名空间std;。
}
} //冒泡结束排序功能
void selectionSort（int * array，const int size，int& count）
{
int i，j，tmp;
for（i = 0; i< size - 1; i ++）
{
tmp = i;
count = count + 1;
for（j = i + 1; j< size; j ++）
if （array [j]< array [tmp]）
tmp = j;
swap（array [i]，array [tmp]）; // call swap funtion
}
我重复关于交换和计数的冒泡排序的评论。
} //选择排序函数结束
void insertionSort（int * array，const int size，int& count）
{
int tmp，i;
for（int j = 1; j< size; j ++）
{
tmp = array [j];
i = j-1;
while（array [i]> tmp&& i> = 0）
如果array [0]<这是未定义的行为。 TMP。这个：
while（i> = 0&& array [i]> tmp）
{
count = count +1;
这个计时是在内循环中完成的。你实际上是什么？
算什么？
array [i + 1] = array [i];
我 - ;
}
数组[i + 1] = tmp;
}
}
-
rbh
" Robert Bauck Hamar < ro ********** @ ifi.uio.nowrote in message
news：f6 ********** @ readme.uio.no .. 。
Trent写道：
>运行这个我在第一次运行时看到，泡沫和选择排序有9个排序计数，而插入排序有ZERO。有一个排序列表，这应该是所有人的零？
我猜你的ZERO意味着零？然后请停止尖叫。不。你的
算法只对排序列表中的插入排序给出零。
>另外bsort和Ssort具有相同的精确度排序计数也......不应该有点不同吗？
for（int i = 0; i< size-1; ++ i）{
count = count + 1;
}
应始终提供相同的答案，只要尺寸保持不变
相同。
请注意，这个
组的排序算法的工作方式不同。
但是，它们是用C ++编写的，并且理解它们在C ++中是如何工作的，因此可以在
上讨论主题
>
>下面的来源和数据文件。
谢谢
Trent
#include< iostream>
#include< fstream>
#include< iomanip>
使用命名空间std;
void bubbleSort（int * array，const int，int&）; //函数原型
void selectionSort（int *，const int，int&）;
void insertionSort（int *，const int，int&）;
void swap（int *， int *）;
std :: swap有什么问题？
不在规格中
> void print（int * array，int size，int * bubbleSort，int * selectionSort，int
* insertionSort，int bcount ，int scount，int icount）;
// print（& numArray，arraySize，& bsort，& ssort，& isort，
bsortCounter，sSortCounter，iSortCounter）;
ifstream inFile;
ofstream outFile;
使这些全球化的任何特殊原因？
>>
int main （）
const int arraySize = 10;
int numArray [arraySize];
int bsort [arraySize];
int bsortCounter = 0;
int isort [arraySize];
int iSortCounter = 0;
int ssort [arraySize];
int sSortCounter = 0;
//每个排序需要数组和计数器（并行数组）
inFile.open（" input.txt"）; //打开输入文件
if（！inFile）
{
cerr<< 错误打开文件 << endl;
系统（暂停）;
我的计算机上没有暂停程序。发布到此列表时，请
不要依赖外部程序。
你的意思是iostream是一个外部程序吗？
它是C ++库的一部分< iomanip>
>
>返回-1;
从main返回只有三个可移植值：
0，EXIT_SUCCESS或EXIT_FAILURE。
好的，我继续进行了研究。
这两个名称是来自< cstdlib>的宏。每个其他值都有实现定义的结果。
>对于（int i = 0; i< 5; i ++）
$（$ j = 0; j< arraySize; j ++）
$ {$}
inFile> numArray [j];
if（！（inFile> numArray [j]））{/ * handle * /}
即使你确实打开了文件，你知道它包含你想要的东西，读它可能会失败。
是的，但这是学习练习。我不打算制作商业
套餐。
随着我了解更多，我会很乐意添加更多东西。 :-)
> bsort [j] = numArray [j];
isort [j] = numArray [j];
ssort [j] = numArray [j];
}
cout<< endl;
bubbleSort（bsort，arraySize，bsortCounter）; //调用排序函数
selectionSort（ssort，arraySize，sSortCounter）;
insertionSort（isort，arraySize，iSortCounter）;
print（numArray，arraySize，bsort，ssort，isort，
bsortCounter，sSortCounter，
iSortCounter）; \
}
cout<< endl;
system（" pause"）;
inFile.close（）; //关闭文件
outFile.close（）;
返回0;
}
//下面的功能
/> {
int i，pass;
for（pass = 0; pass< size - 1; pass ++）// pass of pass
count = count + 1;
a）为什么不计算++计数或计算++？
b）计数总是增加1倍。
我无论如何都能做到这一点..这是一个学习练习，但我可以实现它的b $ b。
>
>>
for（i = 0; i< size - 1; i ++）//一次传递
通常，这将是
for（i = 0; i< size - （pass + 1）; i ++）
You应该找出原因。
其实我从Deitel& amp;中抓住了一个例子。 DeitelC ++如何编程
第二版。
实际上我的所有种类都应该是这样，但我没时间尝试和
算出psuedo代码。
冒泡排序：
排序=假
排序做好
排序=真
我= 1到N-1做
如果A [i] A [I + 1]那么
掉期（A [i]，A [I + 1]）
排序=假
插入排序：
我= 2到N做
J =我
完成=错误
虽然J> = 2但未完成
如果A [J-1] A [J]那么
掉期（A [J]，A [J-1]）
否则
完成=真
J = J-1
选择排序：
我= 1到N-1做
最小= A [i]
位置= I
对于J = I + 1到N做
如果A [J]< ;最小的
最小= A [J]
位置= J
掉期（A [i]，A [位置]）
>
> if（array [i] array [i + 1]）//一个比较
swap（array [i]，array [i + 1]）;
这不可能调用你的交换函数。我的理论是，如果实际编译了这个实际编译，你就是调用std :: swap：允许使用标准头文件b / b
包含另一个，并且因为你说使用命名空间性病;"它可能实际上是_use_任何名称空间std的成员。您通常应该避免使用命名空间std;"
。
它确实......冒泡排序和交换来自同一个例子。
实际上我正在调用函数交换在程序结束时，
正确吗？
>
> //
} //结束泡泡排序功能
void selectionSort（int * array，const int size，int& count）
{
int i，j，tmp;
for（i = 0; i< size - 1; i ++）
{
tmp = i;
count = count + 1;
for（j = i + 1; j< size; j ++）
if（array [j]< array [tmp]）
tmp = j;
swap（array [i]，array [tmp]）; // call swap funtion
}
我重复关于swap和count的冒泡排序的评论。
好的，但似乎对我有用。
>
>} //选择排序函数结束
void insertionSort（int * array，const int size，int& count）
{int / t int，i;
for（int j = 1; j< size; j ++）
{
tmp = array [j];
i = j-1;
while（array [i]> tmp&& i> = 0）
这是未定义的行为，如果array [0]< TMP。这个：
while（i> = 0&& array [i]> tmp）
我这样做了，结果仍然是一样的。
> {
count = count +1;
这个计时是在内循环中完成的。你实际上是什么？
算什么？
我试图计算排序数组所需的实际排序数量。
> array [i + 1] = array [i];
i--;
}
array [i + 1] = tmp;
}
}
感谢您的输入
-
rbh
Running this I see that on first run, both bubble and selection sort have 9
sort counts while insertion sort has ZERO. With a sorted list, should this
be ZERO for all?
Also bsort and Ssort have the same exact sorting counts also..shouldn''t they
differ somewhat?
Source and data file below.
Thanks
Trent
#include <iostream>
#include <fstream>
#include<iomanip>
using namespace std;
void bubbleSort(int *array, const int, int &); //function prototypes
void selectionSort(int *, const int, int &);
void insertionSort(int *, const int, int &);
void swap(int *, int *);
void print(int *array, int size, int *bubbleSort, int *selectionSort, int
*insertionSort, int bcount, int scount, int icount);
// print(&numArray, arraySize, &bsort, &ssort, &isort,
bsortCounter,sSortCounter, iSortCounter);
ifstream inFile;
ofstream outFile;
int main()
{
const int arraySize = 10;
int numArray[arraySize];
int bsort[arraySize];
int bsortCounter =0;
int isort[arraySize];
int iSortCounter =0;
int ssort[arraySize];
int sSortCounter =0;
// each sort needs array and counter (parallel arrays)
inFile.open("input.txt"); //opening input file
if (!inFile)
{
cerr << "Error Opening File" << endl;
system("pause");
return -1;
}
for (int i =0;i < 5;i++)
{
for (int j=0; j< arraySize;j++)
{
inFile >numArray[j];
bsort[j]=numArray[j];
isort[j]=numArray[j];
ssort[j]=numArray[j];
}
cout << endl;
bubbleSort(bsort, arraySize, bsortCounter);// call the sort functions
selectionSort(ssort, arraySize,sSortCounter);
insertionSort(isort, arraySize,iSortCounter);
print(numArray, arraySize, bsort, ssort, isort, bsortCounter,sSortCounter,
iSortCounter);\
}
cout << endl;
system("pause");
inFile.close();// close files
outFile.close();
return 0;
}
// Funtions below
void bubbleSort(int *array, const int size, int &count)
{
int i, pass;
for (pass =0; pass < size - 1; pass++) //# of passes
count= count+1;
for (i= 0; i < size - 1; i++) // one pass
if (array[i] array[i+1]) //one comparison
{
swap(array[i], array[i+1]);
}
}// end of bubble Sort function
void selectionSort(int *array, const int size, int &count)
{
int i, j, tmp;
for (i = 0; i < size - 1; i++)
{
tmp = i;
count = count + 1;
for (j = i+1; j < size; j++)
if (array[j] < array[tmp])
tmp = j;
swap(array[i], array[tmp]); //call swap funtion
}
}//end of selection sort function
void insertionSort(int *array,const int size, int &count)
{
int tmp,i;
for(int j=1;j<size;j++)
{
tmp=array[j];
i=j-1;
while(array[i]>tmp && i>=0)
{
count = count +1;
array[i+1]=array[i];
i--;
}
array[i+1]=tmp;
}
}
void print(int *array, int size, int *bubbleSort, int *selectionSort, int
*insertionSort, int bcount, int scount, int icount)
{
cout << " Unsorted List Bubble Sorted Selection Sorted Insertion
Sorted" << endl;
for (int k =0;k < size;k++)
cout << setw(15) <<array[k] << setw(16) << bubbleSort[k] << setw(20) <<
selectionSort[k] << setw(19) << insertionSort[k] << endl;
cout << endl << "Number: " << setw(23) <<bcount << setw(20)<<scount
<<setw(19)<< icount << endl;
}// end of print function
void swap(int *element1, int *element2)
{
int tmp = *element1;
*element1 = *element2;
*element2 = tmp;
}
----------------------
Data Input File
----------------------
231
678
850
999
1050
1222
1325
1444
1600
1900
1900
1600
1444
1325
1222
1050
999
850
678
231
231
1444
850
999
678
1222
1050
1325
1600
1900
1050
999
850
678
231
1222
1325
1444
1600
1900
231
850
999
1050
1222
1325
1444
1600
1900
678
Oh..I forgot..here are the results:
Unsorted List Bubble Sorted Selection Sorted Insertion Sorted
231 231 231 231
678 678 678 678
850 850 850 850
999 999 999 999
1050 1050 1050 1050
1222 1222 1222 1222
1325 1325 1325 1325
1444 1444 1444 1444
1600 1600 1600 1600
1900 1900 1900 1900
Number: 9 9 0
Unsorted List Bubble Sorted Selection Sorted Insertion Sorted
1900 231 231 231
1600 678 678 678
1444 850 850 850
1325 999 999 999
1222 1050 1050 1050
1050 1222 1222 1222
999 1325 1325 1325
850 1444 1444 1444
678 1600 1600 1600
231 1900 1900 1900
Number: 18 18 45
Unsorted List Bubble Sorted Selection Sorted Insertion Sorted
231 231 231 231
1444 678 678 678
850 850 850 850
999 999 999 999
678 1050 1050 1050
1222 1222 1222 1222
1050 1325 1325 1325
1325 1444 1444 1444
1600 1600 1600 1600
1900 1900 1900 1900
Number: 27 27 54
Unsorted List Bubble Sorted Selection Sorted Insertion Sorted
1050 231 231 231
999 678 678 678
850 850 850 850
678 999 999 999
231 1050 1050 1050
1222 1222 1222 1222
1325 1325 1325 1325
1444 1444 1444 1444
1600 1600 1600 1600
1900 1900 1900 1900
Number: 36 36 64
Unsorted List Bubble Sorted Selection Sorted Insertion Sorted
231 231 231 231
850 678 678 678
999 850 850 850
1050 999 999 999
1222 1050 1050 1050
1325 1222 1222 1222
1444 1325 1325 1325
1600 1444 1444 1444
1900 1600 1600 1600
678 1900 1900 1900
Number: 45 45 72
Press any key to continue . . .
Trent wrote:
Running this I see that on first run, both bubble and selection sort have
9 sort counts while insertion sort has ZERO. With a sorted list, should
this be ZERO for all?I guess you by ZERO mean zero? Then please stop screaming. No. Your
algorithms only give zero for the insertion sort on a sorted list.
Also bsort and Ssort have the same exact sorting counts also..shouldn''t
they differ somewhat?for (int i = 0; i < size-1; ++i) {
count = count + 1;
}
should always provide the same answer for count as long as size remains the
same.
Note that how different sorting algorithms work is off topic on this group.
Source and data file below.
Thanks
Trent
#include <iostream>
#include <fstream>
#include<iomanip>
using namespace std;
void bubbleSort(int *array, const int, int &); //function prototypes
void selectionSort(int *, const int, int &);
void insertionSort(int *, const int, int &);
void swap(int *, int *);What''s wrong with std::swap?
void print(int *array, int size, int *bubbleSort, int *selectionSort, int
*insertionSort, int bcount, int scount, int icount);
// print(&numArray, arraySize, &bsort, &ssort, &isort,
bsortCounter,sSortCounter, iSortCounter);
ifstream inFile;
ofstream outFile;Any particular reason for making these global?
>
int main()
{
const int arraySize = 10;
int numArray[arraySize];
int bsort[arraySize];
int bsortCounter =0;
int isort[arraySize];
int iSortCounter =0;
int ssort[arraySize];
int sSortCounter =0;
// each sort needs array and counter (parallel arrays)
inFile.open("input.txt"); //opening input file
if (!inFile)
{
cerr << "Error Opening File" << endl;
system("pause");I have no pause program on my computer. When posting to this list, please
don''t rely upon external programs.
return -1;There are only three portable values to return from main:
0, EXIT_SUCCESS, or EXIT_FAILURE.
The two names are macros from <cstdlib>. Every other value has
implementation-defined results.
}
for (int i =0;i < 5;i++)
{
for (int j=0; j< arraySize;j++)
{
inFile >numArray[j];if (!(inFile >numArray[j])) { /*handle*/ }
Even if you did open the file, and you _know_ that it contains what you
want, reading it might fail.
bsort[j]=numArray[j];
isort[j]=numArray[j];
ssort[j]=numArray[j];
}
cout << endl;
bubbleSort(bsort, arraySize, bsortCounter);// call the sort functions
selectionSort(ssort, arraySize,sSortCounter);
insertionSort(isort, arraySize,iSortCounter);
print(numArray, arraySize, bsort, ssort, isort, bsortCounter,sSortCounter,
iSortCounter);\
}
cout << endl;
system("pause");
inFile.close();// close files
outFile.close();
return 0;
}
// Funtions below
void bubbleSort(int *array, const int size, int &count)
{
int i, pass;
for (pass =0; pass < size - 1; pass++) //# of passes
count= count+1;a) why not ++count or count++?
b) count is always incremented size-1 times.
>
for (i= 0; i < size - 1; i++) // one passUsually, this would be
for (i = 0; i < size - (pass + 1); i++)
You should find out why.
if (array[i] array[i+1]) //one comparison
{
swap(array[i], array[i+1]);This cannot possibly call your swap function. My theory is that if this
actually compiled, you are calling std::swap: A standard header is allowed
to include another, and since you said "using namespace std;" it might
actually _use_ any member of namespace std. You should generally
avoid "using namespace std;".
}
}// end of bubble Sort function
void selectionSort(int *array, const int size, int &count)
{
int i, j, tmp;
for (i = 0; i < size - 1; i++)
{
tmp = i;
count = count + 1;
for (j = i+1; j < size; j++)
if (array[j] < array[tmp])
tmp = j;
swap(array[i], array[tmp]); //call swap funtion
}I repeat the remarks from bubble sort about swap and count.
}//end of selection sort function
void insertionSort(int *array,const int size, int &count)
{
int tmp,i;
for(int j=1;j<size;j++)
{
tmp=array[j];
i=j-1;
while(array[i]>tmp && i>=0)This is undefined behaviour if array[0] < tmp. Make this:
while (i>=0 && array[i]>tmp)
{
count = count +1;This time counting is done in the inner loop. What are you actually
counting?
array[i+1]=array[i];
i--;
}
array[i+1]=tmp;
}
}--
rbh
"Robert Bauck Hamar" <ro**********@ifi.uio.nowrote in message
news:f6**********@readme.uio.no...Trent wrote:
>Running this I see that on first run, both bubble and selection sort have
9 sort counts while insertion sort has ZERO. With a sorted list, should
this be ZERO for all?
I guess you by ZERO mean zero? Then please stop screaming. No. Your
algorithms only give zero for the insertion sort on a sorted list.
>Also bsort and Ssort have the same exact sorting counts also..shouldn''t
they differ somewhat?
for (int i = 0; i < size-1; ++i) {
count = count + 1;
}
should always provide the same answer for count as long as size remains
the
same.
Note that how different sorting algorithms work is off topic on this
group.But, they are written in C++, and understanding how they work in C++,
therefore on topic
>>Source and data file below.
Thanks
Trent
#include <iostream>
#include <fstream>
#include<iomanip>
using namespace std;
void bubbleSort(int *array, const int, int &); //function prototypes
void selectionSort(int *, const int, int &);
void insertionSort(int *, const int, int &);
void swap(int *, int *);
What''s wrong with std::swap?
Not in specifications
>void print(int *array, int size, int *bubbleSort, int *selectionSort, int
*insertionSort, int bcount, int scount, int icount);
// print(&numArray, arraySize, &bsort, &ssort, &isort,
bsortCounter,sSortCounter, iSortCounter);
ifstream inFile;
ofstream outFile;
Any particular reason for making these global?
>>
int main()
{
const int arraySize = 10;
int numArray[arraySize];
int bsort[arraySize];
int bsortCounter =0;
int isort[arraySize];
int iSortCounter =0;
int ssort[arraySize];
int sSortCounter =0;
// each sort needs array and counter (parallel arrays)
inFile.open("input.txt"); //opening input file
if (!inFile)
{
cerr << "Error Opening File" << endl;
system("pause");
I have no pause program on my computer. When posting to this list, please
don''t rely upon external programs.
You mean like iostream is an external program?
It''s part of the C++ library <iomanip>
>> return -1;
There are only three portable values to return from main:
0, EXIT_SUCCESS, or EXIT_FAILURE.
Okay I went ahead and inplmented that.
The two names are macros from <cstdlib>. Every other value has
implementation-defined results.
> }
for (int i =0;i < 5;i++)
{
for (int j=0; j< arraySize;j++)
{
inFile >numArray[j];
if (!(inFile >numArray[j])) { /*handle*/ }
Even if you did open the file, and you _know_ that it contains what you
want, reading it might fail.
Yes, but this is a learning excercise. I am not trying to make a commercial
package.
As I learn more I will be glad to add more stuff. :-)
> bsort[j]=numArray[j];
isort[j]=numArray[j];
ssort[j]=numArray[j];
}
cout << endl;
bubbleSort(bsort, arraySize, bsortCounter);// call the sort functions
selectionSort(ssort, arraySize,sSortCounter);
insertionSort(isort, arraySize,iSortCounter);
print(numArray, arraySize, bsort, ssort, isort,
bsortCounter,sSortCounter,
iSortCounter);\
}
cout << endl;
system("pause");
inFile.close();// close files
outFile.close();
return 0;
}
// Funtions below
void bubbleSort(int *array, const int size, int &count)
{
int i, pass;
for (pass =0; pass < size - 1; pass++) //# of passes
count= count+1;
a) why not ++count or count++?
b) count is always incremented size-1 times.I can do it anyway..again this is a learning exercise, but I can implement
it.>>>
for (i= 0; i < size - 1; i++) // one pass
Usually, this would be
for (i = 0; i < size - (pass + 1); i++)
You should find out why.
Actually I grabbed an example from the Deitel & Deitel "C++ How to Program"
Second Ed.
In reality all my sorts should be like this, but I am out of time to try and
figure the psuedo code out.
Bubble Sort:
Sorted = False
While not Sorted do
Sorted = True
For I = 1 to N-1 do
If A[i] A[I+1] then
Swap(A[i], A[I+1])
Sorted = False
Insertion Sort:
For I = 2 to N do
J = I
Done = False
While J >= 2 and not Done
If A[J-1] A[J] Then
Swap(A[J], A[J-1])
Else
Done = True
J=J-1
Selection Sort:
For I = 1 to N-1 do
Smallest = A[i]
Location = I
For J=I+1 to N do
If A[J] < Smallest then
Smallest = A[J]
Location = J
Swap(A[i], A[Location])
>> if (array[i] array[i+1]) //one comparison
{
swap(array[i], array[i+1]);
This cannot possibly call your swap function. My theory is that if this
actually compiled, you are calling std::swap: A standard header is allowed
to include another, and since you said "using namespace std;" it might
actually _use_ any member of namespace std. You should generally
avoid "using namespace std;".It does...The bubble sort and the swap came from the same example.
Actually I am calling the function swap that is at the end of the program,
correct?>> }
}// end of bubble Sort function
void selectionSort(int *array, const int size, int &count)
{
int i, j, tmp;
for (i = 0; i < size - 1; i++)
{
tmp = i;
count = count + 1;
for (j = i+1; j < size; j++)
if (array[j] < array[tmp])
tmp = j;
swap(array[i], array[tmp]); //call swap funtion
}
I repeat the remarks from bubble sort about swap and count.Okay, but seems to be functioning to me.
>>}//end of selection sort function
void insertionSort(int *array,const int size, int &count)
{
int tmp,i;
for(int j=1;j<size;j++)
{
tmp=array[j];
i=j-1;
while(array[i]>tmp && i>=0)
This is undefined behaviour if array[0] < tmp. Make this:
while (i>=0 && array[i]>tmp)
I did that and results are still the same.
> {
count = count +1;
This time counting is done in the inner loop. What are you actually
counting?
I am trying to count the actual amount of sorts it takes to sort the array.
> array[i+1]=array[i];
i--;
}
array[i+1]=tmp;
}
}
Thanks for the input
--
rbh
这篇关于那些有额外时间的人..排序问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
