Коллекция алгоритмов, в помощь начинающим Опции

[Ахинея]

Выложенные здесь алгоритмы преследуют исключительно учебные цели.
Код неоптимизирован, местами морально устарел и показывает только принцип решения той или иной задачи. Однако он вполне рабочий и может быть использован с соответствующей дорботкой под Ваши собственные нужды.

Буду рада, если не только я буду их пополнять)


Содержание:
Перевод из ... в ...
Сортировка массивов
Графика
Матрицы
Специальные функции
Методы поиска
Решение систем линейных уравнений
Решение нелинейных уравнений
Решение диф. уравнений

Будет еще дополнено.

Спасибо

[Ахинея]

Сортировка массивов

Binary insertions

» Кликните сюда для просмотра оффтоп текста.. «

Код

//////////////////////////////////////////////////////////////////////////////
//
//  Binary insertion (array sorting)
//  (c) Johna Smith, 1996
//
//  Method description:
//    Split our array into two parts - sorted (left) and unsorted (right)
//    Initially sorted part contains only one element - first array element
//    Take an element from the unsorted part and put it in the right place in
//    the sorted part (using binary search to find this right place). So
//    sorted part contains now two elements. Repeat this process until
//    no elements left in the unsorted part.
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

const N=     10;  // array size

int array[N]={100,15,234,11,63,78,4,200,0,4}; // array of N integers
int element; // value of the element we want to insert
unsigned int right,left,middle; // auxulary variables for binary search

void show_array(void) // displays array
{
  for (int i=0;i<N;i++)
    printf("%d ",array[i]);
}

void main(void)
{
  // Display unsorted array
  printf("Unsorted array: ");
  show_array();

  // Sorting
  for (int i=1;i<N;i++) // main loop
  {
    // Searching place for element i (binary search)
    left=0;
    right=i;
    element=array[i];
    while (left<right)
    {
      middle=(left+right)/2;
      if (array[middle]<=element) left=middle+1; else right=middle;
    }

    // Inserting element i into the right place
    for (int j=i;j>right;j--) array[j]=array[j-1];
    array[right]=element;
  }

  // Display sorted array
  printf("\nSorted array: ");
  show_array();
}

Straight insertion

» Кликните сюда для просмотра оффтоп текста.. «

Код

//////////////////////////////////////////////////////////////////////////////
//
//  Straight insertion (array sorting)
//  (c) Johna Smith, 1996
//
//  Method description:
//    Split our array into two parts - sorted (left) and unsorted (right)
//    Initially sorted part contains only one element - first array element
//    Take an element from the unsorted part and put it in the right place in
//    the sorted part. So sorted part contains now two elements. Repeat
//    this process until no elements left in the unsorted part.
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

const N = 10;  // array size

int array[N]={100,15,234,11,63,78,4,200,0,4}; // array of N integers
int element; // value of the element we want to insert
unsigned int index; // index of the right position of the element

void show_array(void) // displays array
{
  for (int i=0;i<N;i++)
    printf("%d ",array[i]);
}

void main(void)
{
  // Display unsorted array
  printf("Unsorted array: ");
  show_array();

  // Sorting
  for (int i=1;i<N;i++) // main loop
  {
    index=0;
    // Searching place for element i
    while (array[index]<array[i]) index++;
    // Inserting element i into the right place
    element=array[i];
    for (int j=i;j>index;j--) array[j]=array[j-1];
    array[index]=element;
  }

  // Display sorted array
  printf("\nSorted array: ");
  show_array();
}

Heap sort

» Кликните сюда для просмотра оффтоп текста.. «

Код

//////////////////////////////////////////////////////////////////////////////
//
//  Heap sort
//  (c) Johna Smith, 1996
//
//  Method description:
//    This algorithm sorts array using pyramids. The pyramid is the
//    sequence of characters h(L), h(L+1),...,h(R) with the following
//    properties:
//          h(i)<=h(2i);  h(i)<=h(2i+1), i=L..R/2
//                        h1
//                     /     \               This is an example of
//                   h2       h3                   pyramid
//                 /    \   /    \
//               h4     h5 h6     h7
//              .....................
//    There are two steps in this algorythm:
//    1) Building pyramid from the given array using Floyd method of
//    building pyramid "on the same place".
//    2) Sorting built pyramid:
//       Swap last pyramid element (x) with the top one and shift x
//       to the right place using Floyd method
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

