Re: [Dev-C++] Sorting Linked Lists and Array Members

[Per W. <pw...@ia...>]

Large numbers of posts here.

Note 1:
School assignments are intended to be solved by the student.

The student is intended to have the required knowledge to manage the
tasks.

Many schools do follow mailing lists and web forums (google works well for
that) to catch students that offloads their work on the net.

Note 2:
Standard debugging work includes identifying corner cases. Things like:
- what happens if first element is inserted/removed?
- what happens if last element is inserted/removed?
- what happens if internal (not first/last) element is inserted/removed?
- what happens if there is no match?

Should be trivial to step through the code in a debugger for the above
four cases and see what happens. Note that if you have one pointer that is
your "list" and points to the first element - what do you do when you
remove this element?

Note 3:
You don't seem to have tried Google for finding information about how to
sort linked lists. There is huge amounts of information.

Note 4:
You worry about time for copying if using a array for the sorting. But
that means that you haven't spent any time learning about ordo - the cost
of operations taking constant time O(1), proportional time O(n), quadratic
time O(n^2) etc.

It is very fast to walk through a linked list once and copy the element
pointers into an array. That is a linear operation - one extra step for
every extra element.

Sorting an array taks n-log-n time which is the best possible for sorting.

Rebuilding the linked list is one walk through the array, so linear time.

So using an array is a good sorting method.

Now try Google and look at bubble sort, insertion sort, merge sort, ...

Now what do you find about efficiency? Do you still worry about any
copying? You do realize that you only need to copy pointers - not any
real content of the individual list elements?

Note 5:
Just about every function you are requested to add to your program ends up
as a help request to this list. Isn't that a bit strange? Does your class
mates also needs their own web forum or mailing list to get through? Or
maybe they have looked in books about computer algorithms or have tried
Google? Or just spends a bit more time debugging their code?

Real programming means developers who sits and spends their own time
solving problems. The world would ground to a stand-still if all
development required people to ask for help on the net - and who would be
competent enough to answer the questions if people don't learn to solve
their own problems? Experience can't help, because bigger experience just
means people starts working on more complex probems until they reach a
level where they can't trivially write code but just have to spend lots of
own time fighting with the problems at hand.

When looking for a job, the job interview will focus a lot on your ability
to solve problems. And many companies will not allow you to discuss your
projects on the net, making it very hard to ask for magical online help.

What would you do if you googled and found posts where developers from a
major elevator manufactuer asks for help since they don't know how to
safely calculate and regulate the speed of an elevator? If the developers
for a car manufactuers asks about help on anti-lock break system
configuration? If the alarm clock manufacturer needs help how to implement
snooze functionality?

/pwm

On Mon, 2 May 2011, Jordan Burnam wrote:

> Hey Everyone,
>
> I have the following function that I am implementing within a list class in order to be able to sort them. This list should sort the char array elements by the alphabet but so far have had little luck to implement  this. At this point I know that I  cannot compare the two values of the array with the ">" operand but if I type cast it to an int but then I also get the lowercase ASCII value for each letter and make it a constant to figure out which one goes first I could do it this way but there has to be an easier way to do this. Below I have pasted the entire program as to make it easier to understand the context of the function, the function in question is the very last one named "list_selection_sort". Any idea or comments would be much appreciated. 
>
> 	Thanks, 
> 	Jordan     
>
> <code>
>
>
>
>  void list_selection_sort(Node_ptr &a_list)
>
>  {
>
> 	 Node_ptr currNode;
> 	 Node_ptr nextNode;
> 	 Node_ptr lastNode;
>
> 	 int itiems = 1;
>
> 	 
>
>
>
> 	 currNode = a_list;
>
> 	 while(currNode ->ptr_to_next_node != NULL)
>
> 	 { 
>
> 		 currNode = currNode ->ptr_to_next_node;
>
> 		 itiems++;
>
>
>
> 	 }
>
> 	 lastNode = currNode;
> 	 currNode = a_list;
> 	 nextNode = currNode ->ptr_to_next_node;
>
> 	 while (itiems > 0)
> 	 {
> 		  if(currNode -> word[0] > nextNode -> word[0])
> 		  {
> 			 curr
>
>
> 		  }
>
> 		  else
> 			{  lastNode = currNode;
> 			 currNode = currNode ->ptr_to_next_node;
> 			 nextNode = currNode ->ptr_to_next_node;}
> 		  itiems--;
> 	 }
>
> 	 system("pause");
>
>  }
>
> <\code>