алгоритм шеллсорта не работает
Я хотел реализовать сортировку оболочек самостоятельно, а не копировать их в сети. Буду признателен, если кто-нибудь поможет мне найти ошибку и улучшить мой глупый код. Я опишу код ниже.
#include <iostream>
#include <cmath>
using namespace std;
void swap(int p, int j, int *arr);
void shellSort(int arr[], int gap, int size);
int main() {
int array[] = {12, 2, 4, 23, 5, 1, 6, 8, 16, 64, 32, 7, 43, 243, 76};
int size = 15;
for (int i = 15; i >= 1; i /= 2) {
shellSort(array,i,size);
cout << i << endl;
}
print(array, 15);
// shellSortwhile(array, 15);
print(array, 15);
}
void shellSort(int arr[], int gap, int size) {
for (int i = 0; i < size; i += gap) {
if (arr[i] > arr[i + gap]) {
swap(i, i + gap, arr);
for(int j = i; j >= 0; j -= gap) {
if (arr[j] < arr[j - gap]) {
swap(j-gap, j, arr);
}
}
}
}
}
Мой вывод:
Now the array will be printed
2
4
5
6
7
7
8
1076814756
12
15
16
23
32
43
64
Решение
Вы читаете / пишете вне границ. i+gap 15 в вашей первой итерации. В вашем массиве всего 15 элементов, поэтому вы читаете один элемент за последним. Это самая распространенная ошибка в C, не расстраивайтесь!
Другие решения
#include <iostream>
#include <cmath>
using namespace std;
void swap(int p, int j, int* arr );
void shellSortwhile(int arr[], int size);
void shellSort(int arr[], int gap,int size);
void print(int* arr, int size);
int main() {
int array[]={12,2,4,23,5,1,6,8,16,64,32,7,43,243,76};
int size=15;
for (int i=size/2;i>=1;i/=2)#include <iostream>
#include <cmath>
using namespace std;
void swap(int p, int j, int* arr );
void shellSortwhile(int arr[], int size);
void shellSort(int arr[], int gap,int size);
void print(int* arr, int size);
int main() {
int array[]={12,2,4,23,5,1,6,8,16,64,32,7,43,243,76};
int size=15;
print(array,15);
for (int i=size/2;i>=1;i/=2)
{ shellSort(array,i,size);
cout<<i<<endl;
}
print(array,15);
// shellSortwhile(array,15);
}
void print(int* arr, int size)
{
cout<<"Now the array will be printed"<<endl;
for (int i=0;i<size;i++)
cout<<arr[i]<<endl;
}
void swap(int p, int j, int* arr )
{
int temp=arr[p];
arr[p]=arr[j];
arr[j]=temp;
}
void shellSortwhile(int arr[], int size) {
int i, j, gap, temp;
gap = size/2;
while(gap > 0) {
i = gap;
while(i < size) {
temp = arr[i];
for(j = i; (j >= gap) && (arr[j - gap] > temp); j -=gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
i++;
}
gap = gap / 2;
}
}void shellSort(int arr[], int gap,int size)
{
for (int i=0;i<size-(gap);i++)
{
if (arr[i]>arr[i+gap])
{
swap(i,i+gap,arr);
for(int j=i;j>=0+gap;j-=gap)
{if (arr[j]<arr[j-gap])
swap(j-gap,j,arr);
}
}
}
}
{ shellSort(array,i,size);
cout<<i<<endl;
}
print(array,15);
// shellSortwhile(array,15);
print(array,15);
}
void print(int* arr, int size)
{
cout<<"Now the array will be printed"<<endl;
for (int i=0;i<size;i++)
cout<<arr[i]<<endl;
}
void swap(int p, int j, int* arr )
{
int temp=arr[p];
arr[p]=arr[j];
arr[j]=temp;
}
void shellSortwhile(int arr[], int size) {
int i, j, gap, temp;
gap = size/2;
while(gap > 0) {
i = gap;
while(i < size) {
temp = arr[i];
for(j = i; (j >= gap) && (arr[j - gap] > temp); j -=gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
i++;
}
gap = gap / 2;
}
}void shellSort(int arr[], int gap,int size)
{
for (int i=0;i<size-(gap);i++)
{
if (arr[i]>arr[i+gap])
{
swap(i,i+gap,arr);
print(arr,size);
for(int j=i;j>=0+gap;j-=gap)
{if (arr[j]<arr[j-gap])
swap(j-gap,j,arr);
print(arr,size);
}
}
}
}