go_away

### Author Topic: Sorting Algo check up!  (Read 1101 times)

0 Members and 1 Guest are viewing this topic.

#### TrickyNekro

• Contest Winner
• Supreme Robot
• Posts: 1,207
• 1.6L Peugeot 307 tuner
##### Sorting Algo check up!
« 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...

Let's say we have a 50 element array:

Code: [Select]
`A[1] <- GetADCFOR 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  ENDIFNEXT`
For whom the interrupts toll...

P.S. I've been inactive for almost a year... Don't give promises but I'll try to complete my tutorials. I'll let you know when..

Cheers!

#### superchiku

• Supreme Robot
• Posts: 953
• cooll
##### Re: Sorting Algo check up!
« Reply #1 on: March 10, 2009, 01:15:25 AM »
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...
Code: [Select]
`# 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

Code: [Select]
`# 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(); }    `
JAYDEEP ...

IT AND ROBOTICS ENGINEER

"IN THE END IT DOESNT EVEN MATTER"

#### TrickyNekro

• Contest Winner
• Supreme Robot
• Posts: 1,207
• 1.6L Peugeot 307 tuner
##### Re: Sorting Algo check up!
« Reply #2 on: March 10, 2009, 05:14:18 AM »
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...
For whom the interrupts toll...

P.S. I've been inactive for almost a year... Don't give promises but I'll try to complete my tutorials. I'll let you know when..

Cheers!

#### chelmi

• Supreme Robot
• Posts: 496
##### Re: Sorting Algo check up!
« Reply #3 on: March 10, 2009, 07:41:09 AM »
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/Quicksort