Sorting Algorithm Help Pls.

[SwiftDeath]

I am creating a new sorting algorithm as a machine problem and i encounter difficulties.

The logic of my said the said algorithm is to create an array by inputing the total numbers to be accepted followed by the array variables and sorting it ascending or descending. The array would be sorted on both sides, through insertion sort.

So far, i didn't have any luck with it and my deadline is coming to a close. I really need anyone's help on this one i'm begging you.

Here is an example:

Array Total: 6
Ascending: 4 5 9 1 3 2

Compare the 1st and last number in ascending order. Swap if true.
1st Pass: 2 5 9 1 3 4
Increment both sides. this time the numbers to be compared are Group1(2,5) and Group2(3,4). Swap them according to their places.
2nd Pass: 2 3 9 1 4 5
Then the next pass, wherein you do the same procedure as number two. Group1(2,3,9) and Group2(1,4,5) Then swap.
3rd Pass: 2 3 9 1 4 5
The last pass where you arrange the whole array.
Last Pass: 1 2 3 4 5 9

If the amount of numbers to be arrange is odd. Then include the number in the middle to the left group and arrange it before doing the last pass.

Please everyone. Anyone. I really need your help on this.

#include"stdio.h"
#include"stdlib.h"

void read_list(int element[], int total)
{
int ctr;
for(ctr=0;ctr<total;ctr++)
{
printf("\n Enter Element [%d] ::" ,ctr);
scanf("%d", &element[ctr]);
}
}


void print_list(int element[], int total)
{
int ctr;
for(ctr=0;ctr<total;ctr++)
printf(" %d", element[ctr]);
}


void insert_sort(int element[], int total)
{
int mid, left, right, ctr, ctr2, ctr3, temp;

mid = total/2;

for(ctr=total-1; ctr>=mid; ctr--)
{
for(ctr2=0; ctr2<mid && element[ctr2] > element[ctr]; ctr2++)
{
temp = element[ctr];
element[ctr] = element[ctr2];
element[ctr2] = temp;
if ((ctr2 < mid) && (ctr >= mid))
{
if (element[ctr2] > element [ctr2+1])
{
temp = element[ctr2+1];
element[ctr2+1] = element[ctr2];
element[ctr2] = temp;
}
}
if ((ctr2 < mid) && (ctr >= mid))
{
if (element[ctr-1] > element[ctr])
{
temp = element[ctr];
element[ctr] = element[ctr-1];
element[ctr-1] = temp;
}
}
printf("\n Pass %d :: ", ctr2+1);
print_list(element,total);
}
}
}
void main()
{
int element[20], total;
clrscr();

printf("\n Enter Array Length :: ");
scanf("%d", &total);
read_list(element,total);
printf("\n The Array Elements are as follows :: ");
print_list(element,total);
insert_sort(element,total);
printf("\n Last Pass :: ");
print_list(element,total);
getch();
}

I really need you help on this one pls.


 

[ArkM]

IMHO, it's not the best sorting algorithm, but...

See inner loop condition. Why

...&& element[ctr2] > element[ctr] ?

Don't break the loop if no need to swap the current pair: may be, the next pair must been swapped. Check indicies only in this loop header.