const N = 10;  // array size

int array[N]={100,15,234,11,63,78,4,200,0,4}; // array of N integers
int swp; // auxulary variable for swapping
int left,right; // indexes for left and right bounds of the sorted part of the array

void show_array(void) // this function displays array
{
  for (int i=0;i<N;i++)
    printf("%d ",array[i]);
}

// this function shifts element in the pyramid to the right place
// it helps to build pyramid "on the same place" (using Floyd method)

void shift(int left, int right)
{
  int i,j;
  int swp;
  int element;

  i=left;
  j=2*left+1;
  element=array[left];
  if (j<right && array[j]<array[j+1]) j++;
  while (j<=right && element<array[j])
  {
    // swapping elements
    swp=array[i];
    array[i]=array[j];
    array[j]=swp;
    // now i-th element is on j-th place:
    i=j;
    element=array[i];
    // and j-th element is lower (see pyramid picture)
    j=2*j+1;
    if (j<right && array[j]<array[j+1]) j++;
  }
}

void main(void)
{
   // Displaying unsorted array
   printf("Unsorted array: ");
   show_array();

   // Sorting
   left=N/2;
   right=N-1;
   // building pyramid from array
   while (left>0)
   {
     left--;
     shift(left,N-1);
   }
   // sorting built pyramid
   while (right>0)
   {
     // swapping elements
     swp=array[0];
     array[0]=array[right];
     array[right]=swp;
     // shifting element to the right place
     right--;
     shift(0,right);
   }

   // Displaying sorted array
   printf("\nSorted array: ");
   show_array();
}

Straight selections

» Кликните сюда для просмотра оффтоп текста.. «

Код

//////////////////////////////////////////////////////////////////////////////
//
//  Straight selections (array sorting)
//  (б) Johna Smith, 1996
//
//  Method description:
//    searching for smallest element in array, swapping with first element,
//    repeat this operation starting search from second element and so on
//    array become sorted when we'll start search from (n-1)-th element
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

const N = 10;  // number of elements in array

int array[N]={100,15,234,11,63,78,4,200,0,4};
int min; // smallest element in array
int index; // index of the smallest element in array
int swp; // auxulary variable for swapping

void show_array(void) // this function prints array
{
  for (int i=0;i<N;i++)
    printf("%d ",array[i]);
}

void main(void)
{
   // Printing unsorted array
   printf("Unsorted array: ");
   show_array();

   // Sorting
   for (int i=0;i<N-1;i++) // main loop
   {
     // searching for smallest element from i-th
     min=array[i]; // setting i-th elementas smallest
     index=i;
     for (int j=i+1;j<N;j++)
       if (array[j]<min)  // if there is element less than smallest
       {
          min=array[j];  // then remember its value
          index=j;       // and index
       }
     // swapping i-th and smallest element
     swp=array[index];
     array[index]=array[i];
     array[i]=swp;
   }

   // Printing sorted array
   printf("\nSorted array: ");
   show_array();
}

Shaker sort

» Кликните сюда для просмотра оффтоп текста.. «

Код

//////////////////////////////////////////////////////////////////////////////
//
//  Shaker sort
//  (c) Johna Smith, 1996
//
//  Method description:
//    Advanced bubble sort.
//    There are two main steps:
//     1) Move greatest element to the end, moving forward and
//        remembering place of the last elements exchange
//        this place will be right bound of the unsorted part
//     2) Move smallest element to the beginning, moving backward and
//        remembering place of the last elements exchange
//        this place will be left bound of the unsorted part
//    Repeat this two steps while right bound is greater than left
//    This method is useful when almost all elements in the array
//    are sorted.
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

const N=     10;  // array size

int array[N]={100,15,234,11,63,78,4,200,0,4}; // array of N integers
int index; // auxulary variable (the place of last swap)
int swp; // auxulary variable for swapping
int left,right; // indexes for left and right bounds of the sorted part of the array

void show_array(void) // this function displays array
{
  for (int i=0;i<N;i++)
     printf("%d ",array[i]);
}

