Quick Sort in Java

Quick sort is one of the coolest algorithms available in sorting and its performance is measured most of the time in O(nlogn), although the worst case sorting times of bubble sort and this are equal.
Inspite its worst case time, this always performs superiorly when the input is completely shuffled/randomized. This is one of the modest sorts available :).

Quick sort is an example of in-place sort. No extra space is needed as in merge sort where we have to use one full extra array to hold all the merged values. The only space that quick sort uses may be the counter variables and the extra space required for swapping.

Below is a pictorial representation of how this quick sort works,

I ran this sort for a well randomized data of million elements again and again and it beats the Merge sort hands down having a 75% quicker speed. Its always advisable to have shuffle the data upfront before running this algorithm.
Here is the source code for the same,

package dsa.sorting;

/**
 * A wonderful inplace sorting technique
 * @author Braga
 */
public class QuickSort {
 
 public static int SIZE = 1000000;

 public int[] sort(int[] input) {
  quickSort(input, 0, input.length-1);
  return input;
 }
 
 public static void main(String args[]){
  int[] a = new int[SIZE];
  for(int i=0;i<SIZE;i++){
   a[i] = (int)(Math.random()*SIZE);
  }
  QuickSort mNew = new QuickSort();
  long start = System.currentTimeMillis();
  mNew.sort(a);
  long end = System.currentTimeMillis();
  System.out.println("Time taken to sort a million elements : "+(end-start)+" milliseconds");
 }
 
 public void print(int[] inputData) {
  for(int i:inputData){
   System.out.print(i+" ");
  }
  System.out.println();
 }
 
 private void quickSort(int arr[], int left, int right) {
  int index = partition(arr, left, right);
  if (left < index - 1)
   quickSort(arr, left, index - 1);
  if (index < right)
   quickSort(arr, index, right);
 }
 
 private int partition(int arr[], int left, int right) {
  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];
  while (i <= j) {
   while (arr[i] < pivot)
    i++;
   while (arr[j] > pivot)
    j--;
   if (i <= j) {
    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
    i++;
    j--;
   }
  }
  return i;
 }
}
//Time taken to sort a million elements : 156 milliseconds

Pros:
1) Efficient average case compared to any algorithm.
2) Recursive definition and popularity because of its high efficiency.

Cons:
1) Worst case scenario sucks.

As we discussed the worst case can be easily overcome by deliberately shuffling the input. I would rate quick sort as one of the best techniques available in sorting till date.

More sorting methods yet to come.
Cheers,
Bragaadeesh.

Merge Sort in Java

Now that we've examined one of the most simplest and inefficient sorting algorithms (Bubble Sort), lets have a look at O(nlogn) sorts. To start with, we shall look into Merge Sort.
Merge Sort follows divide and conquer technique. The following is a simple pictorial illustration of the same.

There will be two parts in this sort. One would be halving the input numbers O(logn) and the other would be merging them back O(n) which results in a comprehensive O(nlogn) time. Wait till you see the running version of this sort technique and the time taken to sort a million entries.

First for the code part,

package dsa.sorting;

public class MergeSortOptimized
{

    public static int SIZE = 1000000;

    public static void main(String args[])
    {
        int[] a = new int[SIZE];
        for (int i = 0; i < SIZE; i++) {
            a[i] = (int) (Math.random() * SIZE);
        }
        long start = System.currentTimeMillis();
        MergeSortOptimized mNew = new MergeSortOptimized();
        mNew.sort(a);
        long end = System.currentTimeMillis();
        System.out.println("Time taken to sort a million elements : "
                + (end - start) + " milliseconds");
    }

    public int[] sort(int[] input)
    {
        int[] temp = new int[input.length];
        mergeSort(input, temp, 0, input.length - 1);
        return input;
    }

    public void mergeSort(int[] fromArray, int[] toArray, int left, int right)
    {
        if (left < right) {
            int center = (left + right) / 2;
            mergeSort(fromArray, toArray, left, center);
            mergeSort(fromArray, toArray, center + 1, right);
            merge(fromArray, toArray, left, center + 1, right);
        }
    }

