23 replies to this topic

[MathX]

I have never done any kind of sorting before.

#include <cstdlib>

#include <iostream>

#include <iomanip>

using namespace std;


int main(int argc, char *argv[])

{

const int m=12;

int i,j,k, A[m] = {3,4,-2,5,6,-9,9,8,10,24,76,1};


cout << "A = {";

for (i=0;i<m;i++)

{

  cout << " " << A[i];

}

cout << "}\n\n";


for (i=0;i<m;i++)

{

  for (j=i;j<m;j++)

    if (A[i] < A[j])

    {

    k=A[i];

    A[i] = A[j];

    A[j] = k;

   }

}


cout << "Sorted A = { ";

for (i=0;i<m;i++)

  cout <<  " " << A[i];

  cout << " }\n";



system("PAUSE");

return EXIT_SUCCESS;

}

Can u guys tell me how that code really works, especially this part:

k=A[i];

A[i] = A[j];

A[j] = k;

Thank you all in advance!
MathX

[WingedPanther]

k=A[i];
A[i] = A[j];
A[j] = k;

This is the swap code. It swaps the values stored in A[i] and A[j].
The double loop goes through the array and if it finds a pair of elements that are out of order, swaps them. Since the inner loop starts from the current position in the outer loop, the effect is to move the smallest value to position 0, next smallest to position 1, etc.

This is a piece of code where it is DEFINITELY worth tracing through it by hand to see what it's doing.

[Mathematix]

Also review the 'Bubble Sort' algorithm.

[dargueta]

I wouldn't spend too much of my time learning the bubble sort if I were you. Yes, it's simple, but it's incredibly inefficient and is pretty much only used to teach novice programmers about sorting.

Sorting Algorithms
(Scroll down to "Summaries of Popular Algorithms")

The algorithms listed there have pretty good explanations, and pseudocode, so you can implement them yourself once you think you're ready.

Edited by dargueta, 15 August 2009 - 06:16 AM.
Typo

[Mathematix]

dargueta said:

I wouldn't spend too much of my time learning the bubble sort if I were you. Yes, it's simple, but it's incredibly inefficient and is pretty much only used to teach novice programmers about sorting.

That's just bizarre advice!

If something it simple to learn and you don't yet have that knowledge, wouldn't you have something to gain by actually bothering to learn relevant material?

If MathX understood even simple sorting algorithms they would have been able to analyse the code themselves. :rolleyes:

dargueta said:

Sorting Algorithms
(Scroll down to "Summaries of Popular Algorithms")

The algorithms listed there have pretty good explanations, and pseudocode, so you can implement them yourself once you think you're ready.

Or even better...

Sorting Algorithms

Never ever try to skip knowledge. It makes for bad programmers.

[dargueta]

I think it's sound advice. There's a difference between spending enough time, and too much time. Yes, it's a good place to start, but don't dwell on it.

I find it amusing that the first link in the "recommended links" section is the one I posted...

[Mathematix]

dargueta said:

I think it's sound advice. There's a difference between spending enough time, and too much time. Yes, it's a good place to start, but don't dwell on it.

I find it amusing that the first link in the "recommended links" section is the one I posted...

Well, spending enough time would be spending the time required to understand the code and what it is doing. Anything less is pointless. I'm not saying to learn every algorithm out there regarding sorting algorithms, but at least be able to know what the code is doing and why it was coded that way.

Isn't that what programmers do?

[dargueta]

Quote

Well, spending enough time would be spending the time required to understand the code and what it is doing.

Agreed.

Quote

I'm not saying to learn every algorithm out there regarding sorting algorithms

Neither am I...

Quote

be able to know what the code is doing and why it was coded that way.

Yep.

Quote

Isn't that what programmers do?

Not at all. ;)

[MathX]

WingedPanther said:

k=A[i];

A[i] = A[j];

A[j] = k;

This is the swap code. It swaps the values stored in A[i] and A[j].
The double loop goes through the array and if it finds a pair of elements that are out of order, swaps them. Since the inner loop starts from the current position in the outer loop, the effect is to move the smallest value to position 0, next smallest to position 1, etc.

This is a piece of code where it is DEFINITELY worth tracing through it by hand to see what it's doing.

Thanx a lot :)

I DEFINITELY traced through it by hand, and it really helped me understand it even better :).

@dargueta & Mathematix: Thank you both, but I am new to C++ so...I must go through things slowly.

[dargueta]

That you should. How long've you been programming?

[MathX]

I have been doing VB6 for a while, now that I have registered at uni (we learn Java there) I am trying to learn more about C++ and JAVA :)

[dargueta]

Yeah, VB6 was also my first language. I haven't done anything in it in years, though. Java is useful, but it doesn't allow you as much control over everything as C/C++ do. Looks like you're off to a good start.