943,866 Members | Top Members by Rank

Software Development > C > Help Me With Sorting Algo
Ad:
  • C Discussion Thread
  • Unsolved
  • Views: 1216
  • C RSS
You are currently viewing page 1 of this multi-page discussion thread
Permalink
Jul 16th, 2008
0

Help Me With Sorting Algo

Expand Post »
Pls Help me, i am nearing the deadline July 30 of this case study and the code is almost finshed it does sort the input elements the way my algo logic does however i am not able to display the correct number of passes to show the law of the algo, it shoud be:

number of passes = total number of elements / 2
if total number of elements / 2 = .5 round off to left subgroup

the main logic of the algo is to divide it into two groups and sort it in either ascending or descending order, for example:

total number of elements = 6
order: descending

element 1: 5
element 2: 4
element 3: 6
element 4: 8
element 5: 2
element 6: 1

Original: 5 4 6 | 8 2 1
| = MID

Pass 1: the underlined elements are the numbers involved to be sorted, they shoud be swapped if ever the right first element of the right subgroup (in this case 1) is greater than the left subgroup (in this case 5)
5 4 6 | 8 2 1

Pass 3: then increase the number of elements to be sorted on both sides and repeat the seapping process as long as it satisfies the condition.
8 6 5 | 4 2 1

The problem is it didn't print out Pass 2: which should be 5 4 6 | 8 2 1

Here is the code:

  1. #include"stdio.h"
  2. #include"stdlib.h"
  3.  
  4. void read_list(int element[], int total,char choice)
  5. {
  6.   int ctr;
  7.  
  8. 	if (choice == 'a' || choice == 'A')
  9. 	{
  10. 		for(ctr=0;ctr<total;ctr++)
  11. 		{
  12. 			printf("\n Enter Element [%d] ::" ,ctr);
  13. 			scanf("%s", &element[ctr]);
  14. 		}
  15. 	}
  16. 	if (choice == 'b' || choice == 'B')
  17. 	{
  18. 		for(ctr=0;ctr<total;ctr++)
  19. 		{
  20. 			printf("\n Enter Element [%d] ::" ,ctr);
  21. 			scanf("%d", &element[ctr]);
  22. 		}
  23. 	}
  24. }
  25.  
  26.  
  27. void print_list(int element[], int total,char choice)
  28. {
  29.   int ctr;
  30.  
  31. 	if (choice == 'a' || choice == 'A')
  32. 	{
  33. 		for(ctr=0;ctr<total;ctr++)
  34. 			printf("  %c", element[ctr]);
  35. 	}
  36. 	if (choice == 'b' || choice == 'B')
  37. 	{
  38. 		for(ctr=0;ctr<total;ctr++)
  39. 			printf("  %d", element[ctr]);
  40. 	}
  41. }
  42.  
  43.  
  44. void insert_sort(int element[], int total,char choice)
  45. {
  46. 	int pt, mid, left, right, ctr, ctr2, ctr3, temp;
  47.  
  48.   mid = total/2;
  49. 	pt = 0;
  50. 	ctr3 = 0;
  51. 	while (pt++ < mid)
  52. 	{
  53.  
  54. 		for(ctr=total-1, ctr2=0; ctr>=mid && ctr2 <mid; ctr--, ctr2++)
  55. 		{
  56. 			if (element[ctr2] < element[ctr])
  57. 			{
  58. 				temp = element[ctr];
  59. 				element[ctr] = element[ctr2];
  60. 				element[ctr2] = temp;
  61.  
  62. 				printf("\n Go Pass %d :: ", ctr2);
  63. 				print_list(element,total,choice);
  64. 			}
  65.  
  66. 			if ((element[ctr2] >= element[ctr]) && ctr3 == 0)
  67. 			{
  68. 				ctr3 = 1;
  69. 				printf("\n To Pass %d :: ", ctr2);
  70. 				print_list(element,total,choice);
  71. 			}
  72. 			for (ctr3=0; ctr3<mid; ctr3++)
  73. 			{
  74. 				for (left=0; left<mid; left++)
  75. 				{
  76. 					if (element < element [left+1])
  77. 					{
  78. 						temp = element[left+1];
  79. 						element[left+1] = element;
  80. 						element = temp;
  81. 					}
  82. 				}
  83.  
  84. 				for (right=total-1; right>=mid; right--)
  85. 				{
  86. 					if (element[ctr-1] < element[ctr])
  87. 					{
  88. 						temp = element[ctr];
  89. 						element[ctr] = element[ctr-1];
  90. 						element[ctr-1] = temp;
  91. 					}
  92. 				}
  93. 			}
  94. 		}
  95. 	}
  96. 	pt++;
  97. 	printf("\n Pass %d :: ", ctr2);
  98. 	print_list(element,total,choice);
  99.  
  100. }
  101.  
  102. void main()
  103. {
  104.   int element[20], total;
  105. 	char choice;
  106. 	clrscr();
  107.  
  108. 	printf("Choose: A - Alphanumeric B - Numeric :: ");
  109. 	scanf("%c", &choice);
  110.  
  111.   printf("\n Enter Array Length :: ");
  112.   scanf("%d", &total);
  113.  
  114. 	read_list(element,total,choice);
  115.  
  116. 	printf("\n The Array Elements are as follows :: ");
  117. 	print_list(element,total,choice);
  118.  
  119. 	insert_sort(element,total,choice);
  120.  
  121. 	printf("\n\n Final Answer :: ");
  122. 	print_list(element,total,choice);
  123.  
  124. 	getch();
  125. }

