Printable View
what is the most efficient means of putting an array of variables in order from greatest to smallest? i have been laboring for at least a day or two over this trying to get the most simple and practical way possible. the way that i have right now is large, non-functional, and not worth looking at.
i dont need code, just a general concept would suffice.
if you mean putting the values of the variables in an array in order from greatest to smallest...
for loop, then if statement
ok, this is what i want:
i have no problem finding the highest value, but i get stuck when i try to exclude that value from the next search.Code:
// ok, so this isnt really code. this is just the flow of what i want to do:
make an array of 25
v
v
search for the largest value in the array
v
v
output that value
v
v
search for largest value again, excluding the one ive already used
v
v
output that value
v
v
// etc....
another problem i have is that while i want to display the array in order from largest to smallest, i want the values to stay in the same place in the array, because each block of the array has a static label in my program.
for example:
and if array[1] is larger than array[0] i want them to output with their labels connected, like:Code:
array[0] goes by 'label 1'
array[1] goes by 'label 2'
Code:output:
1. (value in array[1]) label 2
2. (value in array[0]) label 1
sorry salem, i didnt edit in time before you already posted. read my above post again for the other part of my problem.
and ive never used qsort(). explain its use to me please...
You should use a sorting algorithm. There are many to choose from, all having their upsides and downsides: Quicksort, Bubblesort, Shakersort, Insertsort, Selectionsort, Mergesort, Bucketsort, Radixsort, Treeselection, Heapsort, Shellsort etc...
In your case with as few as 25 elements, you could use Bubblesort or Selectionsort, since they are pretty easy algorithms (though slow, but it won't matter so much in your case).
Bubble sort is probably the best for a small array. Basically you need two for loops, one nested in the other. In pseudocode:
Code:for (x=0; x<arraysize-1; x++)
for (y=x+1; y<arraysize; y++)
if array[x]>array[y] then swap the two numbers
qsort is part of the Standard C Library......it allows you to sort data using a comparison function you specify
But if you are in C++, you might as well use the sort template function which is part of the Standard C++ Library...its type safe....works with normal arrays as well as stl containers...and you can still implement a special comparison function;
Using a char array with standard lowest highest sorting
Using a std::vector with highest lowest sortingCode:#include <iostream>
#include <cstring>
#include <algorithm>
int main(){
//Get a char array buffer
char str[] = "qwertyuiopasdfghjklzxcvbnm";
std::cout << str << std::endl;
std::sort(str,str + std::strlen(str));//Use sort
std::cout << str << std::endl;
}
Code:#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
int main(){
std::vector<int> v;//create vector
v.push_back(2);//chuck on some unsorted values
v.push_back(4);
v.push_back(1);
v.push_back(3);
v.push_back(5);
//Print vector to screen
std::copy(v.begin(),v.end(),
std::ostream_iterator<int>(std::cout));
std::cout << std::endl;
std::sort(v.begin(),v.end(),
std::greater<int>());//Use Sort with greater comparison
std::copy(v.begin(),v.end(),
std::ostream_iterator<int>(std::cout));
}
This depends on the compiler but I would choose insertionQuote:
Bubble sort is probably the best for a small array. Basically you need two for loops, one nested in the other.
sort over bubble and selection sort for small arrays. If the data is already sorted or almost sorted, insertion sort will run in linear time.
True, bubble sort definately is NOT the fastest sort, but since on small arrays we are talking miliseconds at the most, I like bubble sort since it only takes like 3 lines to write :D The algorithm book I'm studying goes in depth into merge, insertion, heap, and quick sort, but I'm not sure which one selection sort is. Could you give a quick rundown on it to hopefully jar my memory? No code needed, just a sentence on how it works will do!
Selection sort is when you find the smallest
element of A[2 .. N] and then swap it with A[1] then you
find the smallest element of A[3 .. N] and swap it with A[2] and
so on.
It's O(n^2) but is really easy to understand.
Ok, now I remember which one selection sort is. I'm curious, what are the reasons for choosing that over bubble sort? Seems like more work typing (granted only a little!) but the same speed since both are O(n^2).
My favorite so far is the merge sort. True, recursion is the devil, but I just love the idea of an array splitting itself up, sorting all the pieces, then putting itself back together again! :D Of course, I only know like 5 algorithms and learning more every day in my book, so tomorrow I'll probably have a new cool favorite! :p
I don't see any advantage other than selection sortQuote:
Ok, now I remember which one selection sort is. I'm curious, what are the reasons for choosing that over bubble sort? Seems like more work typing (granted only a little!) but the same speed since both are O(n^2).
uses less swaps. Selection sort will do n - 1 swaps
each time it runs and bubble sort will do O(n^2) swaps, but I doubt it would make that much of a difference.
Besides the ones you've learn, most programmers
know counting sort (used in radix sort),
radix sort, bucket sort and shell sort. I don't understand
shell sort too well other than at the end it does a pass
just like regular insertion sort so it has to sort correctly.
For the others, I'm guessing tree sort
is where you insert all of the values into a tree and then
do a inorder traversal.
Hmm, I thought bubblesort were something like this:Quote:
Originally posted by PJYelton
Bubble sort is probably the best for a small array. Basically you need two for loops, one nested in the other. In pseudocode:
Code:for (x=0; x<arraysize-1; x++)
for (y=x+1; y<arraysize; y++)
if array[x]>array[y] then swap the two numbers
It only swaps the two elements next to each other, making it very unefficient. What you wrote is some kind of selection sort, where you (in the first loop) makes sure element 1 is the smallest element, in the next loop element 2 is the second smallest and so on...Code:while(Unsorted())
{
for(i=1; i<LengthOfList; i++)
{
if(ValueOf(i - 1) > ValueOf(i))
{
Swap(i, i - 1);
}
}
}
Could be wrong though.
I think bubble sort is the easiest algorithm for sorting, but it's very slow, I like the Quick Sort algorithm.
you can't use recursion istead of loops, but I think it's slower.
If search the web for sorting algorithms visualized using Java applets, you'll have nice results
Both are bubble sorts. These are the simple sorting algorithmsQuote:
Hmm, I thought bubblesort were something like this:
Code:#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;
void bubble_sort1(int A[], int n)
{
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
if (A[i] > A[j]) {
int t = A[i];
A[i] = A[j];
A[j] = t;
}
}
}
}
void bubble_sort2(int A[], int n)
{
bool noswap = false;
int i = 0;
while(!noswap) {
noswap = true;
for (int j = i + 1; j < n; ++j) {
if (A[i] > A[j]) {
int t = A[i];
A[i] = A[j];
A[j] = t;
noswap = false;
}
}
i++;
}
}
void selection_sort(int A[], int n)
{
int k;
for (int i = 0; i < n - 1; ++i) {
k = i;
for (int j = i + 1; j < n; ++j) {
if (A[j] < A[k])
k = j;
}
int t = A[i];
A[i] = A[k];
A[k] = t;
}
}
void insertion_sort(int A[], int n)
{
for (int i = 1; i < n; ++i) {
int k = A[i];
int j = i - 1;
while(j >= 0 && k < A[j]) {
A[j + 1] = A[j];
j--;
}
A[j + 1] = k;
}
}
void randomize_array(int A[], int n)
{
for (int i = 0; i < n; ++i) {
A[i] = rand() % 100;
}
}
void print_array(int A[], int n)
{
for (int i = 0; i < n; ++i) {
cout << A[i] << " ";
if ((i + 1) % 15 == 0 && i < n - 1)
cout << endl;
}
cout << endl;
}
int main(void)
{
const int N = 100;
int A[N];
srand(time(0));
randomize_array(A, N);
bubble_sort1(A, N);
cout << "bubble_sort1" << endl;
print_array(A, N);
cout << endl;
randomize_array(A, N);
bubble_sort2(A, N);
cout << "bubble_sort2" << endl;
print_array(A, N);
cout << endl;
randomize_array(A, N);
selection_sort(A, N);
cout << "selection sort" << endl;
print_array(A, N);
cout << endl;
randomize_array(A, N);
insertion_sort(A, N);
print_array(A, N);
return 0;
}