Society of Robots - Robot Forum
Software => Software => Topic started by: TrickyNekro on March 09, 2009, 08:50:53 PM
-
Hello guys,
I was just sitting at my chair and trying to make a space and time efficient algorithm for
a little something I'm preparing... I was only familiar with the bubble sort but it's too slow and inefficient
so I came up to this as an idea of mixing smart bubble sort and insertion sort...
Please have a look and tell me your thoughts about it!!!
Let's say we have a 50 element array:
A[1] <- GetADC
FOR i = 1 TO 49
temp <- GetADC
IF temp > A[i] THEN
A[i+1] <- temp
ELSE
j <- i
WHILE a <- false
A[j+1] <- A[j]
j <- j - 1
IF j = 0 THEN
A[1] <- temp
a <- true
ELSE
IF temp > A[j] THEN
A[j+1] <- temp
a <- true
ENDIF
ENDIF
WEND
ENDIF
NEXT
-
use merge sort or quicksort instead don use bubble sort or inserton sort the have max time complexity of n^2 while quick sort has nlogn
i have sample quick sort programs and merge sort programs in c...hope u know c...
# include<stdio.h>
# include<conio.h>
int a[10];
int divideandconquer(int low,int high)
{
int i,j,reference;
i=low-1;
j=high+1;
reference=a[low];
while(i<j)
{
do
{
i++;
}while(a[i]<reference);
do
{
j--;
}while(a[j]>reference);
if(i<j){
a[i]=a[i]+a[j];
a[j]=a[i]-a[j];
a[i]=a[i]-a[j];
}
else
return(j);
}
}
void quicksort(int low,int high)
{
int j;
if(low<high)
{
j=divideandconquer(low,high);
quicksort(low,j);
quicksort(j+1,high);
}
}
void main()
{
int g;
clrscr();
printf("\nenter the elements");
for(g=0;g<=9;g++)
{
printf("\n insert the %dth element",g+1);
scanf("%d",&a[g]);
}
quicksort(0,9);
printf("\n sorted array is ");
for(g=0;g<=9;g++)
{
printf(" %d ",a[g]);
}
getch();
}
merge sort
# include<stdio.h>
# include<conio.h>
# include<math.h>
int a[10];
void merge(int,int,int);
void mergesort(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,mid,high);
}
}
void merge(int low,int mid,int high)
{
int *temp,i,j,k;
i=low;
j=mid+1;
temp=(int*)malloc(sizeof(int)*(high-low+1));
k=0;
while(i<=mid && j<=high)
{
if(a[i]<a[j])
{
temp[k]=a[i];
i++;
k++;
}
else
{
temp[k]=a[j];
j++;
k++;
}
}
while(i<=mid)
{
temp[k]=a[i];
i++;
k++;
}
while(j<=high)
{
temp[k]=a[j];
j++;
k++;
}
k=0;
for(i=low;i<=high;i++)
{
a[i]=temp[k];k++;
}
}
void main()
{
int g;
clrscr();
printf("enter the elements\n");
for(g=0;g<=9;g++)
{
printf("\n enter the %dth element",g+1);
scanf("%d",&a[g]);
}
mergesort(0,9);
printf("\n the sorted array is");
for(g=0;g<=9;g++)
{
printf(" %d ",a[g]);
}
getch();
}
-
Thank man, but unfortunately...
It was a little bit hard for me to read...
I made a try to understand merge but it gives me the creeps...
Quick sort is understandable fortunately....
Any other recommendations are more than well come!!!
better in pseudocode...
-
If there in ONE algorithm you shouldn't invent in 2009, it's a sorting algorithm ;)
http://en.wikipedia.org/wiki/Merge_sort (http://en.wikipedia.org/wiki/Merge_sort)
http://en.wikipedia.org/wiki/Quicksort (http://en.wikipedia.org/wiki/Quicksort)