Code-Bin #1095

untitled C++ Code
Posted by: asdjfhg987 | February 7, 2011 @ 5:43pm

C++ Code

#include<iostream>
using namespace std;

// Exchange two doubles
void exchange(double& x, double& y)
{
    double t = x;
    x = y;
    y = t;
}

// Rearrange the elements of the array so that all the elements
  // whose value is > divider come before all the other elements,
  // and all the elements whose value is < divider come after all
  // the other elements.  Upon return, firstNotGreater is set to the
  // index of the first element in the rearranged array that is
  // <= divider, or n if there is no such element, and firstLess is
  // set to the index of the first element that is < divider, or n
  // if there is no such element.
  // In other words, upon return from the function, the array is a
  // permutation of its original value such that
  //   * for 0 <= i < firstNotGreater, a[i] > divider
  //   * for firstNotGreater <= i < firstLess, a[i] == divider
  //   * for firstLess <= i < n, a[i] < divider
  // All the elements > divider end up in no particular order.
  // All the elements < divider end up in no particular order.
void divide(double a[], int n, double divider,
                                    int& firstNotGreater, int& firstLess)
{
    if (n < 0)
        n = 0;

// It will always be the case that just before evaluating the loop
      // condition:
      //  firstNotGreater <= firstUnknown and firstUnknown <= firstLess
      //  Every element earlier than position firstNotGreater is > divider
      //  Every element from position firstNotGreater to firstUnknown-1 is
      //    == divider
      //  Every element from firstUnknown to firstLess-1 is not known yet
      //  Every element at position firstLess or later is < divider

firstNotGreater = 0;
    firstLess = n;
    int firstUnknown = 0;
    while (firstUnknown < firstLess)
    {
        if (a[firstUnknown] < divider)
        {
            firstLess--;
            exchange(a[firstUnknown], a[firstLess]);
        }
        else
        {
            if (a[firstUnknown] > divider)
            {
                exchange(a[firstNotGreater], a[firstUnknown]);
                firstNotGreater++;
            }
            firstUnknown++;
        }
    }
}

// Rearrange the elements of the array so that
  // a[0] >= a[1] >= a[2] >= ... >= a[n-2] >= a[n-1]
  // If n <= 1, do nothing.
void order(double a[], int n)
{
    if (n <= 1)
        return;

// Divide using a[0] as the divider (any element would do).
    int firstNotGreater;
    int firstLess;
    divide(a, n, a[0], firstNotGreater, firstLess);

// sort the elements > divider
    order(a, firstNotGreater);

// sort the elements < divider
    order(a+firstLess, n-firstLess);
}

int main()
{
     int a[10] = {1,1,3,2,4,5,7,0,4,9};
     order(a,10);
     for(int i = 0; i < 10; i++)
          cout << a[i] << endl;
}

Syntax Highlighting

[Open in new window]

Author Comments

none

Rating

4.58 / 8
52 Votes