insertion sort in C

A

arnuld

It works fine. The Ullman's book does not have the check for (j > 0) in
inner loop which I have put myself. Any advice for improvement ?

One thing I don't get is how it is less expansive than bubble sort, we
have 2 loops and we exchange values and we do it only once. The only
difference is bubble starts for the bottom while insertion sort start
from the top but numbers of iterations are same.



/* A C program to learn insertion sort algorithm
*
* VERSION 0.0
*
*/

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

void sort_insertion(char* );

int main(void)
{
char arrc[] = "kandr";

printf("array(unsorted): %s\n", arrc);
sort_insertion(arrc);
printf("array(sorted): %s\n", arrc);


return 0;
}


void sort_insertion(char c[])
{
size_t i,j;
const size_t s = strlen(c);

if( 0 == s )
{
printf("oops!, nothing to sort\n");
return;
}

/* leave the first element for comparison, basis of insertion sort */
for(i = 1; i != s; ++i)
{
for(j = i; (j > 0) && (c[j] < c[j - 1]); --j)
{
char temp = c[j];
c[j] = c[j - 1];
c[j - 1] = temp;

}
}
}

=================== OUTPUT ==================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra insertion-sort.c
[arnuld@dune programs]$ ./a.out
array(unsorted): kandr
array(sorted): adknr
[arnuld@dune programs]$
 
U

user923005

It works fine. The Ullman's book does not have the check for (j > 0) in
inner loop which I have put myself. Any advice for improvement ?

One thing I don't get is how it is less expansive than bubble sort, we
have 2 loops and we exchange values and we do it only once. The only
difference is bubble starts for the bottom while insertion sort start
from the top but numbers of iterations are same.
Click to expand...
Read this:
http://www.cse.unr.edu/~bebis/CS477/Lect/InsertionSortBubbleSortSelectionSort.ppt
[snip]
 
U

user923005

It works fine. The Ullman's book does not have the check for (j > 0) in
inner loop which I have put myself. Any advice for improvement ?

One thing I don't get is how it is less expansive than bubble sort, we
have 2 loops and we exchange values and we do it only once. The only
difference is bubble starts for the bottom while insertion sort start
from the top but numbers of iterations are same.

/* A C program to learn insertion sort algorithm
 *
 * VERSION 0.0
 *
 */

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

void sort_insertion(char* );
Click to expand...

Suggestion code generically and use a typedef:

void sort_insertion( e_type[], size_t n );
int main(void)
{
  char arrc[] = "kandr";

  printf("array(unsorted): %s\n", arrc);
  sort_insertion(arrc);
  printf("array(sorted):   %s\n", arrc);

  return 0;

}

void sort_insertion(char c[])
{
  size_t i,j;
  const size_t s = strlen(c);

  if( 0 == s )
    {
      printf("oops!, nothing to sort\n");
Click to expand...

This is a mistake. Sorting 0 or 1 items is not much work, but
perfectly valid.
      return;
    }

  /* leave the first element for comparison, basis of insertion sort */
  for(i = 1; i != s; ++i)
    {
      for(j = i; (j > 0) && (c[j] < c[j - 1]); --j)
        {
          char temp = c[j];
          c[j] = c[j - 1];
          c[j - 1] = temp;

        }
    }

}
Click to expand...

Perhaps something along these lines:

#ifdef USE_INTEGER
typedef int e_type;
#define GT(a,b) (((a) > (b)) ? 1 : 0)
#else
/* Add your other types here... */
#endif

void linear_insertion(e_type a[], size_t n)
{
size_t i,
j;
e_type tmp;

for (i = 1; i < n; i++)
for (j = i; j > 0 && GT(a[j - 1], a[j]); j--) {
tmp = a[j];
a[j] = a[j - 1];
a[j - 1] = tmp;
}
}
=================== OUTPUT ==================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra insertion-sort.c
[arnuld@dune programs]$ ./a.out
array(unsorted): kandr
array(sorted):   adknr
[arnuld@dune programs]$

--www.lispmachine.wordpress.com
my email is @ the above blog.
Click to expand...
 
M

Mark

arnuld said:
It works fine. The Ullman's book does not have the check for (j > 0)
in inner loop which I have put myself. Any advice for improvement ?
Click to expand...

[OT] What is the book you are using? Could you provide its title and
authors? [/OT]
Thanks.
 
J

James Kuyper

arnuld said:
Why use a macro when a function with return type int can do the job ?
Click to expand...

Because the macro will work regardless of the types of a and b, so long
as they are types for which the expression a>b is permitted.
 
K

Keith Thompson

arnuld said:
Why use a macro when a function with return type int can do the job ?
Click to expand...

Valid reasons have been presented for using a macro.

But why use the ?: operator? The above could be written as:

#define GT(a, b) ((a) > (b))
 
U

user923005

Why use a macro when a function with return type int can do the job ?
Click to expand...

Actually, when I write data structures and algorithms, I almost always
use C++ and would use a template.

I actually despise function macros and just typed in something off the
top of my head.

A function call would be better (and the remarks about the simple
comparison being superior to the ? operator are also correct.)
 
A

arnuld

...SNIP..
Click to expand...
Personally, I prefer to use functions for comparisons (when it makes
sense). But advocates of the macro are likely to point out that the same
macro does the trick for any numerical types - float, double, long
double, char, short, int, long, long long, very long, and extremely
long.
Click to expand...


And I heard that this feature is the cause of lots of bugs but the
primary reason I heard is "macros cheat the compiler"

Try this program:

#include <stdio.h>

