Skip to content

Instantly share code, notes, and snippets.

@zuch zuch/alphaSort.java
Last active Dec 21, 2015

Embed
What would you like to do?
java - Sort String Alphabetically using Count, Bubble & Quick Sort
/*
* Sort String Alphabetically using Count, Bubble & Quick Sort
*/
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
final public class alphaSort
{
private static String InputPath = "./input.txt";
public static void main(String[] args) throws IOException
{
StringBuilder sb = new StringBuilder();
//Read File
BufferedReader br;
br = new BufferedReader(
new InputStreamReader(
new FileInputStream( InputPath ) ) );
String strLine;
while ((strLine = br.readLine()) != null)
{
sb.append(strLine);
}
//Clean String
String cleanStr = clean(sb.toString());
System.out.println("Cleaned Out Punctuation.\n");
// Improved Count Sort
System.out.println("Count Sorting...");
long startTime = System.nanoTime();
String countStr = CountSort(cleanStr);
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("Time: "+duration+" ns");
System.out.println("Output: "+countStr+"\n");
//Transfrom to String[]
String[] transformStr = transform(cleanStr);
//Bubble Sort
System.out.println("Bubble Sorting...");
startTime = System.nanoTime();
String[] bubbleStr = bubbleSort(transformStr);
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("Time: "+duration+" ns");
print_output(bubbleStr);
//Quick Sort
System.out.println("Quick Sorting...");
startTime = System.nanoTime();
String[] quickStr = quickSort(transformStr,0,transformStr.length-1);
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("Time: "+duration+" ns");
print_output(quickStr);
System.exit(0);
}
//clean out Punctuation
public static String clean(String str)
{
char[] alphabet = {'a','b','c','d','e','f','g','h','i','j','k','l','m',
'n','o','p','q','r','s','t','u','v','x','y','z'};
StringBuilder sb = new StringBuilder();
String temp;
//lowerCase
temp = str.toLowerCase().replaceAll(" ", "");
//filter against alphabet
for(int i = 0; i < temp.length(); i++ )
for(int j = 0; j < alphabet.length; j++ )
if(temp.charAt(i) == alphabet[j])
sb.append(temp.charAt(i));
return sb.toString();
}
//transfrom from String to String[]
public static String[] transform(String str)
{
//instantiate String[]
String strArr[] = new String[str.length()];
//transfrom into String[]
for(int i = 0; i < str.length(); i++ )
strArr[i] = "" + str.charAt(i);
return strArr;
}
public static String CountSort(String str)
{
final int alphabetLength = 26;
final int alphabetAsciiStart = 97;
final int alphabetAsciiEnd = 122;
int[] alphaCount = new int[alphabetLength];
StringBuilder sb = new StringBuilder();
//count occurences of alphabet letter
for(int i = 0; i < str.length(); i++) {
int val = (int) str.charAt(i);
// Is letter
if (val >= alphabetAsciiStart && val <= alphabetAsciiEnd) {
alphaCount[val - alphabetAsciiStart]++;
}
}
for(int i = 0; i < alphabetLength; i++)
{
char c = (char) (i + alphabetAsciiStart);
for (int j = 0; j < alphaCount[i]; j++) {
sb.append(c);
}
}
return sb.toString();
}
public static String[] bubbleSort(String[] strArr)
{
for(int i = 0; i < strArr.length - 1; i++)
for(int j = 0; j < strArr.length - 1; j++)
if(strArr[j].compareTo(strArr[j+1]) > 0)
{
String temp = strArr[j];
strArr[j] = strArr[j+1];
strArr[j+1] = temp;
}
return strArr;
}
public static String[] quickSort(String[] strArr, int p, int r)
{
if(p<r)
{
int q=partition(strArr,p,r);
quickSort(strArr,p,q);
quickSort(strArr,q+1,r);
}
return strArr;
}
private static int partition(String[] strArr, int p, int r) {
String x = strArr[p];
int i = p-1 ;
int j = r+1 ;
while (true)
{
i++;
while ( i< r && strArr[i].compareTo(x) < 0)
i++;
j--;
while (j>p && strArr[j].compareTo(x) > 0)
j--;
if (i < j)
swap(strArr, i, j);
else
return j;
}
}
private static void swap(String[] strArr, int i, int j)
{
String temp = strArr[i];
strArr[i] = strArr[j];
strArr[j] = temp;
}
public static void print_output(String[] strArr) throws IOException
{
String temp = "";
for(int i=0; i < strArr.length; i++)
temp+=""+strArr[i];
System.out.println("Output: " + temp + "\n");
}
}
Contrary to popular belief, the pink unicorn flies east.
Command Line Output:
Cleaned Out Punctuation.
Count Sorting...
Time: 40503 ns
Output: aaabcceeeeeffhiiiiklllnnnnooooppprrrrssttttuuy
Bubble Sorting...
Time: 444155 ns
Output: aaabcceeeeeffhiiiiklllnnnnooooppprrrrssttttuuy
Quick Sorting...
Time: 195491 ns
Output: aaabcceeeeeffhiiiiklllnnnnooooppprrrrssttttuuy
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.