Re: "Sorting" assignment

On Feb 4, 2:28 am, "Ivica" <prljavi_blu...@xxxxxxxxxxx> wrote:
First, I would like to thank everybody in my previous thread called "general
tree assignment in c".
It's not about some kind of student's lazyness, the problem is a little bit
depper. Guy, whose job was to taught us programming basics and C was so bad
so he got fired at our hard initiative so we are faced with severe problems
in this subject called "algorithms and data structures".

Now, we have to write something like this:

We have program which prints news. There are unlimited number of news(?).
Every news contains subject and body text. Also, we count how much was every
news read. Everytime a news get read, we add 1 to to the value "read".
Create functions which will print the top 5 of the news, how much in average
something gets read, and what's the difference between the top news and the
news in the middle.

I am looking at switch case usage and bubblesort?

If you use the bubble sort, your application may be too slow to manage
realistic amounts of news, and it appears you ganged up on your
instructor and got rid of him before you could learn about the
relative efficiency of sorting algorithms. Bubble sorting is how not
to sort.

Here is a C example of a simple program that sorts a list of random
numbers using the method of exchanging between two bins (partition
exchange) that I mentioned in my first post.

As I said, this algorithm grabs an arbitrary member and then compares
it to every other member, throwing each compared member into bin A or
bin B depending on whether it is greater than, or less than (or equal
to) the arbitrary member (called the pivot).

After the first pass. all members of bin A are less than or equal to
the pivot, and all members of bin B are greater than the pivot. The
program then calls itself, first for the A bin and then for the B bin.

This "recursive" call is not a loop since it calls the quicksort for
half the size each time through, therefore the size of bin A and bin B
approaches one, and the main quicksort exits when there are fewer than
2 entries.

But when A and B are one cell, this means that A <= pivot < B for all
members because the two recursive calls you see in the code cover all
the values. But that means that the entire array is sorted in rather
less time than a bubble sort, which maximizes the number of times an
entry must travel to get to its final position. For any arbitrary
entry, the probability of its having to move reduces each time the
quicksort is recursively called.

This is what intelligent workers might do on a farm when sorting
apples. They wouldn't use bubble sort. I think a programmer invented
that time sink.

Here is the code. Examine it in a monospace font such as Courier New.


// ***** Quicksort (partition exchange) example *****

#include <stdio.h>
#include <stdlib.h>

const int SIZE = 27;

int quicksortPartition
(int intArray[],
int intLeft,
int intRight,
int intPivotIndex)
{
int intPivotValue = intArray[intPivotIndex];
intArray[intPivotIndex] = intArray[intRight];
intArray[intRight] = intPivotValue;
int intStoreIndex = intLeft;
int intIndex1;
int intExchange;
for (intIndex1 = intLeft;
intIndex1 < intRight;
intIndex1++)
{
if (intArray[intIndex1] <= intPivotValue)
{
intExchange = intArray[intIndex1];
intArray[intIndex1] = intArray[intStoreIndex];
intArray[intStoreIndex] = intExchange;
intStoreIndex += 1;
}
}
intPivotValue = intArray[intStoreIndex];
intArray[intStoreIndex] = intArray[intRight];
intArray[intRight] = intPivotValue;
return intStoreIndex;
}


void quicksort(int intArray[],
int intLeft,
int intRight)
{
if (intRight > intLeft)
{
int intPivotNewIndex = quicksortPartition
(intArray,
intLeft,
intRight,
intLeft);
quicksort(intArray,
intLeft,
intPivotNewIndex - 1);
quicksort(intArray,
intPivotNewIndex + 1,
intRight);
}
}

int main(int argc,char *argv[])
{
int intArray[SIZE];
int intUpperBound = SIZE - 1;
int intIndex1;
for (intIndex1 = 0; intIndex1 < SIZE; intIndex1++)
{
intArray[intIndex1] =
(int)(frand() * 99);
printf("%2d ", intArray[intIndex1]);
}
printf("\n");
quicksort(intArray, 0, intUpperBound);
for (intIndex1 = 0; intIndex1 < SIZE; intIndex1++)
{
printf("%2d ", intArray[intIndex1]);
}
printf("\n");
return 0;
}




Sorry for any bad translation from croatian to english.

Thank you for your time.



REFERENCES


Hoare 1961: Hoare, C. A. R. "Partition: Algorithm 63," "Quicksort:
Algorithm 64," and "Find: Algorithm 65." Comm. ACM 4(7), 321-322,
1961

Wikipedia 2008: "Quicksort". http://en.wikipedia.org/wiki/Quicksort

.

Relevant Pages

  • Re: "Sorting" assignment
    ... If the array is already sorted, this means that you end up ... attempt to sort them. ... int quicksortPartition ... for (intIndex1 = intLeft; ...
    (comp.programming)
  • Re: "Sorting" assignment
    ... #define elementtype News ... typedef struct { ... int ID; ... Because if you could have written it, why not do the simpler array ...
    (comp.programming)
  • Re: News/Announcements form?
    ... NewsId <int> ... Whenever you create a news item, ... into the UserNews table for every user in the system. ...
    (microsoft.public.dotnet.languages.vb)
  • Getting top row(s) based on date
    ... I have a view which contains details of news items posted, ... [NewsItemCreatedDate] ...
    (microsoft.public.sqlserver.programming)
  • Re: Need help with reordering items
    ... > Here is a solution to the problem that uses a single update query: ... > set nocount on ... > Position int NOT NULL, ... > News wrote: ...
    (microsoft.public.sqlserver.programming)