[Webinar] Streamline your web hosting managementRegister Today

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 305
  • Last Modified:

sorting algorithms and worst case determination

Can someone please give some easy to understand code
and brief description of the following algorithms?

1)Insertion sort
2)Selection sort
3)Heap Sort
4)Merge Sort
5)Quick sort

I would also like to know when to use which algo. and some general rules for determining the worst case and best case complexities.

I could have given more points for this question but the problem is I don't have !!!


Regards & Thanks a lot
0
arut
Asked:
arut
1 Solution
 
abdijCommented:
Hi Man,
  You can always earn more points, cant you?
Any way reagrding the problem you specified. Its gonna take some time. I amy answer you tomorrow since i do have to code them. (Psst: i have forgoten the Haep Sorting!!!).
Meanwhile the others ma answer you.
Thanx
Abdij
0
 
AlexVirochovskyCommented:
In http://www.snippets.org you
can find many sorting code with
comments.
0
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 
Ernest022699Commented:
This sounds too much like homework!
0
 
hongjunCommented:
I agree with Ernest.
0
 
AlexVirochovskyCommented:
From www.snippets.org 
+++++++++++++++++++++++
+++Date last modified: 05-Jul-1997

There are four kinds of sorts.  There are sorts that search, sorts that swap,
sorts that separate, and sorts that don't compare one element to another.  In
the first class are the insertion sort, the extraction sort, and the heap
sort. In the second class are the quick sort and the merge sort.  In the
third class are the bubble sort and the Shell sort.  In the last class are
the Radix-Exchange sort and the Pigeon sort.  (These lists aren't all
inclusive. In fact, I know I'm leaving some sorts out, but I just want to
give examples of what's in each class.)

I won't talk about the last class because I don't find them particularly
interesting.  Even though they are the fastest kind of sorts known, with O(N)
sorts not only possible but practical in many cases, it is difficult to
generalize them, and I'm fond of finding general solutions to general
problems.

In the sorts that swap, the only variable is which elements are swapped.  The
Shell sort starts by swapping elements that are far apart in hopes that any
"large scale" disorder is eliminated quickly.  The bubble sort compares only
those elements that are next to each other.  Each pair is compared and, if
they are found to be out of order, they are swapped.

The sorts that separate work by understanding that it is a lot faster to sort
smaller lists than bigger lists.  So, you seek to break up the lists into
halves and then break up the halves and then break up the quarters, and so on
until each piece is small enough to sort.  (Often, a program will just
continue to break the list down until each piece has a length of one.  A list
of one item is already sorted.  On the other hand, many programmers prefer to
stop after the element size gets small enough.)

However, there is a choice to be made in this case.  Do you attempt to impose
order on the list before or after you split it into parts.  The quick sort is
a before sort.  The merge sort is an after sort.  When you quick sort a list,
you choose a value, called the pivot, and you build your sublists such that
all of the elements which have a key value less than the pivot go into one
sublist and those elements which do not go into the other.  Then, you
recursively sort each sublist and when that is done you simply append the
"greater than" list to the "less than" list to make the whole sorted list.
With a merge sort, you find the middle and break it there without any concern
for the key values of the elements, recursively sort each sublist and then
merge the two sorted lists back together into one big list.  (The real nice
thing about the merge sort is you don't have to be able to pick a good pivot
value in order for it to work well. Most of the algorithms for finding the
best pivot values start "Sort the list...")

The insertion sort is what you do when you "build a sorted list."  Basically,
you go through the unsorted list, and for each element, you find the place in
the sorted list where it should go and put it there.  This process is
repeated until there are no more elements in the unsorted list. The
extraction sort looks through the unsorted list for the element with the
biggest (or smallest) value and once it finds it, appends that element to the
sorted list.  This process is repeated until there are no more elements in
the unsorted list.
+++++++++++++++++
I HOPE, that it is not homework!
0
 
arutAuthor Commented:
Thanks a lot to all of you and sorry for troubling ...

:)arut
0
 
AlexVirochovskyCommented:
For you comment I concluded, that
it is not homework and my info was helpful.
0
 
KangaRooCommented:
Well, his comment was addressed 'to all of you', but you did the most work :)
0
 
pure032398Commented:
Heya all.

I don't want to sound rude, to re-activate this dead thread, but checking that snippet site which was the accepted answer, how do u use this function??

void *sortl(void *list, void *(*getnext)(void *),
            void (*setnext)(void *, void *),
            int (*compare)(void *, void *))

if my list is
struct student_data *student_list;

how do i sort the contents of student list? (that function header is VERY confussing to us 1st years...)

-PK-
0
 
AlexVirochovskyCommented:
pure, this Q is closed. Ask you Question
in c++/c area and I or other expert
will help you.
0

Featured Post

Free tool for managing users' photos in Office 365

Easily upload multiple users’ photos to Office 365. Manage them with an intuitive GUI and use handy built-in cropping and resizing options. Link photos with users based on Azure AD attributes. Free tool!

Tackle projects and never again get stuck behind a technical roadblock.
Join Now