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

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>

Simple (bubble)sort can look like this:

void swap(Node_ptr &list, Node_ptr n, Node_ptr next, Node_ptr prev) {
     n->ptr_to_next_node = next->ptr_to_next_node;
     next->ptr_to_next_node = n;
     if (prev) {
         prev->ptr_to_next_node = next;
     }
     else {
         /* we're at first node */
         list = next;
     }
}

void sort(Node_ptr &list) {
     bool swapped;
     do {
         swapped = false;
         for (Node_ptr n = list, prev = NULL; n && n->ptr_to_next_node; 
prev = n, n = n->ptr_to_next_node) {
             Node_ptr next = n->ptr_to_next_node;
             if (strcmp(n->word, next->word) > 0) {
                 swap(list, n, next, prev);
                 swapped = true;
             }
         }
     } while (swapped);
}

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>

> ------------ Původní zpráva ------------
> Od: Per Westermark <pw...@ia...>
> Předmět: Re: [Dev-C++] Sorting Linked Lists and Array Members
> Datum: 03.5.2011 11:39:34
> ----------------------------------------
> 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, ...

Merge sort is also n*logn; in fact it's often used on arrays as well. The fact that sorting list in place may be slower than using temporary array is because it needs more cpu instructions to traverse/manipulate a list than an array.

Yes, there are a number of n-log-n sorting algorithms. But there are no
algorithm better than n-log-n.

So worrying about the linear transfer times from moving list elements into
a vector of pointers and then back again can not be a time issue when
debating choices.

Next thing is that many n-log-n algorithms does require direct-access to
elements. If requiring traversals to locate the elements, then they will
no longer be n-log-n.

But a person who spends an hour or two with Google looking for different
sort algorithms and looking for specific help on sorting lists should be
able to quickly get a good view of what is recommendable solutions -
obviously taking into account if the lists are always small or if the
lists may have tens of thousands of entries where O(n^2) may be hundreds
of times slower than O(n log n).

If the OP did do as I suggested, he would be able to find the following
(or similar) information about merge-sort (quote is from wikipedia but
other sources of sorting algorithms would come to similar results):
"Merge sort is often the best choice for sorting a linked list: in this
situation it is relatively easy to implement a merge sort in such a way
that it requires only .(1) extra space, and the slow random-access
performance of a linked list makes some other algorithms (such as
quicksort) perform poorly, and others (such as heapsort) completely
impossible."

So in my previous post, I was trying to debate two different things:

The first thing I wanted to make clear was that a multipass solution (like
copying data to an array) can match a single-pass algorithm since O(n) +
O(n log n) + O (n) is still just O(n log n). And that a linked list means
objects are accessed using pointers meaning that the array only needs to
store these pointers and not the full node content.

The second thing I wanted to make clear was that the net have lots of
documentation about sort algorithms and about sorting of linked lists. So
someone who don't know what to do can get far with quite limited time
spent googling. Mailing lists and web forum are then great choices to ask
questions if someone gets stuck after having spent that initial time
reading up on a couple of available choices.

It is way easier when someone comes back and say: "I have been trying to
implement an insertion sort (since it is fast enough for my needs of no
more than 100 elements) but now are stuck trying to ..."

 /pwm

On Tue, 3 May 2011 mol...@se... wrote:

>
> > ------------ Pùvodní zpráva ------------
> > Od: Per Westermark <pw...@ia...>
> > Pøedmìt: Re: [Dev-C++] Sorting Linked Lists and Array Members
> > Datum: 03.5.2011 11:39:34
> > ----------------------------------------
> > 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, ...
>
>  Merge sort is also n*logn; in fact it's often used on arrays as well.
> The fact that sorting list in place may be slower than using temporary
> array is because it needs more cpu instructions to traverse/manipulate a
> list than an array.
>
> ------------------------------------------------------------------------------
> WhatsUp Gold - Download Free Network Management Software
> The most intuitive, comprehensive, and cost-effective network
> management toolset available today.  Delivers lowest initial
> acquisition cost and overall TCO of any competing solution.
> http://p.sf.net/sfu/whatsupgold-sd
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www23.brinkster.com/noicys/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>