Sorting Flashcards
implementation of Bubble Sort.
Let me help you understand bubble sort by implementing it in Java. I’ll explain each part of the algorithm so you can understand how it works.
public class BubbleSort {
/**
* Sorts an array using the bubble sort algorithm.
* The method works by repeatedly stepping through the array, comparing adjacent
* elements and swapping them if they are in the wrong order. The pass through
* the array is repeated until no swaps are needed.
*
* @param arr The array to be sorted
*/
public static <T extends Comparable<T>> void bubbleSort(T[] arr) {
// Get the length of array for iteration bounds
int n = arr.length;
// Flag to track if any swaps were made in a pass
// This optimization helps us stop early if array becomes sorted
boolean swapped;
// Outer loop represents each pass through the array
// We need at most n-1 passes, as after each pass the largest unsorted
// element "bubbles up" to its correct position at the end
for (int i = 0; i < n - 1; i++) {
// Reset swap flag at the start of each pass
swapped = false;
// Inner loop compares adjacent elements
// Note that we only need to go up to n-i-1 because:
// 1. We compare with j+1, so we need to stop one element before the end
// 2. After each pass, i elements at the end are already in place
for (int j = 0; j < n - i - 1; j++) {
// Compare adjacent elements using compareTo method
// compareTo returns > 0 if the first element is greater than the second
if (arr[j].compareTo(arr[j + 1]) > 0) {
// If elements are in wrong order, swap them
swap(arr, j, j + 1);
// Mark that we made a swap in this pass
swapped = true;
}
}
// If no swapping occurred in this pass, array is already sorted
// This optimization helps us avoid unnecessary passes
if (!swapped) {
break;
}
}
}
/**
* Swaps two elements in an array.
*
* @param arr The array containing elements to swap
* @param i Index of first element
* @param j Index of second element
*/
private static <T> void swap(T[] arr, int i, int j) {
T temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/**
* Demonstrates the bubble sort algorithm with a simple example.
*/
public static void main(String[] args) {
// Create an unsorted array of integers
Integer[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("Original array:");
printArray(arr);
// Sort the array using bubble sort
bubbleSort(arr);
System.out.println("\nSorted array:");
printArray(arr);
}
/**
* Utility method to print an array.
*/
private static <T> void printArray(T[] arr) {
for (T element : arr) {
System.out.print(element + " ");
}
System.out.println();
}
}
Let me explain how bubble sort works and why we implemented it this way:
The bubble sort algorithm gets its name from the way larger elements “bubble up” to their correct positions at the end of the array, similar to how air bubbles rise in water. Here’s what’s happening step by step:
- In each pass through the array, we compare adjacent elements:
- If we find any two adjacent elements that are out of order, we swap them
- By the end of each pass, the largest unsorted element will have “bubbled up” to its correct position
- We’ve included two important optimizations in this implementation:
- We use a
swappedflag to detect if any swaps occurred in a pass. If no swaps occurred, the array is already sorted and we can stop early - In each pass, we don’t need to check the last i elements because they’re already in their final positions
- We use a
- The implementation is generic, meaning it works with any type that implements the Comparable interface. This allows us to sort arrays of integers, strings, or any custom objects that define how they should be compared.
Let’s see how this works with a small example. Consider the array [64, 34, 25]:
~~~
First pass:
Compare 64 and 34: Swap → [34, 64, 25]
Compare 64 and 25: Swap → [34, 25, 64]
Second pass:
Compare 34 and 25: Swap → [25, 34, 64]
Third pass:
No swaps needed, array is sorted!
~~~
Some key characteristics of bubble sort:
- Time complexity: O(n²) in worst and average cases, O(n) in best case (already sorted)
- Space complexity: O(1) as it sorts in-place
- It’s stable, meaning it preserves the relative order of equal elements
- Simple to implement but not efficient for large datasets
implementation of Selection Sort.
Selection Sort is a simple sorting algorithm that divides the array into two parts: the sorted part and the unsorted part. It repeatedly selects the smallest (or largest, depending on the order) element from the unsorted part and swaps it with the first element of the unsorted part, effectively growing the sorted portion of the array.
Steps of Selection Sort
- Start with the first element as the current minimum.
- Compare it with every other element in the unsorted part of the array.
- If a smaller element is found, update the minimum.
- After the iteration, swap the smallest element with the first element of the unsorted part.
- Move to the next element and repeat the process until the array is sorted.
Implementation in Java
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// Find the minimum element in the unsorted part
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum with the first element of the unsorted part
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
System.out.println("Original Array:");
for (int num : arr) {
System.out.print(num + " ");
}
selectionSort(arr);
System.out.println("\nSorted Array:");
for (int num : arr) {
System.out.print(num + " ");
}
} }
Example
Input:
64, 25, 12, 22, 11
Output:
11, 12, 22, 25, 64
Characteristics of Selection Sort
Time Complexity:
Best Case: O(n²)
Worst Case: O(n²)
Space Complexity: O(1) (in-place sort)
Stability: Not stable (as it may swap non-adjacent elements).
Use Case: Suitable for small datasets or when memory usage is a concern.
Insertion Sort
I’ll explain insertion sort in Java, breaking down the concept step by step to help you fully understand the algorithm.
Insertion sort is a simple sorting algorithm that builds the final sorted array one element at a time. It works similarly to how you might sort a hand of playing cards, where you insert each new card into its correct position among the already sorted cards.
Here’s a detailed implementation with explanations:
public class InsertionSort {
/**
* Performs insertion sort on the given array.
*
* @param arr The array to be sorted
*/
public static void insertionSort(int[] arr) {
// Start from the second element (index 1)
// The first element (index 0) is considered already sorted
for (int i = 1; i < arr.length; i++) {
// Store the current element to be inserted
int currentElement = arr[i];
// Initialize the position where we'll insert the current element
// Start with the element just before the current element
int j = i - 1;
// Move elements of arr[0..i-1] that are greater than currentElement
// to one position ahead of their current position
while (j >= 0 && arr[j] > currentElement) {
// Shift the larger element one position to the right
arr[j + 1] = arr[j];
// Move to the previous element
j--;
}
// Insert the current element into its correct position
arr[j + 1] = currentElement;
}
}
/**
* Utility method to print an array
*
* @param arr The array to be printed
*/
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
/**
* Main method to demonstrate insertion sort
*/
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("Original array:");
printArray(arr);
// Perform insertion sort
insertionSort(arr);
System.out.println("Sorted array:");
printArray(arr);
}
}
Let me break down how insertion sort works conceptually:
-
Algorithm Mechanism
- Imagine you’re sorting a hand of playing cards one by one.
- You start with the first card as your initial “sorted” collection.
- For each new card, you find its correct position among the already sorted cards by comparing and shifting.
-
Step-by-Step Process
- The algorithm divides the array into two sections: a sorted portion and an unsorted portion.
- Initially, the first element is considered the sorted portion.
- It iterates through the unsorted portion, taking one element at a time.
- For each element, it finds the right position in the sorted portion by comparing and shifting elements.
-
Time Complexity
- Worst-case time complexity: O(n²)
- Best-case time complexity: O(n) - when the array is already sorted
- Average-case time complexity: O(n²)
-
Space Complexity
- O(1) - it sorts in-place, meaning it doesn’t require additional memory proportional to the input size
-
Advantages
- Simple to implement
- Efficient for small datasets
- Adaptive (performs well on nearly sorted arrays)
- Stable sorting algorithm (maintains the relative order of equal elements)
-
Disadvantages
- Inefficient for large datasets
- Quadratic time complexity makes it slow for big arrays
When you run the provided code, it will demonstrate the sorting process by showing the original and sorted arrays.
we will take two sorted arrays and merge them.
Naive Code
#include (iostream>#include (algorithm>using namespace std;
void merge(int a[], int b[], int m, int n){ int c[m+n]; for(int i=0;i(m;i++) c[i]=a[i]; for(int j=0;j(n;j++) c[j+m]=b[j]; sort(c,c+m+n); for(int i=0;i(m+n;i++) cout((c[i]((" ";}
int main() { int a[]={10,15,20,40}; int b[]={5,6,6,10,15};int m=sizeof(a)/sizeof(a[0]);int n=sizeof(b)/sizeof(b[0]);merge(a,b,m,n);}
Efficient Code
#include (iostream>#include (algorithm>using namespace std;
void merge(int a[], int b[], int m, int n){ int i=0,j=0; while(i(m && j(n){ if(a[i](b[j]) cout((a[i++]((" "; else cout((b[j++]((" "; } while(i(m) cout((a[i++]((" "; while(j(n) cout((b[j++]((" "; }
int main() { int a[]={10,15,20,40}; int b[]={5,6,6,10,15};int m=sizeof(a)/sizeof(a[0]);int n=sizeof(b)/sizeof(b[0]);merge(a,b,m,n);}Merge function of merge sort
#include (iostream>#include (algorithm>using namespace std;
void merge(int arr[], int l, int m, int h){ int n1=m-l+1, n2=h-m; int left[n1],right[n2]; for(int i=0;i(n1;i++) left[i]=arr[i+l]; for(int j=0;j(n2;j++) right[j]=arr[m+1+j]; int i=0,j=0,k=l; while(i(n1 && j(n2){ if(left[i](=right[j]) arr[k++]=left[i++]; else arr[k++]=right[j++]; } while(i(n1) arr[k++]=left[i++]; while(j(n2) arr[k++]=right[j++]; }
int main() { int a[]={10,15,20,40,8,11,15,22,25};int l=0,h=8,m=3;merge(a,l,m,h);for(int x: a) cout((x((" ";}Merge Sorting Algorithm
#include (iostream>
#include (algorithm>
using namespace std;
void merge(int arr[], int l, int m, int h){
int n1=m-l+1, n2=h-m;
int left[n1],right[n2];
for(int i=0;i(n1;i++)
left[i]=arr[i+l];
for(int j=0;j(n2;j++)
right[j]=arr[m+1+j];
int i=0,j=0,k=l;
while(i(n1 && j(n2){
if(left[i](=right[j])
arr[k++]=left[i++];
else
arr[k++]=right[j++];
}
while(i(n1)
arr[k++]=left[i++];
while(j(n2)
arr[k++]=right[j++];
}
void mergeSort(int arr[],int l,int r){
if(r>l){
int m=l+(r-l)/2;
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}
}
int main() {
int a[]={10,5,30,15,7};
int l=0,r=4;
mergeSort(a,l,r);
for(int x: a)
cout((x((" ";
}partitioning method is a naive way of approach towards partitioning an array.
#include (bits/stdc++.h>using namespace std;
void partition(int arr[], int l, int h, int p){ int temp[h-l+1],index=0; for(int i=l;i(=h;i++) if(arr[i](=arr[p] && i != p) { temp[index]=arr[i];index++; } temp[index++] = arr[p]; for(int i=l;i(=h;i++) if(arr[i]>arr[p]) { temp[index]=arr[i];index++; } for(int i=l;i(=h;i++) arr[i]=temp[i-l];}int main() { int arr[]={5,13,6,9,12,11,8};int n=sizeof(arr)/sizeof(arr[0]);partition(arr,0,n-1,3);for(int x: arr) cout((x((" ";}Lomuto Partition whichis another method of partitioning. In this method, the traversal is done only once with a constant space complexity.
In the Lomuto partition scheme, usually the last element of the list is chosen as the pivot element.
Two pointers are also maintained for tracking and comparison purposes. A pointer i is maintained while another pointer j is scanning through the array, from its starting all the way to the end (up to the pivot element). The scan ensures that any element e₀ that is present from the starting point of the array to the (i-1)ᵗʰ index is lesser than the pivot element in terms of value and the elements present at any index ranging from i to j are equal to or bigger than the pivot element in terms of value.
Through this technique, the array will be sorted by the time we reach the end of the array.
#include (bits/stdc++.h>using namespace std;
int iPartition(int arr[], int l, int h){ int pivot=arr[h]; int i=l-1; for(int j=l;j(=h-1;j++){ if(arrj{ i++; swap(arr[i],arr[j]); } } swap(arr[i+1],arr[h]); return i+1;}int main() { int arr[]={10,80,30,90,40,50,70};int n=sizeof(arr)/sizeof(arr[0]);iPartition(arr,0,n-1);for(int x: arr) cout((x((“ “;}
Hoare Partition whichis another method of partitioning. This is better than the previously discussed Partitioning method. Thismethod takesconstant space and O(n) time for partitioning. It also travels the input array only once.
Hoare’s Partition Scheme works by initializing two indexes that start at two ends, the two indexes move toward each other until an inversion is (A smaller value on the left side and greater value on the right side) found. When an inversion is found, two values are swapped and the process is repeated.
Algorithm: partition(arr[], lo, hi) pivot = arr[lo] i = lo - 1 // Initialize left index j = hi + 1 // Initialize right index // Find a value in left side greaterthan pivot do i = i + 1 while arr[i] ( pivot // Find a value in right side smaller than pivot do j--; while (arr[j] > pivot); if i >= j then return j swap arr[i] with arr[j]
Below are implementations of this approach:-
/* C++ implementation of QuickSort using Hoare'spartition scheme.
#include (bits/stdc++.h>
using namespace std;
/* This function takes first element as pivot, and places all the elements smaller than the pivot on the left side and all the elements greater than the pivot on the right side. It returns the index of the last element on the smaller side*/
int partition(int arr[], int low, int high){
int pivot = arr[low];
int i = low - 1, j = high + 1;
while (true) {
// Find leftmost element greater than or equal to pivot
do { i++;
} while (arr[i] ( pivot);
// Find rightmost element smaller than or equal to pivot
do { j--;
} while (arr[j] > pivot);
// If two pointers met.
if (i >= j) return j;
swap(arr[i], arr[j]);
}
}
/* The main function that implements QuickSort arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high){
if (low ( high) {
/* pi is partitioning index,
arr[p] is nowat right place */
int pi = partition(arr, low, high);
// Separately sort elements beforepartition and after partition
quickSort(arr, low, pi);
quickSort(arr, pi + 1, high);
}
}
/* Function to print an array */
void printArray(int arr[], int n){
for (int i = 0; i ( n; i++)
printf("%d ", arr[i]);
printf("\n");}
// Driver Code
int main(){
int arr[] = { 10, 7, 8, 9, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Note : If we change Hoare’s partition to pick the last element as pivot, then the Hoare’s partition may cause QuickSort to go into in an infinite recursion. For example, {10, 5, 6, 20} and pivot is arr[high], then returned index will always be high and call to same QuickSort will be made. To handle a random pivot, we can always swap that random element with the first element and simply follow the above algorithm.
Comparison:
- Hoare’s scheme is more efficient than Lomuto’s partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal.
- Like Lomuto’s partition scheme, Hoare partitioning also causes Quick sort to degrade to O(n^2) when the input array is already sorted, it also doesn’t produce a stable sort.
- Note that in this scheme, the pivot’s final location is not necessarily at the index that was returned, and the next two segments that the main algorithm recurs on are (lo..p) and (p+1..hi) as opposed to (lo..p-1) and (p+1..hi) as in Lomuto’s scheme.
QuickSort using the method ofLomuto Partition.
#include (bits/stdc++.h>using namespace std;
int iPartition(int arr[], int l, int h){ int pivot=arr[h]; int i=l-1; for(int j=l;j(=h-1;j++){ if(arr[j](pivot){ i++; swap(arr[i],arr[j]); } } swap(arr[i+1],arr[h]); return i+1;}
void qSort(int arr[],int l,int h){ if(l(h){ int p=iPartition(arr,l,h); qSort(arr,l,p-1); qSort(arr,p+1,h); }}int main() { int arr[]={8,4,7,9,3,10,5};int n=sizeof(arr)/sizeof(arr[0]);qSort(arr,0,n-1);for(int x: arr) cout((x((" ";}QuickSort using the method ofHoare Partition.
#include (bits/stdc++.h>
using namespace std;
int partition(int arr[], int l, int h){
int pivot=arr[l];
int i=l-1,j=h+1;
while(true){
do{
i++;
}while(arr[i](pivot);
do{
j--;
}while(arr[j]>pivot);
if(i>=j)return j;
swap(arr[i],arr[j]);
}
}
void qSort(int arr[],int l,int h){
if(l(h){
int p=partition(arr,l,h);
qSort(arr,l,p);
qSort(arr,p+1,h);
}
}
int main() {
int arr[]={8,4,7,9,3,10,5};
int n=sizeof(arr)/sizeof(arr[0]);
qSort(arr,0,n-1);
for(int x: arr)
cout((x((" ";
}
Heap Sort with implementation.
Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the minimum element and place the minimum element at the beginning. We repeat the same process for the remaining elements.
What is Binary Heap?
Let us first define a Complete Binary Tree. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible (Source Wikipedia)
A Binary Heap is a Complete Binary Tree where items are stored in a special order such that the value in a parent node is greater(or smaller) than the values in its two children nodes. The former is called max heap and the latter is called min-heap. The heap can be represented by a binary tree or array.
Why array based representation for Binary Heap?
Since a Binary Heap is a Complete Binary Tree, it can be easily represented as an array and the array-based representation is space-efficient. If the parent node is stored at index I, the left child can be calculated by 2 * I + 1 and the right child by 2 * I + 2 (assuming the indexing starts at 0).
How to “heapify” a tree?
The process of reshaping a binary tree into a Heap data structure is known as ‘heapify’. A binary tree is a tree data structure that has two child nodes at max. If a node’s children nodes are ‘heapified’, then only ‘heapify’ process can be applied over that node. A heap should always be a complete binary tree.
Starting from a complete binary tree, we can modify it to become a Max-Heap by running a function called ‘heapify’ on all the non-leaf elements of the heap. i.e. ‘heapify’ uses recursion.
Algorithm for “heapify”:
heapify(array)
Root = array[0]
Largest = largest( array[0] , array [2 * 0 + 1]. array[2 * 0 + 2])
if(Root != Largest)
Swap(Root, Largest)
Heap Sort Algorithm for sorting in increasing order:
- Build a max heap from the input data.
- At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of the tree.
- Repeat step 2 while the size of the heap is greater than 1.
How to build the heap?
Heapify procedure can be applied to a node only if its children nodes are heapified. So the heapification must be performed in the bottom-up order.
// C++ program for implementation of Heap Sort
#include (iostream>
using namespace std;
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root if (l ( n && arr[l] > arr[largest]) largest = l;
// If right child is larger than largest so far if (r ( n && arr[r] > arr[largest]) largest = r;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree heapify(arr, n, largest); } }
// main function to do heap sort
void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap heapify(arr, i, 0); } }
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
for (int i = 0; i ( n; ++i)
cout (( arr[i] (( " ";
cout (( "\n";
}
// Driver code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout (( "Sorted array is \n"; printArray(arr, n); } Notes: Heap sort is an in-place algorithm. Its typical implementation is not stable, but can be made stable (See this)
Time Complexity: Time complexity of heapify is O(Logn). Time complexity of createAndBuildHeap() is O(n) and the overall time complexity of Heap Sort is O(nLogn).
Advantages of heapsort –
Efficiency – The time required to perform Heap sort increases logarithmically while other algorithms may grow exponentially slower as the number of items to sort increases. This sorting algorithm is very efficient.
Memory Usage – Memory usage is minimal because apart from what is necessary to hold the initial list of items to be sorted, it needs no additional memory space to work
Simplicity – It is simpler to understand than other equally efficient sorting algorithms because it does not use advanced computer science concepts such as recursion
Counting Sort, a linear time sorting algorithm for limited range elements.
Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.
Let us understand it with the help of an example.
For simplicity, consider the data in the range 0 to 9.
Input data: 1, 4, 1, 2, 7, 5, 2
1) Take a count array to store the count of each unique object.
Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 2 2 0 1 1 0 1 0 0
2) Modify the count array such that each element at each index
stores the sum of previous counts.
Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 2 4 4 5 6 6 7 7 7
The modified count array indicates the position of each object in
the output sequence.
3) Rotate the array clockwise for one time.
Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 0 2 4 4 5 6 6 7 7
4) Output each object from the input sequence followed by
increasing its count by 1.
Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 0.
Put data 1 at index 0 in output. Increase count by 1 to place
next data 1 at an index 1 greater than this index.
// C++ Program for counting sort #include #include using namespace std; #define RANGE 255
// The main function that sort
// the given string arr[] in
// alphabetical order
void countSort(char arr[])
{
// The output character array
// that will have sorted arr
char output[strlen(arr)];
// Create a count array to store count of individual // characters and initialize count array as 0 int count[RANGE + 1], i; memset(count, 0, sizeof(count));
// Store count of each character for (i = 0; arr[i]; ++i) \++count[arr[i]];
// Change count[i] so that count[i] now contains actual // position of this character in output array for (i = 1; i <= RANGE; ++i) count[i] += count[i - 1];
// Build the output character array
for (i = 0; arr[i]; ++i) {
output[count[arr[i]] - 1] = arr[i];
--count[arr[i]];
}
/*
For Stable algorithm
for (i = sizeof(arr)-1; i>=0; --i)
{
output[count[arr[i]]-1] = arr[i];
--count[arr[i]];
}
For Logic : See implementation */
// Copy the output array to arr, so that arr now // contains sorted characters for (i = 0; arr[i]; ++i) arr[i] = output[i]; }
// Driver code
int main()
{
char arr[] = "geeksforgeeks";
countSort(arr); cout << "Sorted character array is " << arr; return 0; }
Time Complexity: O(n+k) where n is the number of elements in input array and k is the range of input.
Auxiliary Space: O(n+k)
Points to be noted:
1. Counting sort is efficient if the range of input data is not significantly greater than the number of objects to be sorted. Consider the situation where the input sequence is between range 1 to 10K and the data is 10, 5, 10K, 5K.
2. It is not a comparison based sorting. It running time complexity is O(n) with space proportional to the range of data.
3. It is often used as a sub-routine to another sorting algorithm like radix sort.
4. Counting sort uses a partial hashing to count the occurrence of the data object in O(1).
5. Counting sort can be extended to work for negative inputs also.
implementation of Radix Sort
Radix sort is a sorting algorithm that sorts the elements by first grouping the individual digits of the same place value. Then, sort the elements according to their increasing/decreasing order.
Suppose, we have an array of 8 elements. First, we will sort elements based on the value of the unit place. Then, we will sort elements based on the value of the tenth place. This process goes on until the last significant place.
Let the initial array be [121, 432, 564, 23, 1, 45, 788]. It is sorted according to radix sort as shown in the figure below.
Working of Radix Sort
1 Find the largest element in the array, i.e. max. Let X be the number of digits in max. X is calculated because we have to go through all the significant places of all elements.
In this array [121, 432, 564, 23, 1, 45, 788], we have the largest number 788. It has 3 digits. Therefore, the loop should go up to hundreds place (3 times).
2 Now, go through each significant place one by one.
Use any stable sorting technique to sort the digits at each significant place. We have used counting sort for this.
Sort the elements based on the unit place digits (X=0).
3 Now, sort the elements based on digits at tens place.
4 Finally, sort the elements based on the digits at hundreds place.
Radix Sort Algorithm
radixSort(array)
d (- maximum number of digits in the largest element
create d buckets of size 0-9
for i (- 0 to d
sort the elements according to ith place digits using countingSort
countingSort(array, d)
max (- find largest element among dth place elements
initialize count array with all zeros
for j (- 0 to size
find the total count of each unique digit in dth place of elements and
store the count at jth index in count array
for i (- 1 to max
find the cumulative sum and store it in count array itself
for j (- size down to 1
restore the elements to array
decrease count of each element restored by 1
// Using counting sort to sort the elements in the basis of significant places
void countingSort(int array[], int size, int place) {
const int max = 10;
int output[size];
int count[max];
for (int i = 0; i ( max; ++i)
count[i] = 0;
// Calculate count of elements
for (int i = 0; i ( size; i++)
count[(array[i] / place) % 10]++;
// Calculate cumulative count
for (int i = 1; i ( max; i++)
count[i] += count[i - 1];
// Place the elements in sorted order
for (int i = size - 1; i >= 0; i--) {
output[count[(array[i] / place) % 10] - 1] = array[i];
count[(array[i] / place) % 10]--;
}
for (int i = 0; i ( size; i++)
array[i] = output[i];
}
// Main function to implement radix sort
void radixsort(int array[], int size) {
// Get maximum element
int max = getMax(array, size);
// Apply counting sort to sort elements based on place value.
for (int place = 1; max / place > 0; place *= 10)
countingSort(array, size, place);
}
// Print an array
void printArray(int array[], int size) {
int i;
for (i = 0; i ( size; i++)
cout (( array[i] (( " ";
cout (( endl;
}
// Driver code
int main() {
int array[] = {121, 432, 564, 23, 1, 45, 788};
int n = sizeof(array) / sizeof(array[0]);
radixsort(array, n);
printArray(array, n);
}
Radix Sort Complexity Time Complexity Best O(n+k) Worst O(n+k) Average O(n+k) Space Complexity O(max) Stability Yes
Since radix sort is a non-comparative algorithm, it has advantages over comparative sorting algorithms.
For the radix sort that uses counting sort as an intermediate stable sort, the time complexity is O(d(n+k)).
Bucket Sort algorithm
#include(bits/stdc++.h>using namespace std;
void bucketSort(int arr[], int n, int k){ int max_val=arr[0]; for(int i=1;i(n;i++) max_val=max(max_val,arr[i]); max_val++; vector(int> bkt[k]; for (int i = 0; i ( n; i++) { int bi = (k * arr[i])/max_val; bkt[bi].push_back(arr[i]); } for (int i = 0; i ( k; i++) sort(bkt[i].begin(), bkt[i].end()); int index = 0; for (int i = 0; i ( k; i++) for (int j = 0; j ( bkt[i].size(); j++) arr[index++] = bkt[i][j];}
int main(){ int arr[] = { 30,40,10,80,5,12,70 }; int n = sizeof(arr) / sizeof(arr[0]); int k=4; bucketSort(arr, n, k); for (int i = 0; i ( n; i++) cout (( arr[i] (( " "; return 0;}
