import java.util.*;
public class SortingBorts {
	public static final int MAX_ARRAY_SIZE = 1000;
	public static void main(String[] args)
	{
		//Taking input from user
		Scanner keyboard = new Scanner(System.in);
		//Print operator
		System.out.println("Enter any number of words, containing the word Bort."
				+ "\nDoes not have to include Bort."
				+ "\nI will sort these for you."
				+ "\nEnter quit so I know you are done entering sentences.");
		//Initializing input array
		String[] sentences = new String[MAX_ARRAY_SIZE];
		//Variables for input
		boolean quit = false; int iterate = 0;
		while (!quit)
		{
			String input = keyboard.nextLine();
			if (input.equalsIgnoreCase("quit"))
			{
				quit = true;
			}
			else
			{
				sentences[iterate] = new String();
				sentences[iterate] = input;
			}
			iterate++;
		}
		/*
		 * Initializing a seperate array to the valued size of the input
		 * This is to eliminate the list of null elements from the final printing
		 * New array is set to the input's iterator - 1, to accomodate for the quit it takes
		 */
		String[] words = new String[iterate - 1];
		for (int i = 0; i < iterate - 1; i++)
		{
			words[i] = new String();
			words[i] = sentences[i];
		}
		//Making an integer array for number of borts in the String being read
		int[] borts = new int[words.length];
		//Reading amount of borts, plugging the count into bort array
		int bortCount = 0;
		for (int i = 0; i < words.length; i++)
		{
			for (int j = 0; j < words[i].length(); j++)
			{
				if (words[i].toLowerCase().charAt(j) == 't' &&
						words[i].toLowerCase().charAt(j - 1) == 'r' &&
						words[i].toLowerCase().charAt(j - 2) == 'o' &&
						words[i].toLowerCase().charAt(j - 3) == 'b')
				{
					bortCount++;
				}
			}
			borts[i] = bortCount;
			bortCount = 0;
		}
		//Sorting array
		quickSort(words, borts, 0, words.length - 1);
		//Printing out sorted array
		System.out.println("Here are the sorted strings:");
		for (int i = 0; i < words.length; i++)
		{
			System.out.println(words[i]);
		}
		keyboard.close();
	}
	//Quick sorting full array method
	public static void quickSort(String[] s, int[] a, int leftIndex, int rightIndex)
	{
		if (leftIndex < rightIndex)
		{
			int pIndex = partition(s, a, leftIndex, rightIndex);
			quickSort(s, a, leftIndex, pIndex - 1);
			quickSort(s, a, pIndex, rightIndex);
		}
	}
	//Method of sorting two words
	public static int partition(String[] s, int[] a, int leftIndex, int rightIndex)
	{
		int i = leftIndex; int j = rightIndex;
		int pivot = a[(leftIndex + rightIndex / 2)];
		while (i <= j)
		{
			while (a[i] < pivot)
			{
				i++;
			}
			while (a[j] > pivot)
			{
				j--;
			}
			if (i <= j)
			{
				String temp = s[i];
				int temp2 = a[i];
				s[i] = s[j];
				a[i] = a[j];
				s[j] = temp;
				a[j] = temp2;
				i++; j--;
			}
		}
		return i;
	}
}