Thread: ordering variables

  1. #1
    Registered User
    Join Date
    Feb 2002
    Posts
    465

    ordering variables

    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.
    I came up with a cool phrase to put down here, but i forgot it...

  2. #2
    Registered User
    Join Date
    Nov 2002
    Posts
    1,109
    if you mean putting the values of the variables in an array in order from greatest to smallest...

    for loop, then if statement

  3. #3
    Registered User
    Join Date
    Feb 2002
    Posts
    465
    ok, this is what i want:

    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....
    i have no problem finding the highest value, but i get stuck when i try to exclude that value from the next search.

    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:

    Code:
    array[0] goes by 'label 1'
    array[1] goes by 'label 2'
    and if array[1] is larger than array[0] i want them to output with their labels connected, like:

    Code:
    output:
    
    1. (value in array[1]) label 2
    2. (value in array[0]) label 1
    Last edited by ...; 11-08-2002 at 04:56 PM.
    I came up with a cool phrase to put down here, but i forgot it...

  4. #4
    Registered User
    Join Date
    Feb 2002
    Posts
    465
    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...
    I came up with a cool phrase to put down here, but i forgot it...

  5. #5
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    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).
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  6. #6
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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

  7. #7
    &TH of undefined behavior Fordy's Avatar
    Join Date
    Aug 2001
    Posts
    5,793
    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
    Code:
    #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;
    	
    }
    Using a std::vector with highest lowest sorting

    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));	
    }

  8. #8
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Bubble sort is probably the best for a small array. Basically you need two for loops, one nested in the other.
    This depends on the compiler but I would choose insertion
    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.

  9. #9
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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 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!
    Last edited by PJYelton; 11-08-2002 at 08:51 PM.

  10. #10
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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.

  11. #11
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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! 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!

  12. #12
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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).
    I don't see any advantage other than selection sort
    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.

  13. #13
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    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
    Hmm, I thought bubblesort were something like this:
    Code:
    while(Unsorted())
    {
       for(i=1; i<LengthOfList; i++)
       {
          if(ValueOf(i - 1) > ValueOf(i))
          {
             Swap(i, i - 1);
          }
       }
    }
    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...
    Could be wrong though.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  14. #14
    Just a Member ammar's Avatar
    Join Date
    Jun 2002
    Posts
    953
    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

  15. #15
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Hmm, I thought bubblesort were something like this:
    Both are bubble sorts. These are the simple sorting algorithms
    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;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. basic question about global variables
    By radeberger in forum C++ Programming
    Replies: 0
    Last Post: 04-06-2009, 12:54 AM
  2. Replies: 15
    Last Post: 09-30-2008, 02:12 AM
  3. esbo's data sharing example
    By esbo in forum C Programming
    Replies: 49
    Last Post: 01-08-2008, 11:07 PM
  4. Replies: 6
    Last Post: 01-02-2004, 01:01 PM
  5. functions to return 2 variables?
    By tim in forum C Programming
    Replies: 5
    Last Post: 02-18-2002, 02:39 PM