#define GTF(a, b) int gt_ ## a ## _ ## b(a x, b y) { return x > y; }

GTF(double, double)
GTF(int, unsigned)

int main(void)
{
printf("%d\n", gt_double_double(42.1, 6.1)); printf("%d\n",
gt_int_unsigned(17, 112U)); return 0;
}
Click to expand...

First thing that came to my mind when I saw that code is "comparison
between signed and unsigned (I have little experience with gcc now :)


#include <stdio.h>

#define GTF(a, b) int gt_ ## a ## _ ## b(a x, b y) { return x > y; }

GTF(double, double)
GTF(int, unsigned)


int main(void)
{
printf("%d\n", gt_double_double(42.1, 6.1));
printf("%d\n", gt_int_unsigned(17, 112U));
return 0;
}

==================== OUTPUT ============================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra macro-trick.c
macro-trick.c: In function ‘gt_int_unsigned’:
macro-trick.c:6: warning: comparison between signed and unsigned
[arnuld@dune programs]$ ./a.out
1
0
[arnuld@dune programs]$


A function does the same thing (except we need 2 functions for that) and
they will not be evil: http://www.parashift.com/c++-faq-lite/misc-
technical-issues.html#faq-39.4
 
N

Norm Mann

arnuld said:
It works fine. The Ullman's book does not have the check for (j > 0) in
inner loop which I have put myself. Any advice for improvement ?

One thing I don't get is how it is less expansive than bubble sort, we
have 2 loops and we exchange values and we do it only once. The only
difference is bubble starts for the bottom while insertion sort start
from the top but numbers of iterations are same.
Click to expand...

I believe that your confusion is that you haven't really written an
insertion sort routine, but a highly modified bubble sort. It can be
improved by exiting the loop once the data swaps end.
In essence, an insertion sort is comprised of two operations:
1. finding the insertion point - in large arrays, a binary search is often
used.
2. moving the sorted data until the insertion point is open and moving the
data to be inserted there.
While operation 1. will result in less comparisons for larger arrays,
operation 2. has 1/3 the number of data moves as the data swaps of a bubble
sort (remember - a swap is 3 data moves).
/* A C program to learn insertion sort algorithm
*
* VERSION 0.0
*
*/

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

void sort_insertion(char* );

int main(void)
{
char arrc[] = "kandr";

printf("array(unsorted): %s\n", arrc);
sort_insertion(arrc);
printf("array(sorted): %s\n", arrc);


return 0;
}


void sort_insertion(char c[])
{
size_t i,j;
const size_t s = strlen(c);

if( 0 == s )
{
printf("oops!, nothing to sort\n");
return;
}

/* leave the first element for comparison, basis of insertion sort */
for(i = 1; i != s; ++i)
{
for(j = i; (j > 0) && (c[j] < c[j - 1]); --j)
{
char temp = c[j];
c[j] = c[j - 1];
c[j - 1] = temp;

}
}
}

=================== OUTPUT ==================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra insertion-sort.c
[arnuld@dune programs]$ ./a.out
array(unsorted): kandr
array(sorted): adknr
[arnuld@dune programs]$
Click to expand...
 
N

Nobody

It works fine. The Ullman's book does not have the check for (j > 0) in
inner loop which I have put myself. Any advice for improvement ?

One thing I don't get is how it is less expansive than bubble sort, we
have 2 loops and we exchange values and we do it only once. The only
difference is bubble starts for the bottom while insertion sort start
from the top but numbers of iterations are same.
Click to expand...

Bubble sort scans the entire array in the inner loop, while insertion sort
only scans a portion of it. This results in bubble sort performing roughly
twice as many comparisons.

Bubble sort performs between 1 and N iterations of the outer loop, and N
iterations of the inner loop, resulting in n^2 comparisons in the worst
case.

Insertion sort performs N-1 iterations of the outer loop, and between 1
and i iterations (average = i/2) of the inner loop, where i is the
iteration number of the outer loop, resulting in n*(n-1)/2 comparisons in
the worst case.
 
T

Tim Rentsch

Nobody said:
Bubble sort scans the entire array in the inner loop, while insertion sort
only scans a portion of it. This results in bubble sort performing roughly
twice as many comparisons.

Bubble sort performs between 1 and N iterations of the outer loop, and N
iterations of the inner loop, resulting in n^2 comparisons in the worst
case.
Click to expand...

The bubble sort that I'm used to performs N-k comparisons on pass k,
with k going from 1 to N-1. That's N*(N-1)/2 comparisons in the worst
case. Maybe you're using a suboptimal bubble sort?
Insertion sort performs N-1 iterations of the outer loop, and between 1
and i iterations (average = i/2) of the inner loop, where i is the
iteration number of the outer loop, resulting in n*(n-1)/2 comparisons in
the worst case.
Click to expand...

Actually insertion sort can do better -- using binary search to find
insertion points, insertion sort can use O( n log n ) compares, and
n*(n-1)/2 moves in the worst case. Besides needing fewer compares,
insertion sort beats bubble sort because data movement in insertion
sort is easier to optimize than it is in bubble sort.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Selection-Sort in C 35
Bubble Sort in C 48
Insertion Sort 4
selection-sort in C 22
pointer to pointer 7
Insertion Sort : C++ implementation 100 times slower than C implementation 7
Beginner at c 0
Binary Search in C 7

Members online

No members online now.
Total: 37 (members: 0, guests: 37)
Robots: 526

Forum statistics

Threads
473,769
Messages
2,569,579
Members
45,053
Latest member
BrodieSola

Latest Threads

Top