Ошибка при использовании алгоритма сортировки вставкой — массив не отсортирован точно.
Вот некоторый рабочий код, который реализует модифицированную версию алгоритма быстрой сортировки, которая использует сортировку вставкой для размера массива n > 8, Мой тестовый массив не сортируется правильно, и я думаю, что это должно быть с моей реализацией Insertionsort а также Insert,
Общая форма рекурсивного Insertionsort Алгоритм является:
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;
}
Вот мой полный рабочий код, который не совсем правильно сортируется:
#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);
}
}
}
}
}
Решение
Функция, которая должна сортировать три элемента массива в порядке возрастания, не выполняет:
int Sort3(int list[], int p, int r)
{
называется только для p + 2 <= r, так
int median = (p + r) / 2;
p < median < r Вот. Позволять a = list[p], b = list[median] а также c = list[r],
comparisons++;
if(list[p] <= list[median])
{
comparisons++;
if(list[median]>list[r])
{
comparisons++;
if(list[p]<list[r])
{
Итак, у нас есть a <= b, c < b а также a < c, все вместе a < c < b
int temp = list[p];
list[p] = list[r];
list[r] = list[median];
list[median] = temp;
но вы размещаете их в порядке c, a, b, Возможно, вы намеревались использовать if (list[r] < list[p]) там.
}
else
c <= a <= b
{
exchange(list,median,r);
так что расставляем их по порядку a, c, b,
}
}
else
;
}
else
Вот, b < a,
{
comparisons++;
if(list[p] > list[r])
{
c < a
comparisons++;
if(list[median] < list[r])
{
затем b < c < a
int temp = list[p];
list[p] = list[median];
list[median] = list[r];
list[r] = temp;
Да, это правильно.
}
else
c <= b < a
{
exchange(list,p,r);
}
Okedoke.
}
else
{
b < a <= c
exchange(list,p,median);
Хорошо.
}
}return list[r];
}
Почему эта функция возвращает что-нибудь? Вы не используете возвращаемое значение в любом случае.
Другие решения
«Общая форма рекурсивного алгоритма вставки:» — если вам нужен хед-рекурсивный алгоритм, да, в противном случае лучшей версией будет:
void Insertionsort(int S[], int i, int n)
{
Insert(S, i, n);
if(i < n)
Insertionsort(S, i+1, n);
}
что гораздо понятнее. Кроме того, вы могли бы также поместить тело Insert в Insertionsort.
Я не собираюсь выяснять вашу слишком сложную версию быстрой сортировки. Приличная быстрая сортировка составляет около 20 строк или менее (например, www.algolist.net/Algorithms/Sorting/Quicksort) (и добавьте еще 10 или менее для вставки сортировки). Я предлагаю получить лучшее понимание, посмотрев на другую реализацию и переписав вашу.
Я считаю, что это можно было бы попросить как продолжение вашего предыдущий вопрос.