Merge sort is a divide-and-conquer sorting algorithm that works by recursively dividing an array into two halves until each half contains only one element, and then merging the sorted halves back together. The merging process involves comparing the elements of the two sorted subarrays and selecting the smaller of the two to be placed in the next position of the merged array. This process is repeated until all the elements have been merged into a single sorted array.
public static ArrayList⋖Integer⋗ mergeSort(ArrayList ⋖Integer⋗ array, int left, int right){
if(left+1==right){
ArrayList ⋖Integer⋗ array1 = new ArrayList ⋖Integer⋗();
array1.add(array.get(left));
return array1;
}
int mid = (right+left)/2;
ArrayList ⋖Integer⋗ a = mergeSort(array,left,mid);
ArrayList ⋖Integer⋗ b = mergeSort(array,mid,right);
ArrayList ⋖Integer⋗ sortedArray = new ArrayList ⋖Integer⋗();
int aPointer = 0;
int bPointer = 0;
int length = a.size() + b.size();
for(int i = 0; i⋖length;i++){
if(aPointer⋗=a.size()){
sortedArray.add(b.get(bPointer));
bPointer++;
}
else if(bPointer⋗=b.size()){
sortedArray.add(a.get(aPointer));
aPointer++;
}
else{
if(a.get(aPointer) ⋖ b.get(bPointer)){
sortedArray.add(a.get(aPointer));
aPointer++;
}
else{
sortedArray.add(b.get(bPointer));
bPointer++;
}
}
}
return sortedArray;
}
What is shell sort?
Shell sort is an in-place comparison-based sorting algorithm that is a variation of insertion sort. It starts by sorting pairs of elements far apart from each other, and then progressively reduces the gap between the elements being compared until the gap is 1. At this point, the algorithm is essentially performing an insertion sort on a partially sorted array, which is much more efficient than performing insertion sort on an unsorted array. The gap sequence used for shell sort can vary.
public static ArrayList⋖Integer⋗ shellSort(ArrayList ⋖Integer> array1){
ArrayList ⋖Integer> array = new ArrayList⋖Integer⋗();
for(int i = 0; i⋖array1.size(); i++){
array.add(array1.get(i));
}
for(int i = array.size()/2; i⋗0; i/=2){
for(int j = i; j⋖array.size(); j++){
int k = j;
while(k⋗=i && array.get(k-i) ⋗ array.get(k)){
int temp = array.get(k);
array.set(k, array.get(k-i));
array.set(k-i, temp);
k -= i;
}
}
}
}
What is quick sort?
Quick sort follows the divide-and-conquer approach. It works by selecting a pivot element from the array and partitioning the remaining elements into two sub-arrays, according to whether they are less than or greater than the pivot element. This process is repeated recursively for each sub-array until the entire array is sorted.
public static ArrayList ⋖Integer⋗ quickSort(ArrayList ⋖Integer> array, int left, int right){
if (left ⋖ right) {
int x = partition(array, left, right);
quickSort(array, left, x - 1);
quickSort(array, x + 1, right);
}
return array;
}
public static int partition(ArrayList ⋖Integer⋗ array, int left, int right){
Integer pivot = array.get(right);
int i = (left - 1);
for (int j = left; j ⋖ right; j++) {
if (array.get(j) ⋖= pivot) {
i++;
int temp = array.get(i);
array.set(i, array.get(j));
array.set(j, temp);
}
}
int temp = array.get(i+1);
array.set(i+1, array.get(right));
array.set(right, temp);
return i+1;
}
What is radix sort?
Radix sort is a sorting algorithm that works by sorting numbers one digit at a time, from the least significant digit to the most significant digit. It relies on the property that numbers with more digits are always greater than numbers with fewer digits. The algorithm sorts the input numbers by grouping them into buckets according to their least significant digit, then sorting each bucket by the next significant digit, and so on, until all digits have been sorted.
public static void radixSort(ArrayList ⋖Integer⋗ array){
ArrayList ⋖CircularLinkedList ⋖Integer⋗⋗ buckets = new ArrayList ⋖CircularLinkedList ⋖Integer⋗⋗();
for(int i = 0; i⋖10; i++){
buckets.add(new CircularLinkedList ⋖Integer⋗());
}
int max = array.get(0);
for (int i = 0; i ⋖ array.size(); i++) {
if (array.get(i) ⋗ max)
max = array.get(i);
}
int digits = (int)(Math.log10(max)+1);
for(int i = 0; i⋖digits; i++){
for(int j = 0; j⋖array.size(); j++){
int x = array.get(j);
int d = x/((int)Math.pow(10,i))%10;
buckets.get(d).append(x);
}
int counter = 0;
for(int j = 0; j⋖10; j++){
while(!buckets.get(j).isEmpty()){
array.set(counter, buckets.get(j).pop());
counter++;
}
}
}
}
Resources
I find https://visualgo.net/en/sorting a very helpful way to visualize how the sorting algorithms work through the data sets. First, navigate to the sorting algorithm you want to see and then you have the option to create your own data set or use the randomly generated one. Click sort to start the animation.