    public void merge(int[] fromArray, int[] toArray, int leftPos,
            int rightPos, int rightEnd)
    {
        int leftEnd = rightPos - 1;
        int tempPos = leftPos;

        int numElements = rightEnd - leftPos + 1;

        while (leftPos <= leftEnd && rightPos <= rightEnd) {
            if (fromArray[leftPos] < fromArray[rightPos]) {
                toArray[tempPos++] = fromArray[leftPos++];
            }
            else {
                toArray[tempPos++] = fromArray[rightPos++];
            }
        }

        while (leftPos <= leftEnd) {
            toArray[tempPos++] = fromArray[leftPos++];
        }
        while (rightPos <= rightEnd) {
            toArray[tempPos++] = fromArray[rightPos++];
        }

        for (int i = 0; i < numElements; i++, rightEnd--) {
            fromArray[rightEnd] = toArray[rightEnd];
        }

    }

}
// Time taken to sort a million elements : 247 milliseconds

As you may observe, the above technique just took 247 milliseconds to sort a million elements whereas the bubble sort tooks almost 28 seconds to sort a hundred thousand elements!!!!! This is due to the logarithmic order of the sort.

Pros:
1) Works in O(nlogn) time.
2) Worst case of merge sort is equal to best case of a quick sort! (We shall discuss more about in the coming sections).

Cons:
1) Consumes extra space.
2) Due to the recursive nature of the algorithm, may eat up stack.

Thanks for reading my post. We shall explore more sorting techniques in the coming days. Till then, bye for now from,
Bragaadeesh.

Java/C++ Program to reverse words in a sentence but still maintain the space position

This is a slight modification to the previous program. Here we should maintain the space as well. For doing that, I am simultaneously tracking the spaces and the words. I have made an assumption that there wont be any trailing or leading spaces in the sentence as such. Even if its there, a slight tweak of the following code would give me the output i desire.

package dsa.stringmanipulation;

import java.util.ArrayList;
import java.util.List;

public class RevWordWhiteSpace {

public static final String SPACE = " ";

private List<Integer> spaceTracker = new ArrayList<Integer>();
private List<String> wordTracker = new ArrayList<String>();

public static void main(String args[]){
RevWordWhiteSpace rev = new RevWordWhiteSpace();
System.out.println(rev.getRevWithWhiteSpace("This     should  maintain the space in place"));
}

/*
* Lets assume that our input text will not have any spaces before and after
*/
public String getRevWithWhiteSpace(String inputText){
if(inputText!=null && inputText.length()>0){
int lenOfText = inputText.length();
if(lenOfText==1){
return inputText;
}else{
constructLists(inputText);
StringBuilder output = new StringBuilder();
for(int i=wordTracker.size()-1,j=0; i>0; i--,j++){
output.append(wordTracker.get(i));
output.append(constructSpace(spaceTracker.get(j)));
}
output.append(wordTracker.get(0));
return output.toString();
}
}else{
System.out.println("Invalid Sentence");
return null;
}
}

private CharSequence constructSpace(Integer integer) {
String op="";
for(int i=0;i<integer;i++){
op+=" ";
}
return op;
}

private void constructLists(String inputText) {
int tempBufSpace = 0;
String bufWord = "";
for(int i=0;i<inputText.length();i++){
if(inputText.charAt(i)!=' '){
if(tempBufSpace>0){
spaceTracker.add(tempBufSpace);
tempBufSpace=0;
}
bufWord+=inputText.charAt(i);
}else{
if(bufWord.length()>0){
wordTracker.add(bufWord);
bufWord = "";
}
tempBufSpace++;
}
}
if(bufWord.length()>0){
wordTracker.add(bufWord);
}
}
}

//The output produced would be
//place     in  space the maintain should This

Also code in C++,

#include <iostream>
#include <string.h>

using namespace std;

void str_rev(char s[], int start, int end)
{
    int len = end - start;
    for(int i=0;i<len/2;i++)
    {
        char t = s[i+start];
        s[i+start] = s[end-i-1];
        s[end-i-1] = t;
    }
}

int main()
{
    char a[] = "my     name is prabhu";
    cout << "[" << a << "] ==> ";
    str_rev(a,0,strlen(a));

    cout << "[" << a << "] ==> ";

    int start_index = 0;
    for(size_t i=0;i<=strlen(a);i++)
    {
      if(a[i] == ' ' || a[i] == '\0')
      {
         str_rev(a,start_index,i);
         start_index = i+1;
      }
    }
    cout << "[" << a << "] ==> ";
    char b[strlen(a)+1];
    int i=0, k=0, j=strlen(a)-1;
    while(a[i] != '\0')
    {
        if(a[i] != ' ')
            b[k++] = a[i];
        else
        {
            while(a[j] != ' ' && j>=0)
                j--;
            while(a[j--] == ' ' && j>=0)
                b[k++] = ' ';
        }
        i++;
    }
    b[k] = '\0';
    cout << "[" << b << "]" << endl;
  
    return 0;
}

Cheers,
Bragaadeesh.