Alternative partition method

 

See also

http://analgorithmaday.blogspot.com/2011/02/partitioning-algorithmin-place.html

Introduction

  Quick sort partition algorithm is sometimes taught differently. :) So, thought of covering that too. There is no difference in performance or space usage. Only advantage is, this method is little bit straight forward.

Concept

  Instead of taking the pivot and incrementing 2 counts: i and j both starting from the left, we can maintain left & right with left starting from the start and right starting from the end.

  As we know that, left needs to have lesser items and right needs to have greater items. until we have appropriate items, we can simply skip it. This is little bit clearer since the skip we do is not so clear in old partition approach.

  After we skip perfectly “ok” left and right, what we have will be swappable items. We continue this until we meet the condition left > right.

  After we do all the swaps and ready with left & right lists smaller & greater. We can simply swap the element in the location where right is.

Code

int qpartition( int *a, int low, int high )

{

    int left, right;

    int pivot_item;

    pivot_item = a[low];

    left = low;

    right = high;

    while ( left < right ) {

        /* Move left while item < pivot */

        while( a[left] <= pivot_item ) left++;

        /* Move right while item > pivot */

        while( a[right] > pivot_item ) right--;

        if ( left < right ) swap(a[left],a[right]);

    }

    /* right is final position for the pivot */

    a[low] = a[right];

    a[right] = pivot_item;

    return right;

}

void main()

{

    int A[] = {9,5,7,1,10,2,3};

    int loc = qpartition(A, 0,6);

}

• I felt this approach, little bit confusing.. :) If you are not used to lots of counters.. be with the old approach
• The above code taken from: http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort1a.html
• Even though a[low] is the pivot, we include that as well in the comparison. This is also another difference in this algorithm.

Randomized Quick sort

“Randomized quick sort uses random partition method we discussed. We just select a random pivot in an array. The advantage we get is that we can reduce the worst case performance of quick sort!! But still, this optimization is expected!!”

Introduction

   As we have seen a lot about this already, we can directly jump into Randomized quick sort

Concept

  Just select a random pivot element in the partition algorithm.

Code

int random_partition(int* arr, int start, int end)

{

    srand(time(NULL));

    int pivotIdx = start + rand() % (end-start+1);

    int pivot = arr[pivotIdx];

    swap(arr[pivotIdx], arr[end]); // move pivot element to the end

    pivotIdx = end;

    int i = start -1;

    for(int j=start; j<=end-1; j++)

    {

        if(arr[j] <= pivot)

        {

            i = i+1;

            swap(arr[i], arr[j]);

        }

    }

    swap(arr[i+1], arr[pivotIdx]);

    return i+1;

}

void random_quick_sort(int* arr, int start, int end)

{

    if(start < end) {

        int mid = random_partition(arr, start, end);

        random_quick_sort(arr, start, mid-1);

        random_quick_sort(arr, mid+1, end);

    }

}

void main()

{

    int A[] = {2,5,7,1,10,8,9};

    random_quick_sort(A, 0,6);

}

• pivot Index must be start + rand() %(end-start+1).. We do a recursive algorithm with different start and end.. :) so be careful about the formula for pivotIndex
• We need to add start to the rand() % end because we need to get near the size of the array
• start->mid-1 and mid+1->end.. is enough for quick sort.. NOTE: we always get the pivot element in right position at every iteration
• There is an alternate way of partitioning given at many other places.. Not a CLRS way!! :) We will see that as well in the next article..!! :D

Reverse only the words in string

 

Introduction

   Another popular interview question is, reverse the words in the string. We have seen how to do string reverse, simply by swapping the last character with first. But when it comes to reversing just words in the sentence, we should be careful as we also need to do this in-place. When you do in-place reverse of just words, you might need to move the letter further in the string which is unnecessary and confusing.

Approach

  Easy approach is to reverse the whole string using string reverse and then reverse each word one-by-one. I wanted to solve a Google code jam practice problem as well parallel

http://code.google.com/codejam/contest/dashboard?c=351101#s=p1

The above problem requires reversing the words in the strings given as input.

Example:

Input: this is  a test

Output: test a is this

How would do this?

Just string reverse the whole string and then reverse each word one-by-one

Intermediate: tset a si siht

Reverse each word: test a is this

Code

char* str_rev_words(char* str)

{

    char* result = str;

    while(*str != '\0') {

        char* tstr = str;

        char* istr = tstr; // string start

        while(1) {

            if(*(tstr+1) == ' ' || *(tstr+1) == '\0') break;

            tstr++;            

        }

        char* estr = tstr; // string end

        while(!(istr >= estr))

        {

            char tmp = *istr;

            *istr = *estr;

            *estr = tmp;

            istr++;

            estr--;

        }

        if(*(tstr+1) == '\0')

            str = tstr+1;

        else

            str = tstr+2;

    }

    return result;

}