void main(void)
{
   // Displaying unsorted array
   printf("Unsorted array: ");
   show_array();

   // Sorting
   left=0;
   right=N-1;
   do
   {
     // moving smallest element to the beginning (moving backward)
     for (int i=right;i>left;i--)
     {
        if (array[i-1]>array[i])
        {
          // swapping a(i) and a(i+1)
          swp=array[i];
          array[i]=array[i-1];
          array[i-1]=swp;
          index=i; // save index
        }
     }
     left=index;
     // moving greatest element to the end (moving forward)
     for (i=left;i<right;i++)
     {
       if (array[i]>array[i+1])
       {
         // swapping a(i) and a(i+1)
         swp=array[i];
         array[i]=array[i+1];
         array[i+1]=swp;
         index=i; // save index
       }
     }
     right=index;
} while (left<right);

   // Displaying sorted array
   printf("\nSorted array: ");
   show_array();
}

Shell sort

» Кликните сюда для просмотра оффтоп текста.. «

Код

//////////////////////////////////////////////////////////////////////////////
//
//  Shell sort (array sorting)
//  (c) Johna Smith, 1996
//
//  Method description:
//    1) Sort elements (0,4,8,12,...) (step=4) using straight insertions method
//    2) Sort elements (0,2,4,6,8,...) (step=2) using straight insertions method
//    3) Sort all elements (step=1) using straight insertions method
//    Shell sort is faster than simple straight insertions because at each
//    step more and more elements are already sorted (productivity increased
//    by ~300% for random array of 256 elements & about 700% (!) for random array
//    of 2048 elements (N. Wirth, Algoritms and data structures)
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

const T = 4;   // number of distances
const N = 20;  // array size

int array[N]={100,15,234,11,63,78,4,200,0,4,14,32,44,58,1,2,3,9,8,7}; // array of N integers
int interval[T]={9,5,3,1}; // last interval must be 1
int step; // current step
int element; // value of the element we want to insert
unsigned int index; // index of the right position of the element

void show_array(void) // displays array
{
  for (int i=0;i<N;i++)
    printf("%d ",array[i]);
}

void main(void)
{
  // Display unsorted array
  printf("Unsorted array: ");
  show_array();

  // Sorting
  for (int m=0;m<T;m++)  // main loop (by all distances)
  {
    step=interval[m];
    // sorting (0,step,2*step,3*step,...) elements using straight insertions
    for (int i=0;i<N;i+=step)
    {
      index=0;
      // Searching place for element i
      while (array[index]<array[i]) index+=step;
      // Inserting element i into the right place
      element=array[i];
      for (int j=i;j>index;j-=step) array[j]=array[j-step];
      array[index]=element;
    }
  }

  // Display sorted array
  printf("\nSorted array: ");
  show_array();
}

Quick sort (recursive)

» Кликните сюда для просмотра оффтоп текста.. «

Код

//////////////////////////////////////////////////////////////////////////////
//
//  Quick sort (recursive)
//  (c) Johna Smith, 1996
//
//  Method description:
//    1) Split array into two parts and remember middle element
//    2) Scan left part for element greater than middle
//    3) Scan right part for element less than middle
//    4) Swap these elements
//    So we have an array where all left elements are less than right elements
//    Apply these four steps to each part (left and right) of the array
//    until we have parts that contain only one element.
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

const N=     10;  // array size

int array[N]={100,15,234,11,63,78,4,200,0,4}; // array of N integers

void show_array(void) // this function displays array
{
  for (int i=0;i<N;i++)
    printf("%d ",array[i]);
}

void sort(int left,int right)
{
  int i,j;
  int element; // auxulary variable for middle element in the interval
  int swp; // auxulary variable for swapping

  i=left;  // index for left part
  j=right;  // index for right part
  element=array[(left+right)/2]; // middle element
  do
  {
    while (array[i]<element) i++; // scanning left part
    while (element<array[j]) j--; // scanning right part
    if (i<=j)
    {
      // swapping elements
      swp=array[i];
      array[i]=array[j];
      array[j]=swp;
      i++; j--;
    }
  } while (i<=j);
  if (left<j) sort(left,j); // applying the same procedure to the left part
  if (i<right) sort(i,right); // applying the same procedure to the right part
}

