insert sort

saphir55 · #1 05-Dec-2004, 23:37

Hi everyone I am kinda having problems with my insert sort program when I

try to sort a couple of numbers I get some weird results some huge numbers

I may be doing this wrong so please point out how it could be done better.

so her goes:

CPP / C++ / C Code:

#include <stdio.h>



void swap(int *a, int *b){
	int c= *a;

	*a=*b;
	
             *b=c;	
}

void insertsort(int * list, int size) {

	int x,y;
 

	for(x = 0;x < (size-2);++x)


		for(y = x+1;y > 0;--y)


			if(   list[y]  <  list[y-1])


				swap( & list[y], & list[y-1]);
}

 int main(void){

	int i,j;
        
            int g[3];


	for(i = 0; i < 3 ; i++)
	 
	scanf(" % i  ", & g);
 

 for(j = 0; j < 3 ; j++)


	printf(" % i \n", & g);


 insertsort( &g   ,  3);


return 0;

}

thx.

nkhambal · #2 06-Dec-2004, 00:35

Hi saphir55,

First thing first, pls use code tags while posting your code. Read the sticky for new users.

Now to your program.I havent gone through it thoroughly...however following things caught my attention worth noting here..

in main() since you are reading and printing one array element at a time, following loops

CPP / C++ / C Code:

for(i = 0; i < 3 ; i++)
scanf(" % d", & g);

for(j = 0; j < 3 ; j++)
printf(" %d \n", & g);

should be..

CPP / C++ / C Code:

for(i = 0; i < 3 ; i++)
{
scanf(" % i ", &g[i]);
}

for(j = 0; j < 3 ; j++)
{
printf(" % i \n", g[i]);
}

Next since you are passing the array to insersort function you do not actually need "&" operator. Simply passing array as "g" is enough.(&g is also correct though not common).

Pls check your program again after making these changes.

davekw7x · #3 06-Dec-2004, 07:37

Quote:

Originally Posted by nkhambal

Hi saphir55,

First thing first, pls use code tags while posting your code. Read the sticky for new users.

Now to your program.I havent gone through it thoroughly...however following things caught my attention worth noting here..

in main() since you are reading and printing one array element at a time, following loops

CPP / C++ / C Code:

for(i = 0; i < 3 ; i++)
scanf(" % d", & g);

for(j = 0; j < 3 ; j++)
printf(" %d \n", & g);

should be..

CPP / C++ / C Code:

for(i = 0; i < 3 ; i++)
{
scanf(" % i ", &g[i]);
}

for(j = 0; j < 3 ; j++)
{
printf(" % i \n", g[i]);
}

Next since you are passing the array to insersort function you do not actually need "&" operator. Simply passing array as "g" is enough.(&g is also correct though not common).

Pls check your program again after making these changes.

nkhambel: your comments on g and the example to read and print individual elements is spot on, but your input format specifier has problems (did you try it?)

Saphir55: Get the main() going before you try the sort:

First of all, you have superfluous spaces in your scanf statement.
Secondly, you are not reading and writing the individual array elements.

To read a value into g[ i ], use something like

CPP / C++ / C Code:

  scanf("%d", &g[ i  ]);

Then, for debug purposes, immediately print out the value:

CPP / C++ / C Code:

  int i,j;
  int g[3];
  for(i = 0; i < 3 ; i++) {
    scanf("%d", &g[i]);
    printf("You entered %d\n", g[i]);
  }

(Note my personal preference for %d rather than %i for general integer I/O, %i for inputs gives interesting results if you enter something with leading zeros.)

After you convince yourself that the input is working OK, then try to find out what you have to do to make the sort work.

Regards,

Dave

Try thi

saphir55 · #4 06-Dec-2004, 12:36

Ok well thx for the help I managed to make my sort program work using a

different code it is still insert sort however I seem to have incountered

another problem, well I want to sort names with this but I don't seem to get

it work can anyone give me pointers on how to transform this program to sort

names....

here is my new code:

CPP / C++ / C Code:

void insert(int n, int a[]) {
	int i, j;
		int x;

	for (i = 1; i < n; i++) {
		
		x = a[i];
		for (j = i - 1; j >= 0 && a[j] > x; j--) {
			
                         a[j+1] = a[j];
			
		}
		a[j+1] = x;	
	}
}

any help will be apreciated.

davekw7x · #5 06-Dec-2004, 14:00

Quote:

Originally Posted by saphir55

Ok well thx for the help I managed to make my sort program work using a

different code it is still insert sort however I seem to have incountered

another problem, well I want to sort names with this but I don't seem to get

it work can anyone give me pointers on how to transform this program to sort

names....

here is my new code:

CPP / C++ / C Code:

void insert(int n, int a[]) {
	int i, j;
		int x;

	for (i = 1; i < n; i++) {
		
		x = a[i];
		for (j = i - 1; j >= 0 && a[j] > x; j--) {
			
                         a[j+1] = a[j];
			
		}
		a[j+1] = x;	
	}
}

any help will be apreciated.

Your algorithm seems sound (I assume you tested it with several different data sets.)

Now you can use exactly the same technique for sorting strings, but first you have to define how strings are represented.

Now, there is no such thing as a string data type in C, but there is a universally used convention that a string is represented by an array of char with 0 in the last element of the string.

So a bunch of strings could be stored in a 2-dimensional array of char, or each string's address could be stored in an array of pointers to char. This second method is what I have chosen for this example

Here's what the main program would look like for a test case:

CPP / C++ / C Code:

#include <stdio.h>
#include <string.h>

int main()
{
  void insert_str(int n, char *arry[]);

  int n;
  char *strparry[10] = {"Dave", "Harry", "Alice", "Zaphrod", "Elvis",
                        "Richard", "Elton", "Irving", "Syzygy", "Hiram"};

  int i;

  n = sizeof(strparry)/sizeof(strparry[0]);

  for (i = 0; i < n; i++) {
    printf("strparry[%2d] = %s\n", i, strparry[i]);
  }
  printf("\n");

  insert_str(n, strparry);

  for (i = 0; i < n; i++) {
    printf("strparry[%2d] = %s\n", i, strparry[i]);
  }
  printf("\n");

  return 0;
}

Note the initialization of the array of pointers to char. Note the prototype and calling sequence for the insertion sort routine.

In this example, I have initialized the pointers to point to string literals (constants), but you could have pointers pointing to arrays of char, perhaps dynamically allocated (with malloc()), as the user enters the names. Whatever.

I will give a method of sorting that does not require copying strings from one place to another, so it works with this example.

Now, note that in this scheme, we will not actually move the strings around; we will sort the array of pointers so that the first pointer points to the "smallest" string (as determined by strcmp), and the last pointer points to the "biggest" string.

In the insertion sort function, x will be a pointer to char, not an int, and the loop function will be something like

CPP / C++ / C Code:

    for (j = i - 1; j >= 0 && strcmp(a[j], x) > 0; j--) {

The only other change required in your function (other than changing the argument type) is to declare x to be a pointer to char, rather than an int as it was in the integer sort function.

Try it!

Regards,

Dave

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Merge sort on a linked list	Temujin_12	C++ Forum	1	06-Mar-2008 20:33
help with Sort arrays/Size	justachessgame	C Programming Language	1	12-Nov-2004 23:46
Insert problem in linked list with two function code	Kay Chan	C++ Forum	1	03-Sep-2004 09:52
insert data into database	jilshi	Web Design Forum	0	29-Apr-2004 22:47
urgent help needed :c + mysql insert	jack	C Programming Language	1	13-Apr-2004 21:16