#include <fstream>

using namespace std;

void main()

{

    char line[1000];

    ifstream myfile ("C:\\Works\\cppassignments\\algorithms\\B-large-practice.in");

    ofstream outfile ("C:\\Works\\cppassignments\\algorithms\\result.txt");

    myfile.getline(line, 1000);

    int num_of_cases = atoi(line);

    for(int i=1; i<=num_of_cases; i++)

    {

        myfile.getline(line, 1000);

        // doProblem

        str_rev(line);

        outfile<<"Case #"<<i<<": "<<str_rev_words(line)<<endl;

    }

    outfile.close();

    myfile.close();

}

Important points:

• You must note that not just ‘ ‘ is the separator for the word. When you reach the last word, even ‘\0’ will become the separator.
• BUG FIX: When you are reversing the string using swapping last and first, sometimes, first might go beyond than last so, it should be >= condition.

 

Partitioning Algorithm–In-place

“Think about a problem in which you are given a value. You need to use that value to move all the lesser elements to the left and the greater elements to the right. And most important without using extra space. What would you do? How would you treat the same array as 2 arrays. How we represent a binary heap in an array the same way we do this as well!!”

Introduction

   The partitioning of array is useful for the next algorithm we discuss about sorting, which is quick sort. Why it is quick, is just because of some important properties of partitioning. The partition algorithm gives divide and combine for any algorithm. Its a part of divide and conquer method similar to the merge method discussed for merge sort.

How the division happens?

Divide: Divide an array A[start….end] into two sub arrays, A[start…minindex] and A[maxindex…end-1]. A[start..minindex] will contain values < A[end] and A[maxindex..end-1] contains values > A[end]

This divide step is somewhat similar to binary search, where we divide the problem set by > or <. Similar way, we divide the data set into two parts,

    =

/       \

       <              >

Concept

  What is the use of this division? How the combine step is contributed equally by the partition. If you note, in merge sort, divide is actually done by the merge sort algorithm. Only the combine is done using merge. That’s why, we call merge sort recursion first, and then finally we do a merge. recollect the algorithm of merge!!

    mid = start+end/2

     MERGE-SORT(arr,start,mid)

     MERGE-SORT(arr,mid+1, end)

     MERGE(arr,start,mid,end);

But for quick sort, if you note, the divide & combine both are intrinsic to partition algorithm. So, first, we do partition and then quick sort recursion does the loop through. The lingos are here:

Merge sort: First divide and then merge

Quick sort: First partition and then divide further

Now, you get why we discussed tree traversal also along with this.. :) What we want to do first goes above the recursion loop always.

How a partition takes care of combine as well?

   Always it makes the array to the left and right with the property explained above. So, if we select all the elements as pivot in a 3 element array, it gets sorted. Since you always get partially sorted based over the pivot. partition doesn’t require a separate combine step

Code

void swap(int& a, int& b)

{

    register int tmp;

    tmp = a;

    a=b;

    b=tmp;

}

int partition(int* arr, int start, int end)

{

    /* 

      1. decide a pivot element, let it be arr[end]

      2. categorize arr the remainting start -> end-1 

      3. consider 2 indeces = i,j: initially i=start-1, j=start

      4. make sure that i+1 to j-1 always contains element > pivot

      5. the above means, i marks end of smaller elements array

      6. j marks the end of larger elements array

     */

    /*

    Example:

      start=0                                           end=12

  i=-1   j=0                                            

        3    6    2    1    9    4    12    19    13    10    8    5    11

        After you do this partition,

        start                            i            j       end

        3    6    2    1    9    4    10    8    5    [11]    12    19    13    

    The important point here is, after 4, we see 8 which is < 11.

    So, it needs to be inserted.

    Because of the above point we need 2 indeces.

    */

    int i,j, pivot;

    pivot = arr[end];

    i=start-1;

    for(j=start; j<=end-1; j++)

    {

        if(arr[j] <= pivot) {

            i=i+1;

            swap(arr[i], arr[j]);

        }

    }

    swap(arr[i+1], arr[end]);

    return i+1;

}

void main()

{

    int A[]={3,    6,    2,    1,    9,    4,    12,    19,    13,    10,    8,    5,    11};

    int B[]={6,10,2};

    partition(A,0,12);

    //sorting 3 elements

    int div = partition(B,0,2);

    //small list= 0->div-1

    //large list = div->3

    int l1 = partition(B,div+1,2);

    int l2 = partition(B,l1+1,2);

}

Important points