Pls Help me T___T
Similar Threads
Reputation Points: 10
Solved Threads: 0
Newbie Poster
SwiftDeath is offline Offline
22 posts
since Jul 2008
Permalink
Jul 16th, 2008
0

A Sorting Algo Question!

We all know that creating your own algorithm should have a law, but is it possible that the number of passes it makes may be lesser or more than the average performance?

example:

average case: number of passes = total elements / 2

best case: number of passes < (total element / 2)

worst case: number of passes > (total element /2) but not more than total element

Pls help me, i would like to hear your comments about this one.
Reputation Points: 10
Solved Threads: 0
Newbie Poster
SwiftDeath is offline Offline
22 posts
since Jul 2008
Permalink
Jul 16th, 2008
0

Re: Help Me With Sorting Algo

i really need any help i can get, hmm.. and i would like to thank adak for helping me with this last time, however i wasn't able to clearly understand what you taught of me in my last thread
Reputation Points: 10
Solved Threads: 0
Newbie Poster
SwiftDeath is offline Offline
22 posts
since Jul 2008
Permalink
Jul 16th, 2008
0

Re: Help Me With Sorting Algo

The code you posted has several compiler errors that you need to fix, such as lines 76, 79 and 80.
Last edited by Ancient Dragon; Jul 16th, 2008 at 8:58 am.
Sponsor
Team Colleague
Featured Poster
Reputation Points: 5608
Solved Threads: 2282
Retired and Enjoying Life
Ancient Dragon is offline Offline
21,951 posts
since Aug 2005
Permalink
Jul 16th, 2008
0

Re: Help Me With Sorting Algo

