Basically, as the name suggests that 3-Way Radix Quicksort is a combination of both radix and 3-way quicksort. It is a hybrid sort which is in between of both radix and 3-way quicksort. This algorithm is mainly used to sort strings.
The main idea behind the radix sort is to use the digits (beginning from LSD to MSD) of all the integers to perform hashing and dividing them into a separate list and then joining. In the same way, we will be using the MSD character of the strings and then using these characters we go on performing what is known as 3-way quicksort.
3-way quicksort is basically a case of general quicksort only. The idea is that if we use quicksort then there can be a situation that we would get the same characters in the array of characters(here we are sorting strings using radix sort idea, to take all the Characters one by one to sort).
So to handle such a situation we divide the array into three parts:
- The partition contains characters less than the pivot character.
- The partition for characters that are equal to that of the pivot character.
- The last partition contains characters that are greater than the pivot character.
So basically what is going to happen is :
- We would consider the MSD character of each string(the idea of radix sort).
- Then we will perform quicksort on this array of characters, which will result in the partition of the array into 3 parts(as discussed above).
This division is shown in the below figure.
Explanation of image:
- So basically as shown that there are 11 strings in the array, and we have to sort them. So now considering the first character of all strings gives an array of {s,a,h,s,s,z,b,t,c,u,s}. This is the idea got from radix sort. Now we are to sort this array of characters on the basis of the idea of quick sort.
- So here the pivot element we are considering is first element of array i.e. ‘s’. Now we are using quicksort to make partition. Partitions are done on the basis that :
- First we are considering the first character as the pivot and also we have to pointers ‘i’ and ‘j’. Pointer ‘i’ moves from start to end and ‘j’ moves from end to start. Initially i=1 and j =n-1; this would help us to get the two boundary index of the second partition.
- Ranges of partition than would be 1st one form 0 – i , 2nd form i+1 – j-1 and third form j to n-1;
- if arr[i]<pivot: pivot is swapped with arr[i] (please Note that here string are swapped and not the characters of the string)
- if arr[i]==pivot it is remained there only, and the pointer is incremented to next one.
- if arr[i]>pivot, the string at j is swapped with arr[i] string and j is decremented.
So after performing these operations we will get the three partitioned array as shown.
After getting the partitions we can see that in the second one we are not able to recursively perform quicksort on the first character of string since in that partition all the strings are having the same first character(here in this example it is ‘s’). So we will be going for doing partition on the basis of the next character. And for the other two, we will recall the same sort again starting from the first character. This is the whole idea about 3-way quicksort.
The main thing here to notice that is all string are not of the same length so at some step we can have a condition that there will be no further characters of the pivot string and other strings are having characters and hence swapping and comparisons of the characters are not possible in that case.
So to handle that case we would first find the max length of strings in the array and then append each string with a character that has ASCII value smaller than the alphabet.
Why smaller?
consider an example:
Array is a={hero, heroes, her}
Here if we give each string with fewer characters than the max amount needed(i.e. 6) a character which is greater than alphabets (say ‘~’), then a will become a={hero~~, heroes, her~~~}.
sorting this array would give the result as {heroes, hero~~, her~~~} but the real answer should be {her, hero, heroes}.
Performing the above algorithm recursively will generate a sorted array and hence we will be able to sort the array of strings.
Recursive Implementation:
Java
// Java program for 3-Way Radix Quicksortimport java.io.BufferedInputStream;import java.io.FileInputStream;import java.io.FileNotFoundException;import java.io.FileOutputStream;import java.io.IOException;import java.io.InputStream;import java.util.Enumeration;import java.util.Scanner;import java.util.zip.ZipEntry;import java.util.zip.ZipFile;import java.util.zip.ZipInputStream;public class GFG { // swapping method. public static void swp(String[] s, int x, int y) { String tmp = s[x]; s[x] = s[y]; s[y] = tmp; } // sort method. public static void srt(String[] s, int start, int last, int character_index) { // base condition if no further index possible. if (start >= last) return; // first making a start pointer for dividing the // list from start to start_pointer. int start_pointer = start; // last_pointer and last are the boundaries for the // third list. int last_pointer = last; // taking the ascii value of the pivot at the index // given. int char_ascii_value_pivot = s[start].charAt(character_index); int pointer = start + 1; // starting a pointer to scan the whole array to // sort. while (pointer <= last) { // ASCII value of char at the position of all // the strings to compare with that of the pivot // char. int char_ascii_value_element = s[pointer].charAt(character_index); // if the element has char less than pivot than // swapping it with the top element and // incrementing the top boundary of the first // list. if (char_ascii_value_pivot > char_ascii_value_element) { swp(s, start_pointer, pointer); start_pointer++; // incrementing the pointer to check for // next string. pointer++; } else // if found larger character than it is // replaced by the element at last_pointer // and lower boundary is raised by // decrementing it. if (char_ascii_value_pivot < char_ascii_value_element) { swp(s, last_pointer, pointer); last_pointer--; pointer++; } // if character is the same as that of the pivot // then no need to swap and move the pointer on else { pointer++; } } // now performing same sort on the first list // bounded by start and start_pointer with same // character_index srt(s, start, start_pointer - 1, character_index); // if we have more character left in the pivot // element than recall quicksort on the second list // bounded by start_pointer and last_pointer and // next character_index. if (char_ascii_value_pivot >= 0) srt(s, start_pointer, last_pointer, character_index + 1); // lastly the third list with boundaries as // last_pointer and last. srt(s, last_pointer + 1, last, character_index); } public static void main(String[] args) throws Exception { // predefined array of five element all of same // length. String s[] = { "some", "same", "hero", "make", "zero" }; // calling sort function to sort the array using // 3-way-radix-quicksort. srt(s, 0, 4, 0); // printing the sorted array; // here we are calling function by passing parameters // using references . for (int i = 0; i < 5; ++i) System.out.println(s[i]); }} |
hero make same some zero
Example 2: To sort strings with different lengths.
Java
// Java program for 3-Way radix QuickSortimport java.io.BufferedInputStream;import java.io.FileInputStream;import java.io.FileNotFoundException;import java.io.FileOutputStream;import java.io.IOException;import java.io.InputStream;import java.util.Enumeration;import java.util.Scanner;import java.util.zip.ZipEntry;import java.util.zip.ZipFile;import java.util.zip.ZipInputStream;public class GFG { // swapping method. public static void swp(String[] s, int x, int y) { String tmp = s[x]; s[x] = s[y]; s[y] = tmp; } // sort method. public static void srt(String[] s, int start, int last, int character_index) { // base condition if no further index possible. if (start >= last) return; // first making a start pointer for dividing the // list from start to start_pointer. int start_pointer = start; // last_pointer and last are the boundaries for the // third list. int last_pointer = last; // taking the ASCII value of the pivot at the index // given. int char_ascii_value_pivot = s[start].charAt(character_index); int pointer = start + 1; // starting a pointer to scan the whole array to // sort. while (pointer <= last) { // ASCII value of char at the position of all // the strings to compare with that of the pivot // char. int char_ascii_value_element = s[pointer].charAt(character_index); // if the element has char less than pivot than // swapping it with the top element and // incrementing the top boundary of the first // list. if (char_ascii_value_pivot> char_ascii_value_element) { swp(s, start_pointer, pointer); start_pointer++; // incrementing the pointer to check for // next string. pointer++; } else // if found larger character than it is // replaced by the element at last_pointer // and lower boundary is raised by // decrementing it. if (char_ascii_value_pivot< char_ascii_value_element) { swp(s, last_pointer, pointer); last_pointer--; pointer++; } // if character is same as that of the pivot then // no need to swap and move the pointer on else { pointer++; } } // now performing same sort on the first list // bounded by start and start_pointer with same // character_index srt(s, start, start_pointer - 1, character_index); // if we have more character left in the pivot // element than recall quicksort on the second list // bounded by start_pointer and last_pointer and // next character_index. if (char_ascii_value_pivot >= 0) srt(s, start_pointer, last_pointer,character_index + 1); // lastly the third list with boundaries as // last_pointer and last. srt(s, last_pointer + 1, last, character_index); } public static void main(String[] args) throws Exception { // predefined array of five element all of different // length. String s[] = { "sam", "same", "her", "make", "zebra" }; int max_character_index = 0; // finding max_character_index for (int i = 0; i < 5; ++i) if (s[i].length() > max_character_index) max_character_index = s[i].length(); // adding each string with a character having less // ascii value than alphabets. for (int i = 0; i < 5; ++i) if (s[i].length() < max_character_index) while (s[i].length() < max_character_index) s[i] += '?'; // calling sort function to sort the array using // 3-way-radix-quicksort. srt(s, 0, 4, 0); // printing the sorted array; // here we are calling function by passing // parameters using references . printing without the // appended character. for (int i = 0; i < 5; ++i) { String ans = ""; for (int j = 0; j < s[i].length(); ++j) if (s[i].charAt(j) != '?') ans += s[i].charAt(j); else break; System.out.println(ans); } }} |
her make sam same zebra
