Sorting Algorithm - How do i improve?

[SargeRX8]

Procedure SelectSort (VAR array : ARRAY OF REAL);

VAR
        	i, j, indexMax: CARDINAL;
	temp : REAL;
BEGIN
	indexMax:=HIGH(array);
        	FOR i := 0 TO indexMax-1	DO
           	FOR j := i + 1 TO indexMax	DO 
                  		IF (array[j] < array[i])	THEN
                       		temp := array[i];
				array[i] := array[j];
				array[j] := temp;
	     		END;
			END;
	     
             	END;
END SelectSort;

This here is a piece of code from a terrible language. Modula2. Anyway this is the code i got and ive been asked to improve it so that the sort does less data moves. I cant figure out how to do it. The way id do it is just to write an extra procedure to make the swap thing happen somewhere else....but that would just be the same thing..

Any ideas?

You dont need to know Modula2 to be able to work with this crud. Its really similar to VB and Java

[chemicalNova]

Not knowing the language I can't offer any proper help. How are you supposed to have less data moves? Even a swap function would do exactly whats there already.. Unless you can do something like..

array[i] := array[j] := array[i];

..and it evaluates it the way you want.. but even then, the behind-the-scenes actions would do what is above.

chem

[KeyDecoder]

What you have is basically a brute force sorting algorithm. It has what is described as O(N^2) complexity (which means it runs through the list N*N times where N is the size of the list). Its also best case O(N^2), average O(N^2) and worst case O(N^2) since it always brute forces it's way through.

What you need is to implement a sorting algorithm that has a better best case and average case complexity.

Check this page out and basically pick one that looks easy to implement in your language. Bubble sort is pretty easy I think.

http://en.wikipedia.org/wiki/Sorting_algorithm

[chemicalNova]

I thought he was required to re-write the selection sort algo .. not implement a different algo altogether..

chem

[SargeRX8]

Ive figured it out. I got a hint which i thought might work and it worked. The modified code below. This new modification i done to it makes it i recon abit more efficient such that it does somewhat less swaps than the original piece of code.

Procedure SelectSort (VAR array : ARRAY OF REAL);

VAR
        	i, j, indexMax, min: CARDINAL;
	temp : REAL;
BEGIN
	indexMax:=HIGH(array);
        	FOR i := 0 TO indexMax-1	DO
		Min:=I;
           	FOR j := i + 1 TO indexMax	DO 
                  		IF (array[ j ] < array[min])	THEN
                       		Min:=j;	
	     		END;
			END;

	temp := array[i];
	array[i] := array[min]; Was a j
	array[min] := temp; Was a j

             	END;
END SelectSort;

Cant wait til i get into C and the family alike. So sick of these "great educational languages". When i first started coding, it was straight to java and VB6, then VB.net. This here, modula2, is a waste of time. Thanks for the support guys. Its good to see that there are always a couple of people who are keeping this part of the forum active. il be getting abit more active as time goes. More i learn, more i got to share.

Anyone here consider a group project?

[chemicalNova]

Stolen straight from wikipedia.. if memory serves thats taken from the C++ implementation on there

I don't see how that uses less cycles. In fact, it probably uses more than your original code.. be interesting to see what your tutor says about it.

..ahh, these forums are a godsend for me. Theres only so much I can put up with the foreign people on vbforums.com that can't really express what their problem is.. most of my replies starts with "I don't quite understand your problem" then I spew out about 10 different ideas I could gather from their thread..

Group project? Like what?

chem

[nightmaRe]

That looks like it would do the exact same ammount of cycles.... infact it does use the same number of cycles AND uses an extra variable... and wow at chem's rep power... it should start a second line and eventually change colour to yellow :P
I'll give him my +2 for helping the coding community so much.
And on the rare occasion Chem doesnt know something about programming (lol not gonna happen...) I'll step in and try help
I think we're actually doing the same sort of course, but im stuck with cHs and his inability to code.. :P

Edit: can only give him +1 cause im so awsome

[chemicalNova]