Hee is the re-written code @ Ancient Dragon,

  1. #include"stdio.h"
  2. #include"stdlib.h"
  3.  
  4. void read_list(int element[], int total,char choice)
  5. {
  6.   int ctr;
  7.  
  8. 	if (choice == 'a' || choice == 'A')
  9. 	{
  10. 		for(ctr=0;ctr<total;ctr++)
  11. 		{
  12. 			printf("\n Enter Element [%d] ::" ,ctr);
  13. 			scanf("%s", &element[ctr]);
  14. 		}
  15. 	}
  16. 	if (choice == 'b' || choice == 'B')
  17. 	{
  18. 		for(ctr=0;ctr<total;ctr++)
  19. 		{
  20. 			printf("\n Enter Element [%d] ::" ,ctr);
  21. 			scanf("%d", &element[ctr]);
  22. 		}
  23. 	}
  24. }
  25.  
  26.  
  27. void print_list(int element[], int total,char choice)
  28. {
  29.   int ctr;
  30.  
  31. 	if (choice == 'a' || choice == 'A')
  32. 	{
  33. 		for(ctr=0;ctr<total;ctr++)
  34. 			printf("  %c", element[ctr]);
  35. 	}
  36. 	if (choice == 'b' || choice == 'B')
  37. 	{
  38. 		for(ctr=0;ctr<total;ctr++)
  39. 			printf("  %d", element[ctr]);
  40. 	}
  41. }
  42.  
  43.  
  44. void insert_sort(int element[], int total,char choice)
  45. {
  46. 	int pt, mid, left, right, ctr, ctr2, ctr3, temp;
  47.  
  48.   mid = total/2;
  49. 	pt = 0;
  50.  
  51. 	while (pt++ < mid)
  52. 	{
  53. 		for(ctr=total-1, ctr2=0; ctr>=mid && ctr2 <mid; ctr--, ctr2++)
  54. 		{
  55. 			if (element[ctr2] > element[ctr])
  56. 			{
  57. 				temp = element[ctr];
  58. 				element[ctr] = element[ctr2];
  59. 				element[ctr2] = temp;
  60.  
  61. 				printf("\n Pass %d :: ", ctr2);
  62. 				print_list(element,total,choice);
  63.  
  64. 			}
  65.  
  66. 			/*
  67. 			printf("\n Pass %d :: ", ctr2);
  68. 			print_list(element,total,choice);
  69. 			*/
  70.  
  71. 			for (ctr3=0; ctr3<mid; ctr3++)
  72. 			{
  73. 				for (left=0; left<mid; left++)
  74. 				{
  75. 					if (element > element [left+1])
  76. 					{
  77. 						temp = element[left+1];
  78. 						element[left+1] = element;
  79. 						element = temp;
  80. 					}
  81. 				}
  82.  
  83. 				for (right=total-1; right>=mid; right--)
  84. 				{
  85. 					if (element[ctr-1] > element[ctr])
  86. 					{
  87. 						temp = element[ctr];
  88. 						element[ctr] = element[ctr-1];
  89. 						element[ctr-1] = temp;
  90. 					}
  91. 				}
  92. 			}
  93. 		}
  94. 	}
  95. 	pt++;
  96.  
  97. 	printf("\n Pass %d :: ", ctr2);
  98. 	print_list(element,total,choice);
  99.  
  100. }
  101.  
  102. void main()
  103. {
  104.   int element[20], total;
  105. 	char choice;
  106. 	clrscr();
  107.  
  108. 	printf("Choose: A - Alphanumeric B - Numeric :: ");
  109. 	scanf("%c", &choice);
  110.  
  111.   printf("\n Enter Array Length :: ");
  112.   scanf("%d", &total);
  113.  
  114. 	read_list(element,total,choice);
  115.  
  116. 	printf("\n The Array Elements are as follows :: ");
  117. 	print_list(element,total,choice);
  118.  
  119. 	insert_sort(element,total,choice);
  120.  
  121. 	printf("\n\n Final Answer :: ");
  122. 	print_list(element,total,choice);
  123.  
  124. 	getch();
  125. }
Reputation Points: 10
Solved Threads: 0
Newbie Poster
SwiftDeath is offline Offline
22 posts
since Jul 2008
Permalink
Jul 16th, 2008
1

Re: Help Me With Sorting Algo

