Best way to sort an array from least to greatest?

[Coconut]

Whats the best way I could go about doing this? I know I'll have to go thru a loop to test whether each element is less than another, but Im kinda confused about how the algorithm would go. Thanks.

[kedaman]

the generally fastest way is quicksort, insertion sort is useful for short arrays, heapsort, mergesort, radixsort, buckestsort and shellsort can be useful for certain things.
quicksort is a recursive algorithm, you start by choosing a pivot, usually the median of 3 (the leftmost, rightmost and middle elements), and then move all elements larger than the pivot right of the pivot and all elements smaller than the pivot left of it, then quicksort each of these unsorted partitions, as small arrays insertion sort is more efficient, you should use a cutoff at 10 elements when you switch over to insertionsort.

[parksie]

In C++, easiest way is just to use the supplied tools:

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int timmah[] = { 4, 3, 7, 2, 1, 4, 5, 8, 3 };

    sort(timmah, timmah + 9);
}

std::sort works with any array-style STL container, or indeed a raw C-style array.

[jim mcnamara]

The qsort() function is used in C, std::sort() in C++.

Usually, because of the flexibility of these two, you do not have to write your own sort algorithm - unless you're in Prgoamming 101.

If that's the case, do a search here for bubble sort

[CornedBee]

What's insertion-sort? qsort() uses bubble-sort for the small remainders.

[kedaman]

I think you mean insertion sort, bubble sort is crazy.
insertion sort iterates from left to right, keeping the left partition sorted by inserting the next element at the right place:
6,3,7,9,1,2
6 | 3,7,9,1,2
3,6 | 7,9,1,2
3,6,7 | 9,1,2
3,6,7,9 | 1,2
1,3,6,7,9 | 2
1,2,3,6,7,9
the algorithm runs at quadratic time

[Coconut]

I just used sort, contained in algorithm. It worked well enough for the simple project I was doing, so thanks again.

[CornedBee]

Originally posted by kedaman
the algorithm runs at quadratic time

Doesn't bubble do that too?

Anyway, VC++7's qsort uses insertion sort for small arrays, alright.
VC++6's too (is the same).

Hmm, I was quite sure they used bubble, don't know why.

[kedaman]

yep, but insertion sort is fastest of those and bubblesort needs tons of swaps to get anything done

[CornedBee]

Ok, so both have O(n^2) but insertion sort has the smalles O?

[kedaman]

O() only tells you the type of proportionality so all terms with lower growth rate and all coefficients are discarded. I don't know the exact analysis for those sorts though..

[Darkwraith]

Actually, the radiax sort has the best all round speed with a O(n). The actual efficiency, however, is dependent on computer speed and programming skill.

Insertion, Bubble, and selection sorts all have a O(N^2) which are great for simple problems.