Форум программистов [Powered by Invision Power Board]

Код
//////////////////////////////////////////////////////////////////////////////
//
//  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>

#include <iostream.h>

int* array, N;

void show_array(void) // this function displays array
{
  for (int i=0; i<N; ++i)
   cout << array[i] << '\t';
}

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)
{

cout << "N = "; cin >> N;



array = new int[N];

  for(int i=0; i<N; ++i)
   cin >> array[i];

cin.get();

  show_array();

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

cin.get();

  cout << '\n';

  show_array();

cin.get();

delete[] array;

}