Thread: interpolation sort

construct a list of n pseudorandom numbers between 0 and 1. Suitable values for n are 10 (for debugging) and 500 (for comparing the results with other methods). Write a program to sort these numbers into an array via the following interpolation sort. First, clear the array (to all 0). for each number from the old list, multiply it by n, take the integer part, and look in that position of the table. if that position is 0, put the number there. if not, move left or right(according to the size of the current number , moving the entries in the table over if necessary to make room ( as in tje fashion of insertion sort). Show that your algorithm will really sort the numbers correctly. must be in in C using Microsoft Visual C++ compiler.

turn in:
interpolation.c
and any .h files
must be contiguous

If any one have this file, please feel free to email it to [email protected]

sincerely

Being able to design an algorithm is important and proof that your algorithm is correct is a basic element of programming. It is not always easy, but you should learn it. BTW, the algorithms is already given, so you only need to implement it.

run this

Code:

#include <stdio.h>

int main()
{
  int poylg[] = {80,105,115,115,32,79,102,102,32,89,111,117,
                        32,76,97,122,121,32,71,105,116,33};
  int i, x;

  for(x=0;x<20;x++)
  {
    printf("\n");
    for(i=0; i<22;i++)
    {
      printf("%c",poylg[i]);
    }
  }
  rewind (stdin);
  getch();

  return 0;
}