Sorting Algorithms 3

[Chemakill]

Can anyone point me to a good site or tutorial on them? Specifically, I need to research BubbleSort, Insertion Sort, Selection Sort. Any help would be greatly appreciated.

 

[Cagliostro]

all of them are in <algorithm>. Every book about STL describe it fine. John Fill

ivfmd@mail.md

 

[Chemakill]

Erm... I have no idea what you are saying.

all of them are in <algorithm>. Every book about STL describe it fine.

What does that mean? I need a link to a good site, a good FAQ, or just a plain old explanation of the major sorting algorithms.

 

[Cagliostro]

STL is Standard Template Library. <algorithm> is a header file.
A very good book about STL is &quot;STL for C++ Programmers&quot; written by Len Ammeraal, Hogeschool Utrech, The Netherland. John Fill

ivfmd@mail.md

 

[Chemakill]

Thank you for explaining that bit. Is the book in English? Pardon me for being an ignorant Canadian. What I'm looking for is a link to an explanation of the various sorting algorithms, or just an explanation. I really don't want to go out and buy a book over this one little problem, and odds are, I can't even get a hold of that book around here (Manitoba) anyhow. But thanks anyways, and can someone please point me to the aforementioned explanation/example or provide it here?

 

[Cagliostro]

The book is available in many languages, but the native book is in english. John Fill

ivfmd@mail.md

 

[dArktEmplAr]

Try out the book Algorithms in C++ by Robert Seidgwick (not sure about the spelling of the surname)

Welcome to the Pythian Games!
Long live Godess Athena!
dArktEmplAr of Delphi Oracle

 

[chiph]

OK, here's the Loonie tour of sorting algorithms:

Bubblesort
Only use this if you have fewer than 10 items in your list. It's a CPU hog, and tends to move the data around way too much. Stay away from it if you can.

Insertion Sort
A 'fair' algorithm. Much better than Bubblesort. Is still somewhat CPU intensive. Somewhat recommended.

Selection Sort
Good general purpose algorithm. Recommended

QuickSort
Very fast sorting algorithm. But it falls down and takes linear time if the data is already partially sorted. First choice when you're fairly certain the data is distributed randomly.

Hope this gets you started. But you really ought to find a book on algorithms and algorithmic efficiency to learn more about these and other sorting/searching algorithms.

Chip H.

 

[aphrodita]

Merge Sort algorithm is very good too.
Here is the code:

...
void mergesort(int x[],int f,int l)
{
int m;
if ( f < l )
{
m = ( f + l ) / 2;
mergesort(x,f,m); // recursive call to sort left part
mergesort(x,m+1,l); // recursive call to sort right part
merge(x,f,m,l); // merging
}
}

void merge(int x[],int f,int m,int l)
{
int temp[MAX]; // MAX is the number of elements
int f1 = f, f2 = m + 1, l1 = m, l2 = l;
int q = f1;

while ((f1 < l1) && (f2 <= l2))
{
if (x[f1] < x[f2])
temp[q++] = x[f1++];
else
temp[q++] = x[f2++];
}

while (f1 <= l1)
temp[q++] = x[f1++];
while (f2 <= l2)
temp[q++] = x[f2++];

// Assigning back to the primary array
for ( q = 0; q < MAX; q ++ )
x[q] = temp[q];
}


The priciple of this sorting algorithm is to divide the problem into smaller parts. These smaller parts become an array with only one element, which means that it is already sorted. Then it is compared with the element from the right part, and the smaller goes to a temporary array. [This is happening at the last level of recursion.] Before the last one, the problem is bigger, with two elements in the array[you have to arrays, one from the left part, the other from the right one], which are sorted. Comparison occurs again, and so on.

QuickSort algorithm
The principle of this one is to find a &quot;pivot&quot; element that will be put at the proper position in the array. For example you have: 6 3 2 8 1 4
You take 6 as pivot. The condition will break when you reach 8 with one counter and 4 with another, so you swap them and 8 will be located in the sorted position
...

void qs(int a[],int n)
{
int k; // index of pivot
if ( n != 0 )
{
k = partition(a,n);
qs(a,k);
qs(a+k+1,n-k-1);
}
}

int partition(int a[],int n)
{
int q = 0, w = n-1, pivot = a[0];
while ( i <= j )
{
while(a[q] <= pivot)
q ++;
while(a[w] > pivot)
w --;

if ( q < w )
swap(a,q,w); // swaping two elements
}
swap(a,0,w);
return w;
}
Best Regards,

aphrodita@mail.krovatka.ru {uiuc rules}

http://www.hellforge.org