Ad:

C++ Discussion Thread
Unsolved
Views: 3704

Apr 5th, 2006

Shell Sort w/ fibonacci numbers...HELP!!! Due Friday

Expand Post »

Hey ya'll, I am working on this assignment that has me that is as follows:

/*
Modify the following shell sort to use the fibonacci sequence, instead of
the sequence h = 3h+1.

Hint use dynamic programming to do this.

*/

#include <iostream>
using namespace std;
#include <stdlib.h>
#include <fstream>
#include <string>
#include <time.h>

long comparisons = 0;
long exchanges = 0;
ofstream fout("output.txt");

void ran(int a[], int N)
{
int i;
srand((unsigned)time(NULL)); //Give us a random array that will be fixed for all sorts
for(i = 0; i<N; i++)
a[i] = int(1000*(1.0*rand()/RAND_MAX));
}

void initial(int a[], int b[], int N)
{
int i;
for(i =0 ; i < N; i++) a[i] = b[i];
}

void output( int a[], int l, int r)
{
int i;
for( i = l; i <= r; i++) fout << a[i] << " ";
fout << endl;
}
void shellsort(int a[], int l, int r)
{
int i,j,h, v;
// for(h = 1; h <= (r)/9; h = 3*h+1);
// for( ; h>0; h/=3)
// for(i = l+h; i <= r; i++)
{
j =i;
v = a[i];
while(j >= l+h && v < a[j-h])
{
a[j] = a[j-h];
j -= h;
}
a[j] = v;
}

}
int main(int argc, char *argv[])
{
int i, N = atoi(argv[1]), sw = atoi(argv[2]);
int *a = new int[N], *b = new int[N];
string filename;
int choice = 0;
if(sw)
ran(a, N);
else
{
cout << "enter file name" << endl;
cin >> filename;
ifstream fin(filename.c_str());
for(i = 0; i < N; i++) fin >> a[i];
}
for( i = 0; i < N; i++)
{
fout << a[i] << " ";
}
fout << endl;
shellsort(a, 0 , N-1);
fout << "Shell Sort " << endl;
output(a, 0, N-1);
return 0;
}

Any Help would be greatly appreciated. I know how the fibonacci sequence works, but I do not know how to add it to this program.

Similar Threads

Help,Fibonacci numbers in VB.NET
Sort algorithm! in C

darylesha

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

4 posts
since Apr 2006

Permalink

Apr 5th, 2006

Re: Shell Sort w/ fibonacci numbers...HELP!!! Due Friday

hmmm,

Perhaps this link may answer your question. Not sure though.

http://www.answers.com/topic/shell-sort

C++ Syntax (Toggle Plain Text)
/**
 * Performs an insertion sort on elements of a[] with the given gap.
 * If gap == 1, performs an ordinary insertion sort.
 * If gap >= length, does nothing.
 * Based on a C implementation from the article Insertion sort implementations
 */
#include <iostream>
using namespace std;
 
void shellSortPhase(int a[], size_t length, size_t gap) {
    int i;
 
    for (i = gap; i < length; ++i) {
        int value = a[i];
        int j;
        for (j = i - gap; j >= 0 && a[j] > value; j -= gap) {
            a[j + gap] = a[j];
        }
        a[j + gap] = value;
    }
}
 
void shellSort(int a[], size_t length) {
    /*
     * gaps[] should approximate a geometric progression.
     * The following gaps are every other Fibonacci number,
     * which gives r=2.616.
     */
    static const int gaps[] = {
        1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946
    };
    int sizeIndex;
 
    for (sizeIndex = sizeof(gaps)/sizeof(gaps[0]) - 1;
               sizeIndex >= 0;
               --sizeIndex)
        shellSortPhase(a, length, gaps[sizeIndex]);
}
int main()
{
    int a[] = {7,34,6,3,2,7,8,12,3,5};
 
    shellSort(a,10);
    for(int i=0; i<10; i++)
    {
        cout<<a[i]<<" ";
    }    
    cin.get();
    return 0;
}
/**
 * Performs an insertion sort on elements of a[] with the given gap.
 * If gap == 1, performs an ordinary insertion sort.
 * If gap >= length, does nothing.
 * Based on a C implementation from the article Insertion sort implementations
 */
#include <iostream>
using namespace std;

void shellSortPhase(int a[], size_t length, size_t gap) {
    int i;

    for (i = gap; i < length; ++i) {
        int value = a[i];
        int j;
        for (j = i - gap; j >= 0 && a[j] > value; j -= gap) {
            a[j + gap] = a[j];
        }
        a[j + gap] = value;
    }
}

void shellSort(int a[], size_t length) {
    /*
     * gaps[] should approximate a geometric progression.
     * The following gaps are every other Fibonacci number,
     * which gives r=2.616.
     */
    static const int gaps[] = {
        1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946
    };
    int sizeIndex;

    for (sizeIndex = sizeof(gaps)/sizeof(gaps[0]) - 1;
               sizeIndex >= 0;
               --sizeIndex)
        shellSortPhase(a, length, gaps[sizeIndex]);
}
int main()
{
    int a[] = {7,34,6,3,2,7,8,12,3,5};
    
    shellSort(a,10);
    for(int i=0; i<10; i++)
    {
        cout<<a[i]<<" ";
    }    
    cin.get();
    return 0;
}

iamthwee

Featured Poster

Reputation Points: 1536

Solved Threads: 431

Posting Expert

Offline

5,865 posts
since Aug 2005

Permalink

Apr 5th, 2006

Re: Shell Sort w/ fibonacci numbers...HELP!!! Due Friday

I'm not fully understanding what that program does. If u could try to explain it to me, it would be greatly appreciated.

darylesha

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

4 posts
since Apr 2006

Permalink

Apr 5th, 2006

Re: Shell Sort w/ fibonacci numbers...HELP!!! Due Friday

[edit]****[/edit]

SpS

Reputation Points: 70

Solved Threads: 32

Posting Pro

Offline

598 posts
since Aug 2005

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: day month year help

Next Thread in C++ Forum Timeline: Selection Sort and String

DaniWeb Message

Cancel Changes

User Name
Password