1

This might not be a conventional of doing quicksort.my first try at it.the numbers are not sorted in the way they should be.I have tried to sort a random list of numbers.However i am unable to identify the logical errors even after a strict checking.

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

int n;
int *expivot;
int *arr;
void quicksort();
void display();
int check();

main()
{
    int i;
    printf("to continue press 'a' always\n");
    while(getch()=='a')
    {
        printf("Enter the length of list\n");
        scanf("%d",&n);
        time_t start,end;
        double t;
        start=clock();
        arr=(int *)calloc(n,sizeof(int));
        expivot=(int *)calloc(n,sizeof(int));
        srand(time(NULL));
        for(i=0;i<n;i++)
            arr[i]=rand()%RAND_MAX + 1;
        printf("\nelements inputted are:");
        display();
        quicksort();
        end=clock();
        t=(double)(end-start)/CLOCKS_PER_SEC;
        printf("\n\nelements sorted are:");
        display();
        printf("\ntime take is %.15lf",t);
        free(arr);
        free(expivot);
    }
}
void quicksort()
{
    int low,high,temp;
    int pivot=rand()%n;//generate random pivot
    int store=pivot;
    /*location of pivot might change due to swapping,so using store to store pivot      location so as to add this to expivot list after running quickort once*/
    int flag=1;
    if(expivot[pivot]==1)   // checks if it's an already used pivot
        flag=0;
    if(flag==1) //if the pivot is unused
    {
        low=pivot;
        high=pivot;
        while(low>0 && expivot[low]==0)
            low--;
        if(expivot[low]==1)//i
            low++;
        /*decrements low to a location where a value has been set permanently and then    increase by 1,if nothing is set then decrements low to zero*/
        /*increments high to a location where a value has been set permanently and then decrease by 1,if nothing is set then increments high to last index*/
        while(high<n-1 && expivot[high]==0)
            high++;
        if(expivot[high]==1)
            high--;
        while(low<high)
        {
            if(arr[low]>=arr[pivot] && arr[high]<=arr[pivot])//checks swap  possibilty
            {
                if(low==pivot)   //if pivot is to be swapped store new location of pivot
                    store=high;
                else if(high==pivot)
                    store=low;
                temp=arr[low];
                arr[low]=arr[high];
                arr[high]=temp;
                low++;
                high--;
            }
            else
            {
                if(arr[low]<arr[pivot])
                    low++;
                else if(arr[high]>arr[pivot])
                    high--;
            }
        }
        expivot[store]=1;
        /*final location of pivot,stores info that this location has a permanent value now
         and cannot be used as a pivot*/
    }
    if(check()==1)
        quicksort();
}


int check() //checks if there are any unused pivots
{
    int i;
    for(i=0;i<n;i++)
    {
        if(expivot[i]==0)
            return 1;
    }
    return 0;
}

void display()
{
    int i;
    for(i=0;i<n;i++)
        printf("%d ",arr[i]);
}
WhozCraig
  • 65,258
  • 11
  • 75
  • 141
Rahul Jha
  • 1,131
  • 1
  • 10
  • 25
  • What's the simplest list it fails to sort correctly? – Beta Nov 28 '13 at 05:51
  • 2
    The use of global variables is moderately evil, and very much unnecessary. It would probably be easier to get the code correct if you passed the range to be sorted to the sort function. – Jonathan Leffler Nov 28 '13 at 05:56
  • Wouldn't choosing the pivot as the mid of list be better than choosing a random pivot? – Harshil Sharma Nov 28 '13 at 06:48
  • 1
    the idea of a pivot flags array, though novel, defeats the fundamental purpose of how quicksort works. The scan of `expivot[]` is O(N). At *best* it is scanned N times, thereby introducing an O(N^2) step into what is supposed to be an O(NlogN) algorithm. Ouch. – WhozCraig Nov 28 '13 at 06:49
  • @HarshilSharma See this: [Quicksort: Choosing the Pivot](http://stackoverflow.com/questions/164163/quicksort-choosing-the-pivot/164183#164183). You want the pivot choice to be non-deterministic if possible (sometimes it isn't). The algorithm's divide-and-conquer structure is data-value based, unlike say mergesort, which is data independent. That dependence means *on average* you want to choose pivot values that will not be on the "ends" of segments. – WhozCraig Nov 28 '13 at 06:50
  • 1. Don't use global variables. 2. Use `assert` statements at the points in the code where you can validate your invariants. Having them fail will give you insights into the code. – Noufal Ibrahim Nov 28 '13 at 06:55

2 Answers2

0

Quicksort is a Divide and Conquer algorithm. You cannot perform it without using stacks or recursion.

Edit: The function does use recursion (oops!). But this isn't quicksort. If your are changing the method of a standard sorting algorithm, then it is no more that algorithm.

skrtbhtngr
  • 2,223
  • 23
  • 29
0

Your method is:

  1. Randomly select a pivot from whole array;
  2. From the pivot, spread a range to both direction, this range will be partitioned by the pivot;
  3. All pivot will be cached in another array (item 5);
  4. The range, mentioned in item 2 above, should apread as large as it can do, but: 1) should not beyond the range of whole array; 2) should not contain another pivot, if it does, stop and shrink one unit;
  5. Partition the range by the pivot it spread from, then cache this pivot;
  6. If all unit in the array has been selected as pivot, sorting is done. If not, repeat as above, over and over again.

There are three problems in your code:

1- "checd()"function should be:

int check() //checks if there are any unused pivots
{
    int flag = 0;
    int i;
    for(i=0;i<n;i++)
    {
        if(expivot[i]==0)
            flag = 1;
    }
    return flag;
}

You should check all member, see if they ALL satisfy your condition, but not one of them satisfy your condition.

2- While shrink the range, make sure the pivot is between "high" and "low" (equal is well). Keep tracking the index and value of the pivot. The while loop should be:

//"store" is not needed, change it to "pivot", even after this code block.
    while(low<high)
    {
        if(arr[low]>=arr[pivot] && arr[high]<=arr[pivot])//checks swap  possibilty
        {
            if(low==pivot)   //if pivot is to be swapped store new location of pivot
                pivot=high;
            else if(high==pivot)
                pivot=low;
            temp=arr[low];
            arr[low]=arr[high];
            arr[high]=temp;

            /////////////////////
            if (low < pivot)
                low++;
            if (high > pivot)
                high--;
            /////////////////////
        }
        else
        {
            if(arr[low]<arr[pivot])
                low++;
            else if(arr[high]>arr[pivot])
                high--;
        }
    }

3- Finally, once you get memory from calloc or malloc, check if it's NULL.

================================== Additionally, you should make sure all unit in the array can be selected, because the random number in computer is mostly pseudo random number. So, maybe for a certain length, a particular unit cannot be chosen forever.

SliceSort
  • 357
  • 3
  • 5