Title: Sorting Algorithms
Description: Week 2: Selection Sort
BloodGhst - April 30, 2004 08:38 PM (GMT)
This post can also be found in the first sorts thread. Myork pointed out that it'd be better to put each week into a new thread, so I decided to make a new thread for it. Here it is:
For this week I'll move onto the selection sort. The selection sort is another simple algorithm. Look through the unsorted elements of the list and find the minimum element and swap with the first unsorted element until all elements have been sorted. Here's the code for the sort:
| CODE |
void SelectionSort(int* elems, int numElems)
{
int minIndex;
int minVal;
for(i=0; i < numElems - 1; ++i)
{
minIndex = i;
minValue = elems[i]
for(j=i + 1; j < numElems; ++j)
if (elems[j] < minValue)
{
minIndex = j;
minValue = elems[j];
}
swap(elems[i], elems[j]);
}
}
|
A few things about the sort:
Best Case sorting time: O(n^2)
Stable: No
This sort doesn't have a best/worst case time. The time it takes to sort a list completely is always O(n^2). So, if this sort is always going to run slowly, why bother use it at all? Well, it's useful to find the top or bottom m elements, where m<<n (m is signicantly less than n), and you don't care about stability. Also, it's one of the foundation sorts that some of the other more complex algorithms fall back upon. The Shell sort is one such sort.
Again, if there are any ideas on improving the algorithm, don't be shy to share them. Please, keep the improvements to the algorithm and don't be caught up in small optimizations.
Incubator - May 2, 2004 12:23 AM (GMT)
looks quite similar to a bubblesort imo
myork - May 3, 2004 01:35 PM (GMT)
| QUOTE |
| looks quite similar to a bubblesort imo |
I concur with that.
That only difference seems to be the bubble sort optimisation that turns it from
O(n^2) into O(n.log(n))
KTC - May 3, 2004 02:07 PM (GMT)
Yeah, if you ever had the joy of first hearing it from a rather crap lecture like I did (Disclaimer: I'm sure he's very knowledgeable... ;)) then one might have thought that selection sort is another name for bubble sort <_<
BloodGhst - May 4, 2004 05:24 AM (GMT)
You are right that the two are quite similar, but they both have different uses. The primary difference is one looks for the max, and the other just looks at two adjacent elements in an array. If you look at the inner loop, the difference is a little more obvious:
| CODE |
for(int cnt2 = 0; cnt2 < cnt1; ++cnt2)
{
flipped = false;
if(nums[cnt2 + 1] < nums[cnt2])
{
dummy = nums[cnt2];
nums[cnt2] = nums[cnt2 + 1];
nums[cnt2 + 1] = dummy;
flipped = true;
}
}
if(!flipped)
return; |
| CODE |
minIndex = i;
minValue = a[i]
for(j=i + 1; j < numElems; ++j)
if (a[j] < minValue)
{
minIndex = j;
minValue = a[j];
}
swap(a[i], a[j]);
|
The speed of the selection sort really comes from the number of swaps being done, or the lack of swaps. With the bubble sort, there's the potential for a swap every iteration of the inner loop. With the selection sort, there is garunteed to be only one swap per iteration of the outer loop.
namso - May 4, 2004 05:52 AM (GMT)
hi i'm new in this topic and guess u guys have been discussing these algo for sometime.
Tell me where did u define this array a[]
and u haven't used the pointer *elems
whats that for?
BloodGhst - May 4, 2004 08:24 AM (GMT)
^ You actually caught an error in my programming; a[] is supposed to be elems[]. I'll make a change to that right away. Thanks.
namso - May 4, 2004 12:59 PM (GMT)
great i could be a help to someone ;)
namso - May 7, 2004 11:32 AM (GMT)
hey the week is about to end what happend to other sort?
KTC - May 7, 2004 01:54 PM (GMT)
| QUOTE (namso @ May 7 2004, 11:32 AM) |
| hey the week is about to end what happend to other sort? |
Come on, give the person a chance ;)
BloodGhst - May 10, 2004 09:31 AM (GMT)
Sorry for taking a while to get the new sort posted. I visit my girlfriend in a different city on the weekends, and the place I stay doesn't have very good internet access. Please be patient, I'll try to get them up before I leave on Fridays, but I may not be able to. This also means that don't expect any clarifications/ corrections on my part throughout the weeknd.