GCC doesn't like your code.
  1. sort.c: In function ‘read_list’:
  2. sort.c:13: warning: format ‘%s’ expects type ‘char *’, but argument 2 has type ‘int *’
  3. sort.c: In function ‘insert_sort’:
  4. sort.c:75: warning: comparison between pointer and integer
  5. sort.c:78: warning: assignment makes integer from pointer without a cast
  6. sort.c:79: warning: assignment makes pointer from integer without a cast
  7. sort.c: At top level:
  8. sort.c:102: warning: return type of ‘main’ is not ‘int’
  9. sort.c: In function ‘main’:
  10. sort.c:106: warning: implicit declaration of function ‘clrscr’
  11. sort.c:124: warning: implicit declaration of function ‘getch’
  12. /tmp/ccNDVhKN.o: In function `main':
  13. sort.c:(.text+0x3d1): undefined reference to `clrscr'
  14. sort.c:(.text+0x489): undefined reference to `getch'
  15. collect2: ld returned 1 exit status
  16.  
GCC doesn't have clrscr() or getch() -- they're non-standard functions, after all -- but if your compiler does you can ignore those errors.

main() should really return int instead of void, though.

And the other warnings I think are important.
printf("\n Enter Element [%d] ::" ,ctr);
scanf("%s", &element[ctr]);
Should be %d, no?

[edit] Ah, I see that you really do want to store a string. Well, you can't do that when you have an array of ints. I suggest either using a struct/union with int and char[] members, or two separate arrays. [/edit]

  1. if (element > element [left+1])
  2. /* ... */
  3. element[left+1] = element;
  4. element = temp;
I think perhaps you wanted this:
  1. if (element > element [left+1])
  2. /* ... */
  3. element[left+1] = element;
  4. element = temp;

[edit] With those modifications, numeric sorting works as far as I can tell. Though the code could be a lot better -- with something like this, for example:
  1. void order(int *a, int *b) {
  2.     if(*a > *b) {
  3.         int temp = *a;
  4.         *a = *b;
  5.         *b = temp;
  6.     }
  7. }
Alphanumeric sorting doesn't work, of course, because you can't read a string into a number. [/edit]

[edit=2] In case you're interested, here's my modified code. Sorry about the length, everyone.
  1. #include"stdio.h"
  2. #include"stdlib.h"
  3.  
  4. void read_list(int element[], int total,char choice)
  5. {
  6.   int ctr;
  7.  
  8.         if (choice == 'a' || choice == 'A')
  9.         {
  10.                 for(ctr=0;ctr<total;ctr++)
  11.                 {
  12.                         printf("\n Enter Element [%d] ::" ,ctr);
  13.                         scanf("%d", &element[ctr]);
  14.                 }
  15.         }
  16.         if (choice == 'b' || choice == 'B')
  17.         {
  18.                 for(ctr=0;ctr<total;ctr++)
  19.                 {
  20.                         printf("\n Enter Element [%d] ::" ,ctr);
  21.                         scanf("%d", &element[ctr]);
  22.                 }
  23.         }
  24. }
  25.  
  26.  
  27. void print_list(int element[], int total,char choice)
  28. {
  29.   int ctr;
  30.  
  31.         if (choice == 'a' || choice == 'A')
  32.         {
  33.                 for(ctr=0;ctr<total;ctr++)
  34.                         printf("  %c", element[ctr]);
  35.         }
  36.         if (choice == 'b' || choice == 'B')
  37.         {
  38.                 for(ctr=0;ctr<total;ctr++)
  39.                         printf("  %d", element[ctr]);
  40.         }
  41. }
  42.  
  43.  
  44. void insert_sort(int element[], int total,char choice)
  45. {
  46.         int pt, mid, left, right, ctr, ctr2, ctr3, temp;
  47.  
  48.   mid = total/2;
  49.         pt = 0;
  50.  
  51.         while (pt++ < mid)
  52.         {
  53.                 for(ctr=total-1, ctr2=0; ctr>=mid && ctr2 <mid; ctr--, ctr2++)
  54.                 {
  55.                         if (element[ctr2] > element[ctr])
  56.                         {
  57.                                 temp = element[ctr];
  58.                                 element[ctr] = element[ctr2];
  59.                                 element[ctr2] = temp;
  60.  
  61.                                 printf("\n Pass %d :: ", ctr2);
  62.                                 print_list(element,total,choice);
  63.  
  64.                         }
  65.  
  66.                         /*
  67.                         printf("\n Pass %d :: ", ctr2);
  68.                         print_list(element,total,choice);
  69.                         */
  70.  
  71.                         for (ctr3=0; ctr3<mid; ctr3++)
  72.                         {
  73.                                 for (left=0; left<mid; left++)
  74.                                 {
  75.                                         if (element > element [left+1])
  76.                                         {
  77.                                                 temp = element[left+1];
  78.                                                 element[left+1] = element;
  79.                                                 element = temp;
  80.                                         }
  81.                                 }
  82.  
  83.                                 for (right=total-1; right>=mid; right--)
  84.                                 {
  85.                                         if (element[ctr-1] > element[ctr])
  86.                                         {
  87.                                                 temp = element[ctr];
  88.                                                 element[ctr] = element[ctr-1];
  89.                                                 element[ctr-1] = temp;
  90.                                         }
  91.                                 }
  92.                         }
  93.                 }
  94.         }
  95.         pt++;
  96.  
  97.         printf("\n Pass %d :: ", ctr2);
  98.         print_list(element,total,choice);
  99.  
  100. }
  101.  
  102. int main()
  103. {
  104.   int element[20], total;
  105.         char choice;
  106.  
  107.         printf("Choose: A - Alphanumeric B - Numeric :: ");
  108.         scanf("%c", &choice);
  109.  
  110.   printf("\n Enter Array Length :: ");
  111.   scanf("%d", &total);
  112.  
  113.         read_list(element,total,choice);
  114.  
  115.         printf("\n The Array Elements are as follows :: ");
  116.         print_list(element,total,choice);
  117.  
  118.         insert_sort(element,total,choice);
  119.  
  120.         printf("\n\n Final Answer :: ");
  121.         print_list(element,total,choice);
  122.  
  123.         return 0;
  124. }
[/edit]
Last edited by dwks; Jul 16th, 2008 at 4:14 pm.
Reputation Points: 185
Solved Threads: 28
Posting Whiz in Training
dwks is offline Offline
269 posts
since Nov 2005
Permalink
Jul 16th, 2008
0

Re: Help Me With Sorting Algo

That last post was getting crowded so I thought I'd start another one -- especially since it's a higher-level one.

Since you're trying to handle both numbers and strings, why not have two separate functions: one to read an array of numbers, and the other an array of strings? The functions themselves could declare the necessary arrays, and then call the sorting function.

The sorting function would need to be able to sort strings or numbers. You could declare two functions, but that's just a waste. You could pass the array in as a void type and then pass in a function pointer to compare the types, just like qsort() does. http://www.cplusplus.com/reference/c...lib/qsort.html

If you don't feel up to that, you could use something a bit simpler, such as:
  1. void sort(void *data, int is_string, /*...*/) {
  2.     /* ... */
  3.     if(is_string) {
  4.         if(strcmp(((char **)data)[0], ((char **)data)[1]) > 0) /* ... */
  5.     }
  6.     else {
  7.         if(((int **)data)[0] > ((int **)data)[1]) /* ... */
  8.     }
  9. }
Or you could just write two separate functions . . . .

Something I gave away in that example: you use strcmp() to compare strings. It returns less than zero, equal to zero, or greater than zero, depending on whether its arguments were less than, equal to, or great than each other, respectively.
Reputation Points: 185
Solved Threads: 28
Posting Whiz in Training
dwks is offline Offline
269 posts
since Nov 2005
Permalink
Jul 16th, 2008
0

Re: Help Me With Sorting Algo

Is this right? (Line 75 or so)
  1.  
  2. if (element > element [left+1])   //???
  3.  
  4. {
  5.  
  6.    temp = element[left+1];   
  7.  
  8.    element[left+1] = element;   //???
  9.  
  10.    element = temp;   //???
  11.  
  12. }

element is the *address* of the array, a pointer to the array, and it's being compared with a value of the array??

You should be getting a warning about this from your compiler. You shouldn't compare an address with an integer or char value, nor should you try assigning the address of the array (which can't be assigned), the value of a char or array, or even another address.
Last edited by Adak; Jul 16th, 2008 at 9:41 pm.
Reputation Points: 416
Solved Threads: 181
Nearly a Posting Virtuoso
Adak is offline Offline
1,463 posts
since Jun 2008
Permalink
Jul 17th, 2008
0

Re: Help Me With Sorting Algo

oh my god!! i'm only a beginner at c and i don't know structs and unions, and i don't know the difference between int main and void main T_T that's why this is how i constructed my sorts.. T_T what is GCC anyway?? hmm.. but of course i do know how to understand the logic tha's my strong points.. sorry >_< if my logic is somehow difficult to understand T_T
Reputation Points: 10
Solved Threads: 0
Newbie Poster
SwiftDeath is offline Offline
22 posts
since Jul 2008
Permalink
Jul 17th, 2008
0

Re: Help Me With Sorting Algo

Uhhm, i was able to fix the recent problems.. now, i think that my sorting algo is a bit off than what i imagined it, uhmm.. i haven't edited it though to integrate it with what you've written here.. but thanks! i think i'll try it later tonight or tomorrow, T__T 10 days before the judgement day..

  1. #include"stdio.h"
  2. #include"stdlib.h"
  3.  
  4. void read_list(int element[], int total,char choice)
  5. {
  6.   int ctr;
  7.  
  8. 	if (choice == 'a' || choice == 'A')
  9. 	{
  10. 		for(ctr=0;ctr<total;ctr++)
  11. 		{
  12. 			printf("\n Enter Element [%d] ::" ,ctr);
  13. 			scanf("%s", &element[ctr]);
  14. 		}
  15. 	}
  16. 	if (choice == 'b' || choice == 'B')
  17. 	{
  18. 		for(ctr=0;ctr<total;ctr++)
  19. 		{
  20. 			printf("\n Enter Element [%d] ::" ,ctr);
  21. 			scanf("%d", &element[ctr]);
  22. 		}
  23. 	}
  24. }
  25.  
  26.  
  27. void print_list(int element[], int total,char choice)
  28. {
  29.   int ctr;
  30.  
  31. 	if (choice == 'a' || choice == 'A')
  32. 	{
  33. 		for(ctr=0;ctr<total;ctr++)
  34. 			printf("  %c", element[ctr]);
  35. 	}
  36. 	if (choice == 'b' || choice == 'B')
  37. 	{
  38. 		for(ctr=0;ctr<total;ctr++)
  39. 			printf("  %d", element[ctr]);
  40. 	}
  41. }
  42.  
  43.  
  44. void insert_sort(int element[], int total,char choice)
  45. {
  46. 	int pt, mid, left, right, ctr, ctr2, ctr3, temp;
  47.  
  48.   mid = (total+1)/2;
  49. 	pt = 0;
  50.  
  51. 		for(ctr=total-1, ctr2=0; ctr>=mid && ctr2 <mid; ctr--, ctr2++)
  52. 		{
  53.  
  54. 				if (element[ctr2] > element[ctr])
  55. 				{
  56. 					temp = element[ctr];
  57. 					element[ctr] = element[ctr2];
  58. 					element[ctr2] = temp;
  59. 				}
  60.  
  61. 				for (left=0; left<=ctr2; left++)
  62. 				{
  63. 					if (element > element [left+1])
  64. 					{
  65. 						temp = element[left+1];
  66. 						element[left+1] = element;
  67. 						element = temp;
  68. 					}
  69. 				}
  70.  
  71. 				for (right=total-1; right>=ctr; right--)
  72. 				{
  73. 					if (element[right-1] > element)
  74. 					{
  75. 						temp = element;
  76. 						element = element[right-1];
  77. 						element[right-1] = temp;
  78. 					}
  79. 				}
  80.  
  81. 			printf("\n Go Pass %d :: ", ctr2);
  82. 			print_list(element,total,choice);
  83.  
  84. 		}
  85. }
  86.  
  87. void main()
  88. {
  89.   int element[20], total;
  90. 	char choice;
  91. 	clrscr();
  92.  
  93. 	printf("Choose: A - Alphanumeric B - Numeric :: ");
  94. 	scanf("%c", &choice);
  95.  
  96.   printf("\n Enter Array Length :: ");
  97.   scanf("%d", &total);
  98.  
  99. 	read_list(element,total,choice);
  100.  
  101. 	printf("\n The Array Elements are as follows :: ");
  102. 	print_list(element,total,choice);
  103.  
  104. 	insert_sort(element,total,choice);
  105.  
  106. 	printf("\n\n Final Answer :: ");
  107. 	print_list(element,total,choice);
  108.  
  109. 	getch();
  110. }
Reputation Points: 10
Solved Threads: 0
Newbie Poster
SwiftDeath is offline Offline
22 posts
since Jul 2008

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C Forum Timeline: cocatenattion without strcat function
Next Thread in C Forum Timeline: two letters = one number?





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC