采用插入排序算法错误 - 阵列是不完全排序。 [英] Error using Insertion Sort algorithm - array is not sorted exactly.
本文介绍了采用插入排序算法错误 - 阵列是不完全排序。的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
下面是一些工作code，它实现了快速排序算法的使用插入排序数组大小 N'GT的修改版本; 8 。我的测试数组排序不完全正确，我想那一定是我的执行 Insertionsort 和插入的。
递归 Insertionsort 算法的一般形式是：
无效Insertionsort（INT S []，INT N）
{
如果（正→1）
Insertionsort（S，N-1）;
插入（S，N-1）;
}
无效插入（INT * S，INT K）
{
INT键= S [K]
INT J = K-1;
而（J＆GT; = 0＆功放;＆放大器; S [J] GT;密钥）
{
S [J + 1] = S [J]。
j--;
}
S [J + 1] =键;
}
下面是我的完整的工作code表示不排序很完全正确的：
的#include＆LT;的iostream＆GT;
＃包括＆LT;字符串＆GT;
＃包括＆LT; stdlib.h中＆GT;
使用名字空间std;
诠释比较= 0;
诠释compare_qs_m3_ins [12];
//函数原型
INT分区（INT * S，诠释L，诠释U）;
无效交换（INT名单[]，INT磷，INT Q）;
无效插入（INT S []，INT K）;
无效Insertionsort（INT S []，INT低，诠释喜）;
无效Quicksort_Insert_M3（INT S []，INT N，INT磷，INT读）;
诠释的main（）
{
函数srand（时间（NULL））;
//声明用于测试的所有阵列
INT S1_500 [500];
INT S2_500 [500];
INT S3_500 [500];
INT S1_300 [300];
INT S2_300 [300];
INT S3_300 [300];
INT S1_100 [100];
INT S2_100 [100];
INT S3_100 [100];
INT S1_8 [8];
INT S2_8 [8];
INT S3_8 [8];
//填充随机整数数组
的for（int i = 0; I＆LT; 500;我++）
{
S1_500 [I] =兰特（）％1000;
S2_500 [I] =兰特（）％1000;
S3_500 [I] =兰特（）％1000;
}
的for（int i = 0; I＆LT; 300;我++）
{
S1_300 [I] =兰特（）％1000;
S2_300 [I] =兰特（）％1000;
S3_300 [I] =兰特（）％1000;
}
的for（int i = 0; I＆LT; 100;我++）
{
S1_100 [I] =兰特（）％500;
S2_100 [I] =兰特（）％500;
S3_100 [I] =兰特（）％500;
}
的for（int i = 0; I＆LT; 8;我++）
{
S1_8 [I] =兰特（）％100;
S2_8 [I] =兰特（）％100;
S3_8 [I] =兰特（）％100;
}
Quicksort_Insert_M3（S1_500,500,0,499）;
compare_qs_m3_ins [0] =比较;
比较= 0;
Quicksort_Insert_M3（S2_500,500,0,499）;
compare_qs_m3_ins [1] =比较;
比较= 0;
Quicksort_Insert_M3（S3_500,500,0,499）;
compare_qs_m3_ins [2] =比较;
比较= 0;
Quicksort_Insert_M3（S1_300,300,0,299）;
compare_qs_m3_ins [3] =比较;
比较= 0;
Quicksort_Insert_M3（S2_300,300,0,299）;
compare_qs_m3_ins [4] =比较;
比较= 0;
Quicksort_Insert_M3（S3_300,300,0,299）;
compare_qs_m3_ins [5] =比较;
比较= 0;
Quicksort_Insert_M3（S1_100,100,0,99）;
compare_qs_m3_ins [6] =比较;
比较= 0;
Quicksort_Insert_M3（S2_100,100,0,99）;
compare_qs_m3_ins [7] =比较;
比较= 0;
Quicksort_Insert_M3（S3_100,100,0,99）;
compare_qs_m3_ins [8] =比较;
比较= 0;
Quicksort_Insert_M3（S1_8,8,0,7）;
compare_qs_m3_ins [9] =比较;
比较= 0;
Quicksort_Insert_M3（S2_8,8,0,7）;
compare_qs_m3_ins [10] =比较;
比较= 0;
Quicksort_Insert_M3（S3_8,8,0,7）;
compare_qs_m3_ins [11] =比较;
比较= 0;
//的for（int i = 0; I＆LT; 12;我++）
// cout的＆LT;＆LT; compare_qs_m3_ins [1] - ;＆其中; ENDL;
的for（int i = 0; I＆LT; 499;我++）
COUT＆LT;＆LT; S1_500 [1] - ;＆其中; ENDL;
}
INT分区（INT * S，诠释L，诠释U）
{
INT X = S [升];
诠释J = 1;
的for（int i = L + 1; I＆LT; = U;我++）
{
比较++;
如果（S [1] - ; x）的
{
J ++;
掉期（S [I]，S [J]）;
}
}
INT P = D];
交换（S [升]，S [P]）;
返回磷;
}
无效掉期（INT和放大器; VAL1，INT和放大器;将val2）
{
INT TEMP = VAL1;
VAL1 = val2的;
将val2 =温度;
}
无效交换（INT名单[]，INT磷，INT Q）
{
INT TEMP =列表[P]。
列表[P] =列表[Q]
列表[Q] =温度;
}
INT Sort3（INT名单[]，INT磷，INT读）
{
INT中位数=（P + R）/ 2;
比较++;
如果（名单[P]＆LT; =列表[位数]）
{
比较++;
如果（名单[位数]≥列表[R]）
{
比较++;
如果（名单[P]＆LT;列表[R]）
{
INT TEMP =列表[P]。
列表[P] =列表[R]。
列表[R] =列表[位数]
列表[位数] =气温;
}
其他
{
交换（列表，中位数，R）;
}
}
其他
;
}
其他
{
比较++;
如果（名单[P]＆GT;清单[R]）
{
比较++;
如果（名单[位数]其中，列表[R]）
{
INT TEMP =列表[P]。
列表[P] =列表[位数]
列表[位数] =列表[R]。
列表[R] =温度;
}
其他
{
交换（列表中，P，R）;
}
}
其他
{
交换（列表页，中位数）;
}
}
返回列表[R]。
}
无效插入（INT * S，INT K）
{
INT键= S [K]
INT J = K-1;
而（J＆GT; = 0＆功放;＆放大器; S [J] GT;密钥）
{
S [J + 1] = S [J]。
j--;
比较++;
}
比较++;
S [J + 1] =键;
}
无效Insertionsort（INT S []，INT低，诠释喜）
{
如果（（高至低）+ 1→1）
Insertionsort（S，低+ 1，喜）;
插入（S，高保真低）;
}
无效Quicksort_Insert_M3（INT S []，int的N，INT低，诠释喜）
{
如果（（高至低）＆LT; = 8）
Insertionsort（S，低，HI）;
其他
{
如果（低＆LT;喜）
{
如果（（低+ 1）==喜）
{
比较++;
如果（S [小]＆GT; S [喜]）
掉期（S [小]，S [喜]）;
}
其他
{
Sort3（S，低，HI）;
如果（（低+ 2）＆LT;喜）
{
掉期（S [低+ 1]，S [（低+ HI）/ 2]）;
INT Q =分区（S，低+ 1，HI-1）;
Quicksort_Insert_M3（S，N，低，Q-1）;
Quicksort_Insert_M3（S，N，Q + 1，喜）;
}
}
}
}
}
解决方案
应该升序李树斌数组元素进行排序的功能不会：
INT Sort3（INT名单[]，INT磷，INT读）
{
仅供 P + 2'调用; = R ，所以
INT值=（P + R）/ 2;
P＆LT;平均＆LT; - [R 在这里。让 A =列表[P] ， B =列表[位数] 和 C =列表[R] 。
比较++;
如果（名单[P]＆LT; =列表[位数]）
{
比较++;
如果（名单[位数]≥列表[R]）
{
比较++;
如果（名单[P]＆LT;列表[R]）
{
所以在这里，我们有 A＆LT; = B ， C＆LT; b 和 A＆LT; ç，以及 A＆LT; C＆LT; b
INT TEMP =列表[P]。
列表[P] =列表[R]。
列表[R] =列表[位数]
列表[位数] =气温;
但将它们放在顺序 C，A，B 。也许你打算使用如果（名单[R]＆LT;列表[P]）。有
}
其他
C＆LT; = A LT; = B
{
交换（列表，中位数，R）;
，以便安排他们为了 A，C，B 。
}
}
其他
;
}
其他
下面， B＆LT;一个。
{
比较++;
如果（名单[P]＆GT;清单[R]）
{
C＆LT;一个
比较++;
如果（名单[位数]其中，列表[R]）
{
然后 B＆LT; C＆LT;一个
INT TEMP =列表[P]。
列表[P] =列表[位数]
列表[位数] =列表[R]。
列表[R] =温度;
是啊，这是正确的。
}
其他
C＆LT; = B＆LT;一个
{
交换（列表中，P，R）;
}
Okedoke。
}
其他
{
B＆LT; A＆LT; = C
交换（列表页，中位数）;
好了。
}
}
返回列表[R]。
}
为什么这个函数返回任何东西？你不使用返回值呢。
Here is some working code that implements a modified version of the Quicksort algorithm that uses Insertion Sort for array size n > 8. My test array isn't sorting exactly right, and I think it must be with my implementation of Insertionsort and Insert.
The general form of the recursive Insertionsort algorithm is:
void Insertionsort(int S[], int n)
{
if(n>1)
Insertionsort(S,n-1);
Insert(S,n-1);
}
void Insert(int *S, int k)
{
int key = S[k];
int j = k-1;
while(j>=0 && S[j] > key)
{
S[j+1] = S[j];
j--;
}
S[j+1] = key;
}
Here is my complete working code that does not sort quite exactly right:
#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;
int comparisons = 0;
int compare_qs_m3_ins[12];
// Function prototypes
int partition(int *S,int l, int u);
void exchange(int list[], int p, int q);
void Insert(int S[], int k);
void Insertionsort(int S[], int low, int hi);
void Quicksort_Insert_M3(int S[], int n, int p, int r);
int main()
{
srand (time(NULL));
// Declare all arrays used for testing
int S1_500[500];
int S2_500[500];
int S3_500[500];
int S1_300[300];
int S2_300[300];
int S3_300[300];
int S1_100[100];
int S2_100[100];
int S3_100[100];
int S1_8[8];
int S2_8[8];
int S3_8[8];
// Fill arrays with random integers
for(int i=0; i<500; i++)
{
S1_500[i] = rand()%1000;
S2_500[i] = rand()%1000;
S3_500[i] = rand()%1000;
}
for(int i=0; i<300; i++)
{
S1_300[i] = rand()%1000;
S2_300[i] = rand()%1000;
S3_300[i] = rand()%1000;
}
for(int i=0; i<100; i++)
{
S1_100[i] = rand()%500;
S2_100[i] = rand()%500;
S3_100[i] = rand()%500;
}
for(int i=0; i<8; i++)
{
S1_8[i] = rand()%100;
S2_8[i] = rand()%100;
S3_8[i] = rand()%100;
}
Quicksort_Insert_M3(S1_500,500,0,499);
compare_qs_m3_ins[0] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S2_500,500,0,499);
compare_qs_m3_ins[1] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S3_500,500,0,499);
compare_qs_m3_ins[2] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S1_300,300,0,299);
compare_qs_m3_ins[3] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S2_300,300,0,299);
compare_qs_m3_ins[4] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S3_300,300,0,299);
compare_qs_m3_ins[5] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S1_100,100,0,99);
compare_qs_m3_ins[6] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S2_100,100,0,99);
compare_qs_m3_ins[7] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S3_100,100,0,99);
compare_qs_m3_ins[8] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S1_8,8,0,7);
compare_qs_m3_ins[9] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S2_8,8,0,7);
compare_qs_m3_ins[10] = comparisons;
comparisons = 0;
Quicksort_Insert_M3(S3_8,8,0,7);
compare_qs_m3_ins[11] = comparisons;
comparisons = 0;
//for(int i=0; i<12; i++)
//cout << compare_qs_m3_ins[i] << endl;
for(int i=0;i<499;i++)
cout << S1_500[i] << endl;
}
int partition(int *S,int l, int u)
{
int x = S[l];
int j = l;
for(int i=l+1; i<=u; i++)
{
comparisons++;
if(S[i] < x)
{
j++;
swap(S[i],S[j]);
}
}
int p = j;
swap(S[l],S[p]);
return p;
}
void swap(int &val1, int &val2)
{
int temp = val1;
val1 = val2;
val2 = temp;
}
void exchange(int list[], int p, int q)
{
int temp = list[p];
list[p] = list[q];
list[q] = temp;
}
int Sort3(int list[], int p, int r)
{
int median = (p + r) / 2;
comparisons++;
if(list[p] <= list[median])
{
comparisons++;
if(list[median]>list[r])
{
comparisons++;
if(list[p]<list[r])
{
int temp = list[p];
list[p] = list[r];
list[r] = list[median];
list[median] = temp;
}
else
{
exchange(list,median,r);
}
}
else
;
}
else
{
comparisons++;
if(list[p] > list[r])
{
comparisons++;
if(list[median] < list[r])
{
int temp = list[p];
list[p] = list[median];
list[median] = list[r];
list[r] = temp;
}
else
{
exchange(list,p,r);
}
}
else
{
exchange(list,p,median);
}
}
return list[r];
}
void Insert(int *S, int k)
{
int key = S[k];
int j = k-1;
while(j>=0 && S[j] > key)
{
S[j+1] = S[j];
j--;
comparisons++;
}
comparisons++;
S[j+1] = key;
}
void Insertionsort(int S[], int low, int hi)
{
if((hi-low)+1>1)
Insertionsort(S,low+1,hi);
Insert(S,hi-low);
}
void Quicksort_Insert_M3(int S[], int n, int low, int hi)
{
if((hi-low)<=8)
Insertionsort(S,low,hi);
else
{
if(low < hi)
{
if((low+1) == hi)
{
comparisons++;
if(S[low] > S[hi])
swap(S[low],S[hi]);
}
else
{
Sort3(S,low,hi);
if((low+2)<hi)
{
swap(S[low+1],S[(low+hi)/2]);
int q = partition(S, low+1, hi-1);
Quicksort_Insert_M3(S, n, low, q-1);
Quicksort_Insert_M3(S, n, q+1, hi);
}
}
}
}
}
解决方案
The function supposed to sort three array elements in ascending order doesn't:
int Sort3(int list[], int p, int r)
{
called only for p + 2 <= r, so
int median = (p + r) / 2;
p < median < r here. Let a = list[p], b = list[median] and c = list[r].
comparisons++;
if(list[p] <= list[median])
{
comparisons++;
if(list[median]>list[r])
{
comparisons++;
if(list[p]<list[r])
{
So here we have a <= b, c < b and a < c, together a < c < b
int temp = list[p];
list[p] = list[r];
list[r] = list[median];
list[median] = temp;
but you place them in order c, a, b. Probably you intended to use if (list[r] < list[p]) there.
}
else
c <= a <= b
{
exchange(list,median,r);
so that arranges them in order a, c, b.
}
}
else
;
}
else
Here, b < a.
{
comparisons++;
if(list[p] > list[r])
{
c < a
comparisons++;
if(list[median] < list[r])
{
Then b < c < a
int temp = list[p];
list[p] = list[median];
list[median] = list[r];
list[r] = temp;
Yup, that's correct.
}
else
c <= b < a
{
exchange(list,p,r);
}
Okedoke.
}
else
{
b < a <= c
exchange(list,p,median);
Okay.
}
}
return list[r];
}
Why does this function return anything? You don't use the return value anyway.
这篇关于采用插入排序算法错误 - 阵列是不完全排序。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