void main(void)
{
  // Displaying unsorted array
  printf("Unsorted array: ");
  show_array();

  // Sorting
  sort(0,N-1);

  // Displaying sorted array
  printf("\nSorted array: ");
  show_array();
}

Quick sort (non-recursive)

» Кликните сюда для просмотра оффтоп текста.. «

Код

//////////////////////////////////////////////////////////////////////////////
//
//  Quick sort (non-recursive)
//  (c) Johna Smith, 1996
//
//  Method description:
//    1) Split array into two parts and remember middle element
//    2) Scan left part for element greater than middle
//    3) Scan right part for element less than middle
//    4) Swap these elements
//    So we have an array where all left elements are less than right elements
//    Apply these four steps to each part (left and right) of the array
//    until we have parts that contain only one element.
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

const N = 10;         // array size
const STACK_SIZE = 4; // stack size must be >=log N

int array[N]={100,15,234,11,63,78,4,200,0,4}; // array of N integers

void show_array(void) // this function displays array
{
  for (int i=0;i<N;i++)
    printf("%d ",array[i]);
}

struct {int left; int right;} stack[STACK_SIZE]; // stack emulation
unsigned int ss; // current stack size
int i,j;
int element; // auxulary variable for middle element in the interval
int swp; // auxulary variable for swapping
int left,right; // interval bounds


void main(void)
{
  // Displaying unsorted array
  printf("Unsorted array: ");
  show_array();

  // Sorting
  ss=1;
  stack[0].left=0;
  stack[0].right=N-1;
  do
  {
    // pushing from stack last request
    left=stack[ss-1].left;
    right=stack[ss-1].right;
    ss--;
    do
    {
      // splitting array[left]..array[right] interval
      i=left;  // index for left part
      j=right;  // index for right part
      element=array[(left+right)/2]; // middle element
      do
      {
        while (array[i]<element) i++; // scanning left part
        while (element<array[j]) j--; // scanning right part
        if (i<=j)
        {
          // swapping elements
          swp=array[i];
          array[i]=array[j];
          array[j]=swp;
          i++; j--;
        }
      } while (i<=j);
      // pushing request into stack
      // (we select longest part and push request for it to reduce stack size)
      if (j-left<right-i)
      {
        if (i<right) // push request for the right part (because it's longer than left)
        {
          ss++;
          stack[ss-1].left=i;
          stack[ss-1].right=right;
        }
        right=j; // continue sorting left part
      } else
      {
        if (left<j) // push request for the left part (because it's longer than right)
        {
          ss++;
          stack[ss-1].left=left;
          stack[ss-1].right=j;
        }
        left=i; // continue sorting right part
      }
    } while(left<right);
  } while(ss!=0);

  // Displaying sorted array
  printf("\nSorted array: ");
  show_array();
}

Exchanges

» Кликните сюда для просмотра оффтоп текста.. «

Код

//////////////////////////////////////////////////////////////////////////////
//
//  Exchanges (array sorting)
//  (б) Johna Smith, 1996
//
//  Method description:
//    Using linear search find smallest i with the following property:
//    a(i)>a(i+1), swap a(i) and a(i+1) and repeat this process searching
//    from a(i+1). After one pass greatest number will be placed at right
//    place. We'll decrease amount of acting elements on each pass.
//    When 2 elements will left we'll say that array is sorted
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

const N=     10;  // number of array elements

int array[N]={100,15,234,11,63,78,4,200,0,4};
int swp; // auxulary variable for swapping
int m; // number of active elements on current pass

void show_array(void) // this function prints array
{
  for (int i=0;i<N;i++)
    printf("%d ",array[i]);
}

void main(void)
{
   // Printing unsorted array
   printf("Unsorted array: ");
   show_array();

   // Sorting
   m=N; // All elements acting at first pass
   while (m>1) // repeat passes while there is more than one element
   {
     for (int i=0;i<m-1;i++) // main loop
     {
       // searching for smallest element
       if (array[i]>array[i+1]) // if a(i)>a(i+1)
       {
         // swapping a(i) and a(i+1)
         swp=array[i];
         array[i]=array[i+1];
         array[i+1]=swp;
       }
     }
     m--; // decreasing amount of acting elements
   }

   // Printing sorted array
   printf("\nSorted array: ");
   show_array();
}