Now see inner loop body. It's time to check swap condition:

  { /* inner loop body */
     if (element[ctr2] > element[ctr])
     {
        temp = element[ctr];
        element[ctr] = element[ctr2];
        element[ctr2] = temp;
     }
  ...

See 2nd and 3rd ifs conditions in the inner loop. They are exactly the same as loops conditions, so both are true in the inner loop body. Discard these redundant checks...

Good luck!

PS. Don't fill test array from the keyboard on debug stage, fill it by auxiliary routine or by simple initialization (or, better, use stdin redirection and test files). Remember deadline...

 

[SwiftDeath]

I tried what you told me and so far it really lessened the problems,

unfortunately, the looping statement which increments and decrements both sides are having problems. once the side increments or decrements once it passes the 1st and last side, it wont be able to check them again.

Example: 5 4 6 8 2 1

1st: 1 4 6 8 2 5
2nd: 1 4 6 8 2 5
The loop condition can't check 1 & 5 again since ctr and ctr2 already incremented.
3rd: 1 4 6 2 8 5
Not just that if i pull the print condition from inside ctr2 loop, it won't be able to print the changes happening inside and only prints the output.

and if i don't it doubles the amount of passes it does.

i really appreciate your help, since i'm only a newbie in c. (1st yr college) i mean a real nwebie and i hope at getting better in this language.

here is the revised codes:

void insert_sort(int element[], int total)
{
int mid, left, right, ctr, ctr2, ctr3, temp;

mid = total/2;

for(ctr=total-1; ctr>=mid; ctr--)
{
for(ctr2=0; ctr2<mid; ctr2++)
{
if(element[ctr2] > element[ctr])
{
temp = element[ctr];
element[ctr] = element[ctr2];
element[ctr2] = temp;
}
if ((ctr2 < mid) && (element[ctr2] > element[ctr2+1]))
{
temp = element[ctr2+1];
element[ctr2+1] = element[ctr2];
element[ctr2] = temp;
}
if ((ctr >= mid) && (element[ctr-1] > element[ctr]))
{
temp = element[ctr];
element[ctr] = element[ctr-1];
element[ctr-1] = temp;
}
printf("\n Pass %d :: ", ctr2+1);
print_list(element,total);
}
}
}

pls help me.

 

[Salem]

http://www.daniweb.com/forums/thread132372.html

Also

http://www.catb.org/~esr/faqs/smart-questions.html#forum

Also, learn to use the code tags which every forum provides.


--
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.

 

[ArkM]

Unfortunately, this algorithm is not correct in principle, it does not sort any array element configuration.

Emergency measures: add outer loop to repeate your sorting loops (I'm not sure it's a mortal blow:

int i;
mid = total / 2;
for (i = 0; i < 2; --i)
{
  /* your loops here */
}

Alas, I'm not ready to invent new sorting algorithm now (it's a really hard work. Try to proof new algorithm before implement it.

Again: draw attention to inner loops logic:

  for(ctr=total-1; ctr>=mid; ctr--)
  {
    for(ctr2=0; ctr2<mid; ctr2++)
    { /* ctr >= mid && ctr2 < mid now (see above)! */
      ....
      if ((ctr2 < mid) && ....) /* Why if (true && ...)? */
         ....
      if ((ctr >= mid) && ....) /* Why if (true %% ...)? */
         ....
      ...
    }
  }

 

[ArkM]

Sorry, must be:

for (i = 0; i < 2; ++i)
....

 

[SwiftDeath]

i didn't quite get what you mean? what does %% mean?? hmm.. this is a case study of sorts and shoud i omit the inner loop ctr2? and add the one you included?

 

[ArkM]

Where is %% (two percent signs) in my post above?!
Sorry, I don't understand you: why omit inner loop?
Please, see my post above: make a NEW loop to repeate YOUR loops (for ctr2 and ctr) TWICE.

 

[SwiftDeath]

ahh.. ok.. i'm sorry i didn't quite understand well, if i do that i would be increasing the passes made with the sorting algo, the sorting algo's goal is to reduce the amount of passes if it is done using insert sort.

for example:

to sort this: 5 4 6 8 2 1
in insertion it'll take 5 passes

while in the algorithm i'm trying to make it should take less than that..

but thanks for your reply,

 

[ArkM]

Better use more passes + sorted array than a very very fast algorithm returned unsorted array, eh?..

It's possible to break Hoar sort (for example) on 1/2 its way (what's a wonderful speeding up but don't call this algorithm SuperSonicSorting...

 

[SwiftDeath]

no of course i won't ^_^ its just i need to follow the logic and at times i get dizzy becaus of it, i only have months of exposure in c and i don't even have that many background on sorting algorithms. and sometimes have a tendency on sticking to what i have been doing instead of finding new ways >.< pls help me.

 

[SwiftDeath]

what is hoar sort anyway?

 

[ArkM]

Hoare (sorry for misspelling), or Quick Sort, see:

http://www.softpanorama.org/Algorithms/Sorting/quicksort.shtml

or

http://en.wikipedia.org/wiki/Quicksort

(there are tons of useful links on this page).

About help. I see incorrect or incomplete sorting algorithm description. What else can I do for you in this circumstances? It's not C language issue. Try to revise the new sorting algorithm and demonstrate its correctness.

May be I'm wrong...

 

[lionelhill]

Looking at this, I get the feeling you might appreciate Shellsort, if you haven't already looked into it.

 

[SwiftDeath]

oops.. i'm sorry that i wasn't able to explain it clearly, here is an example of it. .

ascending order:
for example: 5 4 6 8 2 1 -- 1st last to be compared, then increment left and decrement right.

1st pass: 1 4 6 8 2 5 -- then compare the underline again and swap

2nd pass: 1 2 6 8 4 5 -- compare the underline again and swap

last pass: 1 2 4 5 6 8 -- final answer.

this is the flow of the algorithms logic. . thanks a lot every one i really appreciate it T_T

 

[ArkM]

That's OK but I don't understand why the last pass swaps {4,5} and {6,8}. It's impossible for increment left/decrement right process. Let's forget (for the time being) your implementation. Can you explain ALL algorithmic steps in plain English (preferably on school math level?

 

[SwiftDeath]

ohhh sory.. uhmm, here it is..

ascending order:
for example: 5 4 6 8 2 1
-- this is the original array increment composed of 6 elements, 1st we need to determine the mid point. so total numbers / 2 = mid point. when the mid point is determined already we will now proceed with the 1st pass. to get the 1st pass you must compare the left most element with the rightmost depending on the order here it is ascending. after determining which is which, you swap it.. that is how we got the answer in the 1st pass.

1st pass: 1 4 6 8 2 5
-- to be able to proceed to the next pass, first, you increment the left side and then decrement the right side, to be able to include 4 and 2. here the left group elements are 1,4 and the right group elements are 2,5. so again we determine the order of the numbers, arrange it first in groups, then as a whole by swapping their places. thus the arranged should be in pass 2.

2nd pass: 1 2 6 8 4 5
-- in pass 2 we increment the amount again, this time to include 6 to the left and 8 to the right, arrange it in groups then swap as a whole. that is how we get to the last pass.

last pass: 1 2 4 5 6 8 -- final answer.

the algo has flaws of its own but i have to face it i don't have enough time and my deadline is july 30, 2008 T_T i'm really sorry for inconvenience, but i do really appreciate your help on this.

 

[ArkM]

Please, try to state the algorithm without any for example, array size == 6, steps 1, 2, last - and other unnecessary details. You have an array of n integers - let's go. Include some kind of correctness proof - it goes without saying, of course.

After that (not in place of you may illustrate this description on int[6] array, but you want a sorting algorithm for arbitrary 1D array, not for array of 6 (or 7, or 5 etc) elements.

It's impossible to debug a program implemented undefined algorithm - we are in situation patch this, patch that...

 

[lionelhill]

Can I make a suggestion?

From the fact you have a deadline, I assume this is a college project of some sort?

If so, can I suggest you write a good implementation for any of the known sorting algorithms? No sane human is going to expect you to come up with a brand-new sorting algorithm. Vast amounts of thought have gone into sorting, and it is really hard to come up with a good idea that no one has ever had before.

Also, now you've put considerable thought into sorting, you'll probably find yourself very well placed to understand the quite sophisticated ideas behind such algorithms as shellsort and quicksort, both of which feature in most good textbooks, though not always particularly well-explained. If you want the whole works, look at the big algorithm textbooks, Knuth etc.

I think you'll find great educational value in finding out about them; more than there is in battering around with getting a fix out of tek-tips. Also, knowing when to turn to known methods, and knowing what methods are available, is an essential part of good professionalism. And it isn't always easy to write a good implementation of a good algorithm. The best algorithms frequently have extremely simple inner loops, and one foolishly-placed test (e.g. for whether you've reached the end of an array) can render the whole thing half the speed it should be. What I'm trying to say, is you're not "chickening out" if you decide to implement quicksort.

Incidentally, there are people here who would red-flag a thread like this for the likely "homework" aspect...

 

[ArkM]

I'm agree with lionelhill (100%).