Array Sort

[nowy20180820]

  /******************************************************************************

                            Online C Compiler.
                Code, Compile, Run and Debug C program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

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

// Heap sort based on CLRS's pseudocode with removed recursion

void heapify(int *A,int i,int heapSize)
{
    int l,r,largest,save;
    int temp;
    do
    {
        l = 2 * i + 1;
        r = 2 * i + 2;
        if(l <= heapSize && A[l] > A[i])
            largest = l;
        else
            largest = i;
        if(r <= heapSize && A[r] > A[largest])
            largest = r;
        save = i;
        if(largest != i)
        {
            temp = A[i];
            A[i] = A[largest];
            A[largest] = temp;
            i = largest;
        }
    }
    while(largest != save);
}

void heapSort(int *A,int n)
{
    int i,heapSize;
    int temp;
    for(i = n/2 - 1;i >= 0;i--)
        heapify(A,i,n-1);
    heapSize = n - 1;
    while(heapSize >= 1)
    {
        temp = A[0];
        A[0] = A[heapSize];
        A[heapSize] = temp;
        heapSize--;
        heapify(A,0,heapSize);
    }
}

// Quick sort based on example from Wirth's Algorithms + Data Structures = Programs

void quickSort(int *A,int l,int r)
{
    int i,j;
    int x,w;
    i = l;
    j = r;
    x = A[(l + r)/2];
    do
    {
        while(A[i] < x) i++;
        while(x < A[j]) j--;
        if(i <= j)
        {
            w = A[i];
            A[i] = A[j];
            A[j] = w;
            i++;
            j--;
        }
    }
    while(i <= j);
    if(l < j) quickSort(A,l,j);
    if(i < r) quickSort(A,i,r);
}

// Shell Sort based on insertion Sort

void ShellSort(int *A,int n)
{
    int i,j,h;
    int buffer;
    h = 1;
    while(h <= n)
    {
        h *= 3;
        h++;
    }
    while(h > 0)
    {
        for(i = h;i < n;i++)
        {
            j = i;
            buffer = A[j];
            while((j >= h) && (A[j-h] > buffer))
            {
                A[j] = A[j - h];
                j -= h;
            }
            A[j] = buffer;
        }
        h /= 3;
    }
}

void printArray(int *A,int n)
{
    int k;
    for(k = 0;k < n;k++)
      printf("%d ",A[k]);
    printf("\n\n");
}

int main()
{
    int k,m,n;
    int *A;
    srand(time(NULL));
    printf("Podaj liczbê elementów tablicy \n");
    scanf("%d",&n);
    printf("Podaj maksymalny zakres przedzia³u dla losowanych liczb \n");
    scanf("%d",&m);
    A = (int *)malloc(n*sizeof(int));
    for(k = 0;k < n;k++)
       A[k] = rand()%m;
    printArray(A,n);
    heapSort(A,n);
    //quickSort(A,0,n-1);
    //ShellSort(A,n);
    printArray(A,n);
    free(A);
    system("PAUSE");
    return 0;
}

How can I eliminate worst case of quicksort using these three algorithms

[jonnin]

stop doing recursion of quick sort at some N and just shellsort the list from there. I forget the theoretical N size, but its substantial.
also get a better list of values for your shellsort's H array.

quicksort's recursive calls cost, and shell approaches O(N) as the list approaches sorted. So what happens is that after a few calls, quicksort partly orders the list making shell more efficient, and at some point it costs more to sub-divide than to finish out with shell.

[nowy20180820]

I thougth about switching to heap sort
and using Shell sort as a cut off for small sub array

https://oeis.org/A003586

Here is sequence for Shell sort
Hai He & Gilbert Traub
gave nice way to generate this sequence

Wikipedia claims that complexity of Shell sort with sequence
https://oeis.org/A003586
is O(nlog^2 n)

[jonnin]

what exactly do you want to accomplish?
heap is good -- if your stated goal of avoiding worst case is the priority, yes try it.

Ill trust you on the sequence. I was admittedly just looking at it quickly and historically the easy to generate ones have not been ideal.