• partition just divides an array based on a pivot!! and returns the mid index. The index can be start or end as well!!.. since there is always possibility that non of the elements are greater or lesser than pivot
• pivot selection is the very important concept in partition algorithm. Since selection of pivot decides how much sorted you get.
• There is not even a single guarantee that array get sorted by minimal partitions without doing a partition over each and every element. You need to see all the elements in the array and do a partition.
• partition takes O(1) time, when start and end are equal or zero.
• partition at its worst case takes Theta(n) and sometimes since swap is ignored, constant time is lesser!! That’s why, we tell Theta(n) rather than O(n)
• Doing multiple partitions at worst case always leads to Theta(n²) since we need to treat all the elements as pivot. That’s why quicksort worst case is Theta(n²). Quick sort is not so quick as you hear!! :D
• How can multiple partition lead to Theta(log n)? The constant time is the main factor here!! when partition is done on a reducing set, you get same Theta(n).
• There are lots of mathematics studied with such recursive algorithms like quick sort and merge sort!!.. We will learn all those in detail in future

Selection sort & Bubble sort

“Selection sort would have invented when a beautiful mermaid sat and sorted different sized pebbles by pure selection. Compare the full pebble collection and pick the smallest out first.. continue until you get different sized pebbles arranged”

Metaphor

   This is the simplest algorithm and also very important algorithm which has different use cases. Metaphor is the same as the quote. Even your grandma would do this sort in daily life, removing stones out of a rice crunch, organizing smaller to bigger bottles in the kitchen, arranging smaller books to the bigger books purely based on selection. Our mind by default uses selection sort to do day-to-day sorts.

Concept

Wikipedia explains this concept very clearly with the below image,

There is a monkey sort everyone learns named Bubble sort, which compares each number with each other and swaps. Selection sort swaps only after finding the minimum index in the list under study.

Bubble sort is heavily discouraged by everyone. Even interviewers don’t ask questions related to it since even college pass-out treats this as an personal insult.  

Code

   1:  void bubble_sort(int* arr, int size)

   2:  {

   3:      int temp;

   4:      for(int i=0;i<size;i++)

   5:      {

   6:          for(int j=0; j<size;j++)

   7:          {

   8:              if(arr[i] < arr[j])

   9:              {

  10:                  temp = arr[i];

  11:                  arr[i] = arr[j];

  12:                  arr[j] = temp;

  13:              }

  14:          }

  15:      }

  16:  }

  17:  void main()

  18:  {

  19:      int A[]={3,41,52,26,38,57,9,49};

  20:      bubble_sort(A,8);

  21:  }

In the above bubble sort, note the amount of swap done and the total count of operations which is O(n²) which is why people avoid this algorithm altogether. Important notes for even writing this code, I am such a dummy you know

Note:

1. swap never follow any order and swap operates only on indexes. So, You can store arr[i] or arr[j] either of them in temp. i.e, if a[4]=32, a[2] =24 needs to be swapped, don’t confuse with value, see the index 4->2, 2->4 is what happens whatever value they hold the condition safe guards it. Since, a[4] > a[2], the swap won’t happen and only when a[2] < a[4] becomes true, swap happens. So just converting the lesser symbol to greater symbol makes it sort in decreasing order. Note that most of the sorting algorithms have this property.

2. Why swap is so complex? try removing the condition which safeguards swap and check what happens. It gives you something like a dice thrown upon the array. But its not random. Believe me!! It rotates the array by 2 (since its 8*8 rotations along each index) . This will become an interview question . We will discuss this rotations inside an array in far future.

   1:   

   2:  void selection_sort(int *arr, int size)

   3:  {

   4:      int imin = 0;

   5:      int temp;

   6:      for(int i=0; i<size;i++)

   7:      {

   8:          imin = i;

   9:          for(int j=i+1;j<size;j++)

  10:          {

  11:              if(arr[j] < arr[imin])

  12:              {

  13:                  imin = j;

  14:              }

  15:          }

  16:          //swap

  17:          temp = arr[i];

  18:          arr[i] = arr[imin];

  19:          arr[imin] = temp;

  20:      }

  21:  }

  22:   

  23:  void main()

  24:  {

  25:      int A[]={3,41,52,26,38,57,9,49};

  26:      selection_sort(A, 8);

  27:  }

Problems in a selection sort, swap is orderless. So, don’t care. Store only the index where minimum is found and assume ‘i’ as the minimum index at each loop. You need values only for the swap. Even that can be simplified, if there is a routine for swap which takes index.

Important points

• Selection sort has use cases when u just need the minimum values first. There is a data structure called Min Heap which returns minimum value from a heap always. Such data structures operate based on selection sort.
• Selection sort has same complexity equal to bubble sort O(n²). But performs better than bubble sort. But usually all quadratic time algorithms are avoided in real time and large scale projects.
• Read again and review insertion, if you had forgotten by now (i did)http://analgorithmaday.blogspot.com/2010/12/insertion-sort.html 
• In Insertion sort, we select a number in an unsorted list and scan the already sorted list. So, it is faster than Selection sort. But still its O(n²). Speed comes with the difference in the constants that gets hidden with the above notation.