Array sorting logic

[CplusplusAcolyte]

I know there are plenty of threads on the topic, but I wished to start a thread exploring the logic of sorting. Below is a simple sorting algorithm that goes through an array in passes, moving larger values to the right, and smaller values to the left. The primary question I have is how can I increase the efficiency of my sorting without introducing more complexity. Currently, the array will be sorted in anywhere from 3-8 passes.

#include <iostream>
#include <time.h>
#include <windows.h>

using namespace std;

void Color (int color)
{
    HANDLE hCon = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(hCon,color);
}

void outarray(int array[10])
{
    for (int i=0; i<10; i++)
    {
        if (array[i]!=i)
            Color(12);
        else
            Color(7);
        cout<<array[i]<<" ";
    }
    cout<<endl;
    Color(7);
}

void sorter(int array[10], int x)
{
    if (x==1)
    {
        for (int i=0; i<9; i++)
        {
            int temp=array[i];
            if (array[i]>array[i+1])
            {
                //perform swap
                array[i]=array[i+1];
                array[i+1]=temp;
            }
        }
    }
    else
    {
        for (int i=9; i>0; i--)
        {
            int temp=array[i];
            if (array[i]<array[i-1])
            {
                //perform swap
                array[i]=array[i-1];
                array[i-1]=temp;
            }
        }
    }
}
int main ()
{
    srand(time(NULL));//set random number seed
    //initialize array of 10 ints
    int array[10]={};
    bool sorted=false;
    //populate and output array with 0-9
    cout<<"Original Array:   ";
    for (int i=0;i<10;i++)
        array[i]=i;
    outarray(array);
    //randomize locations
    for (int i=0;i<10;i++)
    {
        int temp=array[i];//store value being swapped
        int temp2;
        do
        {
            temp2=rand()%10;//randomize swap position
        } while (temp2==i);
        array[i]=array[temp2];
        array[temp2]=temp;
    }
    cout<<"Randomized Array: ";
    outarray(array);

    int i=0;
    while (sorted==false)
    {
        sorter(array,i%2==0);
        cout<<i+1<<((i==0) ? "st" : (i==1) ? "nd" : (i==2) ? "rd" : "th")<<"  pass  sort:  ";
        outarray(array);
        i++;
        if (array[0]==0 && array[1]==1 && array[2]==2 && array[3]==3 &&
            array[4]==4 && array[5]==5 && array[6]==6 && array[7]==7 &&
            array[8]==8 && array[9]==9)
        {
            sorted=true;
        }
    }
    cout<<"It took "<<i<<" passes to sort the array.\n\n";
}

[Stewbond]

Here's a class for a course I did in Java a few months ago. It's an array with embedded sort algorithms.

class Array
{
  int[] arr;

  public Array(int inSize)
  {
    arr = new int[inSize];
  }

  public int at(int pos) throws ArrayIndexOutOfBoundsException
  {
    if (pos < 0 || pos >= arr.length)
      throw new ArrayIndexOutOfBoundsException();
    return arr[pos];
  }

  public void set(int pos, int data) 
    throws ArrayIndexOutOfBoundsException
  {
    if (pos < 0 || pos >= arr.length)
      throw new ArrayIndexOutOfBoundsException();
    arr[pos] = data;
  }

  public int size()
  {
    return arr.length;
  }

  public void bubbleSort()
  {
    boolean sorted = false;
    int j = 0; 
    while (!sorted)
    {
      sorted = true;
      j++;
      for (int i = 0; i < arr.length - j; i++)
      {
        if (arr[i] > arr[i+1])
        {
          int tmp = arr[i];
          arr[i] = arr[i+1];
          arr[i+1] = tmp;
          sorted = false;
        }
      }
    }
  }

  public void selectionSort()
  {
    for (int i = 0; i < arr.length - 1; i++)
    {
      int minIndex = i;
      for (int j = i+1; j < arr.length; j++)
        if (arr[j] < arr[minIndex])
          minIndex = j;
      if (minIndex != i)
      {
        int tmp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = tmp;
      }
    }
  }

  public void insertionSort()
  {
    for (int i = 1; i < arr.length; i++)
    {
      int newVal = arr[i], j = i;
      for (; j > 0 && arr[j-1] > newVal; j--)
        arr[j] = arr[j-1];
      if (i != j)
        arr[j] = newVal; 
    }
  }

  public void quickSort()
  {
    quickSort(arr, 0, arr.length-1);
  }

  private void quickSort(int ar[], int left, int right)
  {
    int i = left, j = right;
    int pivot = ar[(left + right) / 2];

    while (i <= j)
    {
      while(ar[i] < pivot)
        i++;
      while(ar[j] > pivot)
        j--;
      if (i < j)
      {
        int tmp = ar[i];
        ar[i] = ar[j];
        ar[j] = tmp;
        i++; j--;
      }
      else if (i == j)
      {
        i++; j--;
      }
    }
    if (left < j)
      quickSort(ar, left, j);
    if (i < right)
      quickSort(ar, i, right);
  }

  public void shellSort()
  {
    for(int inc = arr.length/2; inc > 0; inc /= 2)
    {
      for (int i = inc; i < arr.length; i++)
      {
        int tmp = arr[i], j = i;
        for (; j >= inc; j -= inc)
        {
          if(tmp < arr[j-inc])
            arr[j] = arr[j-inc];
          else
            break;
        }
        if (j != i)
          arr[j] = tmp;
      }
    }
  }
}

[Smac89]

The one optimization I know about is already in the program provided by Stewbond. Look at the for-loop in the bubblesort method. Notice that at each iteration, the number of elements to check decreases by one? This is because the next largest/smallest element (depending on the order you want to sort the array), "bubbles" to the back of the array after each iteration of the for-loop. So there is no need to check that last element after each iteration.

This reduction in complexity is almost non significant with this optimization, but it is nonetheless slightly faster than any bubblesort program that does not make use of this

To test this, use the following numbers and run one loop of bubblesort on it then look at the last value:

5, 4, 3, 2, 1

[Stewbond]

Some sorting algorithms are more efficient than others when randomly sorted, inverted, nearly sorted, or with only a few values. Check this site out. It explains things pretty well:
http://www.sorting-algorithms.com/

[CplusplusAcolyte]

Thanks guys, I'll be looking into this further.