lol.. if I'm anything.. I'm a dud compared to khaless and keydecoder. They do it as a profession! (I will be soon.. once I've finished school!)

chem

[chX]

I've never even heard of Modula2... LOL.

Seriously, we all need to use that LOL code that Coffex posted a while back.

KTHXBYE.

[SargeRX8]

Modula2 i believe is based on Pascal or something or rather. I showed it to my tutor and landed full marks -.-

I didnt get it from wikipedia, i was looking thru some of my notes and i read something about doing something to something. The teacher laughed at me coz when i explained how i done it he sed "why didnt you just take it from my lecture notes?"

GG to not attending lectures.

[nightmaRe]

it may just be the language but looking at what youve written shows me you have just made another variable to store what you allready had.. meh CBF! Just spent a whole day coding... Gheyness..
Yeah Chem I'll be pro too in 1 and a half years when im finished my course..
(pro = Qualified Pro....)

[fluent]

My mate is just about to complete his degree in Mathematics and Information Technology/Software Design. None of this makes sense to me, but it might to you...

rofl lol l2sort noob

change swapping to use xor if modla2 can do it, cos its ****

change algorithm to beta sortingness, like bubblesort if u can do it lol

fluent

[chemicalNova]

Is it just me or is your friend retarded? Bubblesorting is one of the worst/slowest algo's around.

chem

[chX]

Somehow... I read bubblesort... I simultaneously thought of a bubble bath, Ice Tea and yoghurt... and then I saw an image of Chem in a bubble bath drinking ice tea and yoghurt.

[KeyDecoder]

Originally Posted by chemicalNova

Is it just me or is your friend retarded? Bubblesorting is one of the worst/slowest algo's around.

chem

Actually the Selection Sort (the one that SargeMX has) is the worst since it always has for O(N^2) complexity, so it always runs over the list N*N times.

But Bubble Sort can technically in a best case scenario only have O(N) complexity which means it may only run over the list N times (best case means that the list is already sorted).

Technically they are both crap, you need a quicksort or insert sort to really be effective (or beyond that you can start looking into trees and other fun stuff that computer science students get nutty about).

Oh and SargeMX's original algorithm is a half-arsed selection sort, and his revised is the actual selection sort and it is actually slightly better, it still has O(N^2) complexity technically, but may do less swap operations since the 'min' value will move up in the array faster than the 'i' value.

[KeyDecoder]

Originally Posted by fluent

My mate is just about to complete his degree in Mathematics and Information Technology/Software Design. None of this makes sense to me, but it might to you...

Maths and IT/Software Design, sounds a like a reasonable sort of degree to have I guess. Shame the best he can write is:

Originally Posted by someguy

rofl lol l2sort noob

change swapping to use xor if modla2 can do it, cos its ****

change algorithm to beta sortingness, like bubblesort if u can do it lol

Should have added an English subject to it as well.

[SargeRX8]

hahahahahhahaha keydecoder, kick ass reply imo

[chemicalNova]

Still, saying a bubblesort would be faster is an assumption.. if the list isn't already ordered or its by chance almost completely in order anyway, then its useless compared to the rest.. am I wrong?

chem

[KeyDecoder]

Originally Posted by chemicalNova

Still, saying a bubblesort would be faster is an assumption.. if the list isn't already ordered or its by chance almost completely in order anyway, then its useless compared to the rest.. am I wrong?

chem

Yes, thats actually wrong. Some algorithms will still iterate over the list the same amount of times even if the list is already sorted. A select sort will run over the list the same amount of times, even if the list is already sorted. However a bubble sort will only iterate over the list once if already sorted.

This is why algorithms are generally compared using the three different scenarios, best case, average case and worst case. For sorting, best case is when the list is already sorted, average is basically half sorted and worst case is if the list is already sorted backwards. These are thought of in terms of complexity or how many times something will theoretically iterate over the list.

An algorithm which has the same best,average and worst case complexity is always going to be crap since there is no chance of it being faster in any case. Generally these sorts of algorithms are simple to implement and fast to run anyway, so work well for small lists.

This algorithm complexity stuff is probably useful for you to learn Chem, since if you ever write a 3D game engine, this is the sort of stuff you'll probably want to know about, only you'll be applying it in the form of evaluting BSP trees implementation and other complex algorithms.