Monday, May 12, 2014

QuickSort in Java

public class QuickSort
{
    public static void main(String args[])
    {

        int arr[] = { 5, 4, 3, 2, 1 };

        quickSort(arr, 0, 4);
        System.out.println("Output");
        for (int i : arr)
            System.out.println(i);
    }

    public static void quickSort(int arr[], int f, int l)
    {
        int j;
        if (f < l)
        {
            j = partition(arr, f, l);
            quickSort(arr, f, j - 1);
            quickSort(arr, j + 1, l);
        }
    }

    public static int partition(int arr[], int f, int l)
    {
        int pivot = arr[f];

        int i = f;
        int j = l;
        int temp;

        while (i < j)
        {
            while (arr[i] <= pivot && i < l)
                i++;
            while (arr[j] > pivot && j > f)
                j--;

            if (i < j)
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;

            }
        }

        temp = arr[f];
        arr[f] = arr[j];
        arr[j] = temp;

        return j;
    }
}

Thursday, August 8, 2013

Optimized Insertion Sort

Insertion Sort can be helpful when you only want to place a single element in the array.
However, it is not efficient if there data set is large because of it's number of comparisons and shifts.
I found that we can actually do small modification in the Insertion sort and can reduce number of comparisons.

While working on the Binary Search we can modify the binary search in such way that if element is not present in array it will return the -(index-1); this will denote element's index if you want to insert this into array.
In java I found that they have already done this kind of implementation however, people who work in other languages can write their own implementation
like below in C:

int bsearch(int low, int high, int item)
{
     int  mid;
    int midItem;
     while(low <= high)
     {
        mid = (low+high)/2;
        midValue=arr[mid];
        if(item == midItem) return mid;
        if(item < midItem)
           high = mid - 1;
        else
           low = mid + 1;
    }
    return -low-1;
}
  • So instead of comparing each element to other sorted elements, we can simply perform the binary search on the sorted part of array and can find the location where new element should be inserted. In this way we can save the time of comparison, Yes shift will still require. 
  • However, in java there is API System.arraycopy which can help you in copying the entire array at one shot, yes it is better than a loop to shift each element.
  • I tried this on more than one dimensional array and didn't get the desired results.

Saturday, July 26, 2008

Palindrome

int palindrom(const char *str)
{
int len;
int i;
len = strlen(str);
len--;
for(i=0; i < len;i++,len--)
if(str[i]!=str[len])
return 1;//not a palindrome
return 0;//a palindrome
}

To reverse a string.

void rev(char *str)
{
int len;
int i;
char temp;
len = strlen(str)-1;
for(i=0; i < len; i++,len--)
{
temp=str[i];
str[i]=str[len];
str[len]=temp;
}
}

A program to move a circle in a box.

#include
#include
#include
#include

#define DELAY 4
#define RADIUS 10

int main(void)
{
/* request auto detection */
int gdriver = DETECT, gmode, errorcode;
int midx, midy;
int signx=1, signy=1;

/* initialize graphics and local variables */
initgraph(&gdriver, &gmode, "c:\\tc\\bgi");

/* read result of initialization */
errorcode = graphresult();
if (errorcode != grOk) /* an error occurred */
{
printf("Graphics error: %s\n", grapherrormsg(errorcode));
printf("Press any key to halt:");
getch();
exit(1); /* terminate with an error code */
}

midx = getmaxx() / 2;
midy = getmaxy() / 2;
setcolor(getmaxcolor());

/* draw the circle and move it continously */
rectangle(0,0,getmaxx(), getmaxy());

while(!kbhit())
{
setcolor(WHITE);
circle(midx, midy, RADIUS);
delay(DELAY);
setcolor(BLACK);
circle(midx, midy, RADIUS);
midx=midx+signx*1;
midy=midy+signy*1;
if( (midx+RADIUS+1>= getmaxx()) || (midx-RADIUS-1 <= 0) )
signx=-signx;

if( (midy+RADIUS+1>=getmaxy()) || (midy-RADIUS-1<= 0))
signy=-signy;


}

/* clean up */
getch();
closegraph();
return 0;
}