Czasy wykonywania algorytmu sortowań różnią się poprzez CodeBlocksa i terminal

Question

Cześć.

Mam za zadanie porównać czasy działania algorytmów dla różnych sortowań dla różnych wielkości tablic.

Napisałem cały program.

Odpalam terminal, włączam program i za każdym razem mimo dużego rozmiaru liczb do posortowania wartość zawsze była bliska 0. Głowię się nad tym już od 2h i nie wiem o co chodzi.

Włączyłem CodeBlocksa i tam pokazuje w miarę możliwe do uzyskania wynika.

Oto wycinek z obu konsol:

( https://zapodaj.net/971b359b814ac.png.html )

Oto kod:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include<time.h>

void shell_Sort(int *tab, int n)
{
    int i, j, increment, tmp;
    for(increment = n/2; increment > 0; increment /= 2)
    {
        for(i = increment; i < n; i++)
        {
            tmp = tab[i];
            for(j = i; j >= increment; j -= increment)
            {
                if(tmp < tab[j-increment])
                    tab[j] = tab[j-increment];
                else
                    break;
            }
            tab[j] = tmp;
        }
    }
}

void bubble_Sort(int *tab, int n)
{
    int j;
    bool swapped = true;
    int index =0;

    while(index < n-1 && swapped)
    {
        swapped = false;
        for(j = 0; j < n -1 ; j++)
            if(tab[j] > tab[j+1])
            {
                swap(tab,j,j+1);
                swapped = true;
            }
        index++;
    }
}

void insert_Sort(int *tab, int n)
{
    int i,x,j;

    for(i=1; i<n; i++)
    {
        x=tab[i];
        j=i-1;
        while(tab[j]>x && j>=0)
        {
            tab[j+1]=tab[j];
            j--;
        }
        tab[j+1]=x;
    }
}

void select_Sort(int *tab, int n)
{
    int minIndex,i,j;

    for(i=0; i<n; i++)
    {
        minIndex = i;

        for(j = i+1 ; j< n; j++)
        {
            if(tab[minIndex]>tab[j])
            {
                minIndex = j;
            }
        }
        if(minIndex!=i)
        {
            swap(tab,minIndex,i);
        }
    }
}

void swap(int *tab, int index1, int index2)
{
    int temp = tab[index1];
    tab[index1] = tab[index2];
    tab[index2] = temp;
}

void heap_Sort(int *tab, int n)
{
    int i;
    for( i = n / 2 - 1; i >= 0; i--)
    {
        checkMaxHeap(tab, n, i);
    }

    for( i = n - 1; i > 0; i--)
    {
        swap(tab, 0, i);
        --n;
        checkMaxHeap(tab, n, 0);
    }
}

void checkMaxHeap(int *tab, int heapSize, int parentIndex)
{
    int maximumIndex = parentIndex;
    int leftChild = parentIndex * 2 + 1;
    int rightChild = parentIndex * 2 + 2;

    if(leftChild < heapSize && tab[leftChild] > tab[maximumIndex])
    {
        maximumIndex = leftChild;
    }
    if(rightChild < heapSize && tab[rightChild] > tab[maximumIndex])
    {
        maximumIndex = rightChild;
    }
    if(maximumIndex != parentIndex)
    {
        swap(tab, maximumIndex, parentIndex);
        checkMaxHeap(tab, heapSize, maximumIndex);
    }
}

void quick_Sort(int *tab, int poczatek, int koniec)
{
    int i=poczatek,j=koniec,s,pom;

    s=tab[(i+j)/2];
    do
    {
        while (tab[i]<s)
            i++;
        while (tab[j]>s)
            j--;
        if(i<=j)
        {
            pom=tab[i];
            tab[i]=tab[j];
            tab[j]=pom;
            i++;

            j--;
        };
    }
    while(i<=j);
    if(j>poczatek)
        quick_Sort(tab,poczatek,j);
    if(i<koniec)
        quick_Sort(tab,i,koniec);
}


int main()
{
    int n, sortOption, typeOption,i ;

    printf("How many numbers do you want to sort?\n");
    scanf("%d", &n);

    int *tab = (int*)malloc(sizeof(int)*n);

    printf("Please input which numbers you want to sort <-100,100>:\n");
    printf("1. Random numbers\n2. Numbers sorted descending\n3. Numbers sorted ascending\n");
    scanf("%d", &typeOption);

    printf("Which type of sorting do you want to use?\n");
    printf("1. Bubble sort \n2. Insert Sort\n3. Select Sort\n4. Shell Sort\n5. Heap Sort\n6. Quick Sort\n");
    scanf("%d",&sortOption);

    switch(typeOption)
    {
    case 1:
    {
        FILE* fp = fopen("dane-test1.txt", "r");
        for(i = 0 ; i < n ; i++)
        {
            fscanf(fp, "%d", &tab[i]);
        }
        fclose(fp);
        break;
    }

    case 2:
    {
        FILE* fp = fopen("dane-test2.txt", "r");
        for(i = 0 ; i < n ; i++)
        {
            fscanf(fp, "%d", &tab[i]);
        }
        fclose(fp);
        break;
    }
    case 3:
    {
        FILE* fp = fopen("dane-test3.txt", "r");
        for(i = 0 ; i < n ; i++)
        {
            fscanf(fp, "%d", &tab[i]);
        }
        fclose(fp);
        break;
    }
    }

    clock_t start,stop;
    double time;
    start=clock();

    switch(sortOption)
    {
    case 1:
        bubble_Sort(tab,n);
        break;
    case 2:
        insert_Sort(tab,n);
        break;
    case 3:
        select_Sort(tab,n);
        break;
    case 4:
        shell_Sort(tab,n);
        break;
    case 5:
        heap_Sort(tab,n);
        break;
    case 6:
        quick_Sort(tab,0,n);
        break;
    }

    stop=clock();
    time=(double)(stop-start) / CLOCKS_PER_SEC;
    printf("Algorithm needed  %f seconds",time);
    free(tab);
}

 

Answer 1

Masz odpowiednie pliki w folderze, z którego uruchamiasz program w terminalu zwykłym? Nie masz kontroli poprawnego otwarcia pliku w kodzie, więc program notuje czas który potrzebował na działanie polegające na przejściu przez switch'a

To jedyne co przychodzi mi do głowy

Comments

....

Masakra. Zginął bym bez tego forum.

Taka drobnostka, tyle czasu w dupe:)

Dzieki