Solved

Sorting individual integers

Posted on 2004-08-26
7
282 Views
Last Modified: 2010-05-18
I was wondering, what is a good way to sort through multiple ints and place them into ascending order.

Currently, they are individual values stored as ints.

In the end, after they are sorted, I want to write them into a string in ascending order.

Thank you for your assistance,
Tyson Edwards
0
Comment
Question by:theravibes
7 Comments
 
LVL 55

Expert Comment

by:Jaime Olivares
Comment Utility
I guess this is a homework, so let's go step by step. I hope other experts don't give a full-solution in one post.

First of all, you need to store your numbers in an array. Something like:

int myArray[10];

Now you can fill it with any method. Let's do it directly:

myArray[0] = 5;
myArray[1] = 36;
myArray[2] = 12;
...
...
myArray[9] = 8;   /* notice that 9 is the greatest index */

To traverse an array you will need a for...loop:

int i;
for (i=0; i<10; i++) {
    printf("%d ", myArray[i]);
}

0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
#include <stdlib.h>

void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
0
 
LVL 55

Expert Comment

by:Jaime Olivares
Comment Utility
One of the most traditional and easiest ways to sort an array is the bubble method. Here is the recipe.

- Use a for loop to traverse the array, but only to last-1
- Compare current item with next item: array[i] with array[i+1]
- If the current item is greater than next item then swap values (tip: use a temporary variable to help swap)
- Repeat all previous step until no swap is mad (tip: use a "flag" variable, activate it when a swap is made)

0
Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

 

Author Comment

by:theravibes
Comment Utility
no, this isnt a homework project...

I have been trying to teach myself C, although one of the books that I am going from doesnt seem to make the most sence when it comes to bubble sorting and qsort, so I was wanting to get an example in hopes that it can make some sence.
0
 
LVL 4

Accepted Solution

by:
pankajtiwary earned 500 total points
Comment Utility
You need to go step by step. First you have to make a container or bin where you can store the numbers initially in any order and then in the sorted order. The elements you have are all homogenous i.e. ints, so you can peacefully choose to keep them in an array. Now you need to fill the array with your numbers. example lets say you have 5 numbers 3, 6, 2, 4, 1. So you need to create an array of size such that the capacity should be at least equal to the maximum number of elements because remember you can't change the size of the array once it is fixed. Also you have tyo keep track of the number of elements in that array because there is no way you can find out the number of elements in the array unless you explicitly keep track of it. You can define the array as int arr[5] (we are assuming here for simplicity a maximum of 5 elements) and the number of elements as int n which would initially be zero because the array is empty.

So far so good, the preparation is done. Now you have to fill the array with the elements and remember as soon as you put one element in the array, you have to increase the count of elements i.e. the value of n by one.

There are 2 ways now to fill the array. Either you know before hand how many elements are going to be in the array and you fill the array within the code itself. This is known as the static initialization of an array. The second method could be asking the users to enter the number. Since this is just an example, we can use the static initialization and the interactive input from the user, you can do as an exercise. So, here we go.

int arr[5] = { 3, 6, 2, 4, 1 } ;
int n = 5 ;

Now you need to sort the array. There are lots of methods available for sorting numbers.  You can read any book on algorithms to have a feel of that. But for the time being you can use the excellent qsort() provided with standard library (correct me if I am wrong). The prototype for qsort is

void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

This declaration is from stdlib.h. Since this function is a quite generic one and can be used to sort any type of elements even user defined data types and structs, it takes the name of the array to sort as a void*. Second argument is the number of elements in that array which you will pass as n. The third argument is the size of one element. The function needs this information because it doesn't know what kind of elements are there to sort. We can pass sizeof(int) as this parameter as all our elements are int. The final arguments the the name of the function which will be used for comparing two elements. The function needs to know this too because for user defined types it has no idea what do you mean by greater or less. For this we need to write a function named compare() which will decide about greater or less nomenclature according to your wish.

int compare(const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

Now you simply call qsort() with appropriate parameters and the array will be sorted before you in no time.

qsort ( arr, n, sizeof(int), compare ) ;

after this call the array is sorted and you can print the elements of the array in a for loop to the standard output or a file or a string anywhere you want. To output the numbers in ascending order in a string first you have to create the string.

char str[100];

Then you have to call sprintf() which acts more or less like printf but it prints the output in a string. So, here you go...

int i ;

for ( i = 0 ; i < n ; i++ )
    sprintf ( str , "%d " , arr[i] ) ;

Now the numbers in ascending order are there in the string. You can do whatever you want to do with them.

A note to experts, the o/p wanted to see an example so he could understand the way. I hope I have taken an example and try to go with that with a view to make the o/p understand how to write the code. I hope I have not violated any rules.

The o/p is asked to make appropriate changes according to his/her desire and do his own coding based on what he/she could understand. In case of any doubt, he/she is most welcome.
0
 
LVL 55

Expert Comment

by:Jaime Olivares
Comment Utility
Ok, I will continue with the Bubble sort example, according to my recipe:


int i;
int flag = 1;
int temp;

do {
    flag = 0;
    for (i=0; i<9; i++) {                       // for loop up to max element - 1
        if (myArray[i]>myArray[i+1]) {    // The comparison
            temp = myArray[i];
            myArray[i] = myArray[i+1];    // the swaping operation using temp variable
            myArray[i+1] = temp;
            flag = 1;                               // signaling flag to make a new pass
        }
    }
} while (flag==1);       // repeat if any swap has been made

Hope there are not error. Good luck,
Jaime.
0
 
LVL 45

Expert Comment

by:sunnycoder
Comment Utility
Hi Tyson,

>what is a good way to sort through multiple ints and place them into ascending order
This depends entirely on the type of data you have, how you get the data, and the requirements for your application... To illustrate this point, let us consider a few examples

1. assume you have 10 integers in the range of 0 to 19. You need to sort them as fast as you can even at the cost of some extra memory. Ordinarily the fastest sorting methods are bounded to take a minimum of O(n log n ) time where n is the size of your input. Here however, it is possible to do it in O(n).

You can declare an array of 20 ints (you can use shorts or char too for saving the memory)
int arr[20];

set all elements to 0
for ( int i=0; i<20; i++ )
        arr[i] = 0;

next for all the integers you have, set the corresponding value to 1
int a;
for ( int i=0; i<10; i++)
{
          scanf ("%d", &a);
          arr[a] = 1;
}

Now to print the sorted order, all you need to do is traverse the array and print the indices that are 1

for ( int i=0; i <20; i++ )
{
       if ( arr[i] )
           printf ("%d ", arr[i]);
}

However, in most pratical applications, we are not fortnate enough to afford double memory as compared to data set size or be able to have a bound on the range of values. There are sometimes other complications such as we are given a data set and we have to sort in place or we can take only constant amount of memory irrespective of the data set size.

These contraints force us to explore more algorithms and rethink to tailor them for our applications.

Some of the popular (academically) sorting algorithms for beginners are
- Bubble sort
- Heap sort
- Insertion sort
- Merge sort
- Quick sort
- Selection sort
- Shell sort
- Radix Sort

Check these links for explanation for these algorithms, their analysis, and a demonstration of how they work
http://linux.wku.edu/~lamonml/algor/sort/sort.html
http://cs.smith.edu/~thiebaut/java/sort/demo.html
http://atschool.eduweb.co.uk/mbaker/sorts.html

I recommend this book for further study
http://www.amazon.com/exec/obidos/tg/detail/-/0262032937/103-8849165-8075000?v=glance

good luck
sunnycoder
0

Featured Post

Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

Join & Write a Comment

Suggested Solutions

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now