1 /*

     2  * Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies). 

     3  * All rights reserved.

     4  * This component and the accompanying materials are made available

     5  * under the terms of the License "Eclipse Public License v1.0"

     6  * which accompanies this distribution, and is available

     7  * at the URL "http://www.eclipse.org/legal/epl-v10.html".

     8  *

     9  * Initial Contributors:

    10  * Nokia Corporation - initial contribution.

    11  *

    12  * Contributors:

    13  *

    14  * Description: 

    15  *

    16  */

    17 

    18 package com.nokia.carbide.cpp.internal.pi.utils;

    19 

    20 import java.util.Stack;

    21 import java.util.Vector;

    22 

    23 

    24 public class QuickSortImpl

    25 {

    26 	public static void sort(Sortable[] array)

    27 	{

    28 		quickSort(array,0,array.length-1);

    29 	}

    30 	

    31 	public static void sort(Vector sortables)

    32 	{

    33 		Sortable[] s = new Sortable[sortables.size()];

    34 		s = (Sortable[])sortables.toArray(s);

    35 		sort(s);

    36 		sortables.clear();

    37 		for (int i=0;i<s.length;i++)

    38 		{

    39 			sortables.add(s[i]);

    40 		}

    41 	}

    42 	

    43 	public static void sortReversed(Vector sortables)

    44 	{

    45 		Sortable[] s = new Sortable[sortables.size()];

    46 		s = (Sortable[])sortables.toArray(s);

    47 		sort(s);

    48 		sortables.clear();

    49 		for (int i=(s.length-1);i>=0;i--)

    50 		{

    51 			sortables.add(s[i]);

    52 		}

    53 	}

    54 		

    55 	public static void quickSort(Sortable[] a,int low, int high)

    56 	{

    57 		Stack stack = new Stack();

    58 		

    59 		//System.out.println("QS both sides "+low+" "+high);

    60 		int pivot;

    61 		/* Termination condition! */

    62 		if ( high > low )

    63 		{

    64 			while(high > low)

    65 			{

    66 				pivot = partition( a, low, high );

    67 				//System.out.println("QS left side is "+low+"-"+pivot+" right side is "+pivot+"-"+high);

    68 

    69 				//quickSort( a, low, pivot-1 );

    70 				stack.push(new Integer(pivot+1));

    71 				stack.push(new Integer(high));

    72 				//System.out.println("Pushed right side");

    73 				high = pivot-1;

    74 			}				

    75 			

    76 			while(!stack.isEmpty())

    77 			{

    78 				high = ((Integer)stack.pop()).intValue();

    79 				low = ((Integer)stack.pop()).intValue();

    80 				//System.out.println("Popping right side "+low+"-"+high);

    81 				quickSort( a, low, high );

    82 			}

    83 		}

    84 	}

    85 	

    86 	public static int partition(Sortable[] a,int low,int high)

    87 	{

    88 		int left, right;

    89 		int pivot;

    90 		

    91 		pivot = left = low;

    92 		right = high;

    93 		long pivotValue = a[pivot].valueOf();

    94 		Sortable pivotItem = a[pivot];

    95 		

    96 		while ( left < right ) 

    97 		{

    98 			// Move left while item < pivot 

    99 				//System.out.println("Starting left "+left);

   100 				while(a[left].valueOf() <= pivotValue ) 

   101 				{

   102 					//System.out.println(valueOf(a[left])+" < "+pivotValue);

   103 					left++;

   104 					//System.out.println("left ="+left);

   105 					if (left == a.length)

   106 						break;

   107 				}

   108 				//System.out.println("Final left = "+left);

   109 			// Move right while item > pivot

   110 			while( a[right].valueOf() > pivotValue ) 

   111 			{

   112 				right--;

   113 				//System.out.println("right ="+right);

   114 			}

   115 			if ( left < right )

   116 			{

   117 				//System.out.println("Swapping "+left+" and "+right);

   118 				Sortable tmp = a[left];

   119 				a[left] = a[right];

   120 				a[right] = tmp;

   121 				//SWAP(a,left,right);

   122 			}

   123 		}

   124 		// right is final position for the pivot

   125 		a[low] = a[right];

   126 		a[right] = pivotItem;

   127 		//System.out.println("Pivot is now "+right+" pivot value "+valueOf(a[right]));

   128 		return right;

   129 	}

   130 }