Coding Interview QuestionsInterview Questions and Answers
Top 50 Sorting Interview Questions
Introductions
Sorting interview questions are a common topic that assesses a candidate’s problem-solving and algorithmic skills. Sorting involves arranging a collection of items in a specific order, such as ascending or descending. These questions explore a candidate’s understanding of various sorting algorithms like bubble sort, merge sort, and quicksort. They may require analyzing the time and space complexity of different approaches and identifying the most efficient solution for a given scenario. Sorting questions test a candidate’s ability to think critically, write clean code, and optimize algorithms, making them an essential aspect of technical interviews for software engineering and computer science roles.
Questions
1. Describe Bubble Sort.
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
C++
#include <iostream>
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, size);
std::cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}2. Explain QuickSort.
QuickSort is a highly efficient and widely used sorting algorithm based on the divide-and-conquer strategy. It picks an element as a pivot and partitions the array around the pivot, such that elements less than the pivot are on the left, and elements greater than the pivot are on the right. It then recursively sorts the left and right partitions.
C++
#include <iostream>
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, size - 1);
std::cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}3. Explain Merge Sort and its time complexity.
Merge Sort is a divide-and-conquer sorting algorithm. It divides the unsorted list into n sublists, each containing one element, and then repeatedly merges sublists to produce new sorted sublists until there is only one sorted sublist remaining.
The time complexity of Merge Sort is O(n log n).
C++
#include <iostream>
void merge(int arr[], int left, int mid, int right) {
int leftSize = mid - left + 1;
int rightSize = right - mid;
int* leftArr = new int[leftSize];
int* rightArr = new int[rightSize];
for (int i = 0; i < leftSize; i++)
leftArr[i] = arr[left + i];
for (int j = 0; j < rightSize; j++)
rightArr[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < leftSize && j < rightSize) {
if (leftArr[i] <= rightArr[j])
arr[k++] = leftArr[i++];
else
arr[k++] = rightArr[j++];
}
while (i < leftSize)
arr[k++] = leftArr[i++];
while (j < rightSize)
arr[k++] = rightArr[j++];
delete[] leftArr;
delete[] rightArr;
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
std::cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}4. Explain Heap Sort, its time complexity, and when it might be used.
Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It first builds a max heap (for ascending order) or a min heap (for descending order) from the elements and then repeatedly extracts the root element, which is the maximum (or minimum) value, and rebuilds the heap until the array is sorted.
The time complexity of Heap Sort is O(n log n).
C++
#include <iostream>
void heapify(int arr[], int size, int root) {
int largest = root;
int leftChild = 2 * root + 1;
int rightChild = 2 * root + 2;
if (leftChild < size && arr[leftChild] > arr[largest])
largest = leftChild;
if (rightChild < size && arr[rightChild] > arr[largest])
largest = rightChild;
if (largest != root) {
std::swap(arr[root], arr[largest]);
heapify(arr, size, largest);
}
}
void heapSort(int arr[], int size) {
// Build max heap
for (int i = size / 2 - 1; i >= 0; i--)
heapify(arr, size, i);
// Extract elements one by one
for (int i = size - 1; i >= 0; i--) {
std::swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, size);
std::cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}5. Explain the difference between QuickSort, MergeSort, and HeapSort
| Algorithm | Time Complexity | Space Complexity | Stable? | Suitable for Large Data? |
|---|---|---|---|---|
| QuickSort | O(n log n) | O(log n) | No | Yes |
| MergeSort | O(n log n) | O(n) | Yes | Yes |
| HeapSort | O(n log n) | O(1) | No | Yes |
6. Explain Insertion Sort and when it is considered efficient.
Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It takes an element and inserts it into the correct position in the sorted part of the array.
Insertion Sort is efficient for small data sets or nearly sorted data. Its time complexity is O(n^2) in the worst and average cases, but it can perform better than other algorithms for small data sets.
C++
#include <iostream>
void insertionSort(int arr[], int size) {
for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, size);
std::cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}7. Explain Selection Sort and how it operates.
Selection Sort is a simple sorting algorithm that divides the input list into two parts: the sorted part on the left and the unsorted part on the right. It repeatedly finds the minimum (or maximum) element from the unsorted part and moves it to the end of the sorted part.
C++
#include <iostream>
void selectionSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
std::swap(arr[i], arr[minIndex]);
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, size);
std::cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}8. What is a stable sort, and what sorts would be considered stable?
A stable sort is a sorting algorithm that preserves the relative order of equal elements in the sorted output as they appear in the input.
Examples of stable sorting algorithms:
- Merge Sort
- Bubble Sort
- Insertion Sort
Example of unstable sorting algorithm:
- QuickSort
C++
// Stable Sort Example (Merge Sort)
#include <iostream>
void merge(int arr[], int left, int mid, int right) {
// ... (same as previous Merge Sort implementation)
}
void mergeSort(int arr[], int left, int right) {
// ... (same as previous Merge Sort implementation)
}
int main() {
int arr[] = {5, 2, 8, 2, 1, 5};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
std::cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}
// Unstable Sort Example (QuickSort)
#include <iostream>
int partition(int arr[], int low, int high) {
// ... (same as previous QuickSort implementation)
}
void quickSort(int arr[], int low, int high) {
// ... (same as previous QuickSort implementation)
}
int main() {
int arr[] = {5, 2, 8, 2, 1, 5};
int size = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, size - 1);
std::cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}9. What is an in-place sorting algorithm?
An in-place sorting algorithm is a sorting algorithm that does not require any additional memory space for sorting. It means that the sorting is done directly on the input array without using extra data structures.
Example of an in-place sorting algorithm:
- Bubble Sort
C++
#include <iostream>
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements in-place
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, size);
std::cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}10. Explain external sorting and provide an example.
External sorting is a technique used to sort large datasets that cannot fit entirely in memory. It involves using external storage, such as a hard disk, to store and manipulate data that exceeds the available RAM.
Example scenario: Sorting a large file containing a huge number of records that cannot fit into memory at once.
The external sorting process typically involves the following steps:
- Divide the large dataset into smaller chunks that can fit into memory.
- Sort each chunk in memory using an efficient in-memory sorting algorithm like Merge Sort.
- Merge the sorted chunks together using a merging algorithm, like Merge Sort, but adapted for external storage.
By dividing the dataset into smaller manageable chunks, external sorting allows for efficient sorting even with limited memory resources.
11. Benefits of using Radix Sort:
- Radix Sort is a non-comparative sorting algorithm, making it more efficient than comparison-based algorithms like QuickSort and MergeSort.
- It is particularly suitable for sorting integers or fixed-size strings.
- Radix Sort has a linear time complexity for integers when the number of digits is small compared to the number of elements.
- It has a stable nature, preserving the order of equal elements.
- Radix Sort can be used for large datasets or when the range of numbers to be sorted is known in advance.
12. What is a bucket sort, and when might it be used?
Bucket Sort is a sorting algorithm that divides the input into a fixed number of equally-sized “buckets.” Elements are distributed into these buckets based on their values, and each bucket is sorted individually, either using another sorting algorithm or recursively applying Bucket Sort.
Bucket Sort is useful when the input data is uniformly distributed over a range. It can achieve linear time complexity in best-case scenarios.
C++
#include <iostream>
#include <vector>
#include <algorithm>
void bucketSort(float arr[], int size) {
std::vector<float> buckets[size];
for (int i = 0; i < size; i++) {
int bucketIndex = size * arr[i];
buckets[bucketIndex].push_back(arr[i]);
}
for (int i = 0; i < size; i++) {
std::sort(buckets[i].begin(), buckets[i].end());
}
int index = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < buckets[i].size(); j++) {
arr[index++] = buckets[i][j];
}
}
}
int main() {
float arr[] = {0.8, 0.2, 0.5, 0.1, 0.9, 0.3};
int size = sizeof(arr) / sizeof(arr[0]);
bucketSort(arr, size);
std::cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}13. What is Counting Sort, and where is it used?
Counting Sort is an integer sorting algorithm that works by determining the number of occurrences of each distinct element in the input array and using this information to place the elements in sorted order.
Counting Sort is used when the range of input elements is small compared to the number of elements and when the data is non-negative integers.
C++
#include <iostream>
void countingSort(int arr[], int size) {
int max = arr[0];
for (int i = 1; i < size; i++) {
if (arr[i] > max)
max = arr[i];
}
int* count = new int[max + 1](); // Initialize the count array with 0
for (int i = 0; i < size; i++) {
count[arr[i]]++;
}
int index = 0;
for (int i = 0; i <= max; i++) {
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}
delete[] count;
}
int main() {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
int size = sizeof(arr) / sizeof(arr[0]);
countingSort(arr, size);
std::cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}14. Describe Shell Sort and its benefits.
Shell Sort, also known as diminishing increment sort, is an extension of Insertion Sort. It divides the array into smaller subarrays and sorts the elements at a specific interval. As the algorithm progresses, the interval is reduced, leading to a more efficient final sorting.
Benefits of Shell Sort:
- It has better performance than Insertion Sort for larger datasets.
- Shell Sort is an in-place sorting algorithm, meaning it doesn’t require additional memory for sorting.
- It is relatively easy to implement.
- It has a time complexity between O(n) and O(n^2), depending on the gap sequence chosen.
Shell Sort can be useful for small to moderately-sized datasets or as a preliminary sort before using a more efficient algorithm.
15. Difference between Comparison Sort and Non-comparison Sort.
Comparison Sort: It is a type of sorting algorithm that compares elements using comparison operators (e.g., >, <, >=, <=) to determine their relative order. Most well-known sorting algorithms, like QuickSort, MergeSort, and HeapSort, fall under this category.
Non-comparison Sort: It is a type of sorting algorithm that doesn’t rely on comparison operations to determine the relative order of elements. Instead, it uses special properties or knowledge about the data to perform sorting. Examples of non-comparison sorts include Counting Sort, Radix Sort, and Bucket Sort.
Comparison Sorts have a lower time complexity limit of O(n log n) due to the need to compare elements pairwise. In contrast, Non-comparison Sorts can achieve better time complexity in certain scenarios, like linear time complexity (O(n)), by leveraging specific characteristics of the input data.
16. Concept of time complexity in sorting algorithms.
Time complexity in sorting algorithms refers to the measure of the amount of time it takes for an algorithm to execute and sort a given set of elements. It is generally expressed in Big O notation.
The time complexity of a sorting algorithm indicates how the execution time increases with the size of the input (n). The lower the time complexity, the more efficient the algorithm is for larger datasets.
For example:
- O(n log n): Efficient sorting algorithms like Merge Sort, QuickSort, and HeapSort have this time complexity.
- O(n^2): Less efficient sorting algorithms like Bubble Sort, Selection Sort, and Insertion Sort have this time complexity.
- O(n) or linear time complexity: Specialized sorting algorithms like Counting Sort and Bucket Sort can achieve linear time complexity in specific scenarios.
17. What is the best, average, and worst-case scenario for QuickSort?
- Best Case: The best-case scenario for QuickSort occurs when the pivot chosen is the median element, and it divides the array into two roughly equal halves at each step. In this case, the time complexity is O(n log n).
C++
// Best Case (already sorted array)
int arr[] = {11, 12, 22, 25, 34, 64, 90};- Average Case: The average-case scenario for QuickSort occurs when the pivot divides the array into reasonably balanced halves. The time complexity is O(n log n) on average.
C++
// Average Case
int arr[] = {64, 34, 25, 12, 22, 11, 90};- Worst Case: The worst-case scenario for QuickSort occurs when the pivot is either the smallest or largest element, leading to unbalanced partitions. This results in a time complexity of O(n^2).
C++
// Worst Case (already sorted array in reverse order)
int arr[] = {90, 64, 34, 25, 22, 12, 11};18. How does the choice of pivot affect the efficiency of QuickSort?
The choice of pivot significantly affects the efficiency of QuickSort. In the best-case scenario, a well-chosen pivot divides the array into roughly equal halves, leading to a balanced partitioning and efficient sorting. On the other hand, a poorly chosen pivot can result in unbalanced partitions, leading to poor performance.
- Best Case Pivot: The median element is the ideal pivot choice as it evenly divides the array into two halves.
- Average Case Pivot: The pivot selected at random or through heuristics usually leads to reasonable partitioning, resulting in good average performance.
- Worst Case Pivot: The first or last element of the array (or a sorted array) can lead to unbalanced partitions, resulting in the worst-case performance of O(n^2).
19. What is an adaptive sorting algorithm?
An adaptive sorting algorithm is an algorithm that takes advantage of the existing order or pattern in the input data to improve its performance. If the input data is partially sorted or almost sorted, adaptive sorting algorithms can detect and efficiently sort the elements with fewer comparisons and swaps.
Example of an adaptive sorting algorithm: Insertion Sort
Insertion Sort performs very efficiently on almost sorted data, as it only needs to make a few comparisons and swaps to achieve the final sorted order.
20. How can sorting algorithms be parallelized?
Parallelizing sorting algorithms involves dividing the sorting task into smaller independent subtasks that can be executed simultaneously on multiple processors or cores.
One common parallel sorting algorithm is “Parallel Merge Sort”:
C++
#include <iostream>
#include <omp.h>
void merge(int arr[], int left, int mid, int right) {
// ... (same as previous Merge Sort implementation)
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
#pragma omp parallel sections
{
#pragma omp section
mergeSort(arr, left, mid);
#pragma omp section
mergeSort(arr, mid + 1, right);
}
merge(arr, left, mid, right);
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
std::cout << "Sorted array: ";
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
return 0;
}In this example, we’ve used OpenMP to parallelize the Merge Sort algorithm. The #pragma omp parallel sections directive divides the two recursive calls to mergeSort into separate parallel sections, allowing them to be executed in parallel. The merge step, which requires the results of the two parallel sorts, is executed sequentially. Parallelizing the sorting algorithm can significantly speed up the sorting process, especially for large datasets and on machines with multiple cores or processors.
Coding Questions
1. Write a program to implement Bubble Sort.
C++
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap the elements
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {5, 2, 8, 12, 1, 6};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
bubbleSort(arr, n);
cout << "\nSorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}2. Implement QuickSort in a given language.
C++
#include <iostream>
using namespace std;
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
// Swap elements
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap pivot with the element at i+1
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
quickSort(arr, 0, n - 1);
cout << "\nSorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}3. Write a program to perform Merge Sort.
C++
#include <iostream>
using namespace std;
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays
int L[n1], R[n2];
// Copy data to temporary arrays L[] and R[]
for (i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (j = 0; j
< n2; j++) {
R[j] = arr[mid + 1 + j];
}
// Merge the temporary arrays back into arr[left..right]
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[], if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[], if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Sort first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
mergeSort(arr, 0, n - 1);
cout << "\nSorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}4. Implement Heap Sort algorithm in a given language.
C++
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
// Swap elements
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements from heap one by one
for (int i = n - 1; i >= 0; i--) {
// Swap the root (maximum element) with the last element
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
heap
Sort(arr, n);
cout << "\nSorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}5. Write a program to perform Insertion Sort.
C++
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
insertionSort(arr, n);
cout << "\nSorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}6. Implement Selection Sort in a given language.
C++
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the minimum element with the first element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
selectionSort(arr, n);
cout << "\nSorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}7. Write a program to perform Radix Sort.
C++
#include <iostream>
using namespace std;
int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
void countSort(int arr[], int n, int exp) {
int output[n];
int count[10] = {0};
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
void radixSort(int arr[], int n) {
int max = getMax(arr, n);
for (int exp = 1; max / exp > 0; exp *= 10) {
countSort(arr, n, exp);
}
}
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
radixSort(arr, n);
cout << "\nSorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}8. Implement Bucket Sort in a given language.
C++
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void bucketSort(float arr[], int n) {
vector<float> buckets[n];
for (int i = 0; i < n; i++) {
int bucketIndex = n * arr[i];
buckets[bucketIndex].push_back(arr[i]);
}
for (int i = 0; i < n; i++) {
sort(buckets[i].begin(), buckets[i].end());
}
int index = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < buckets[i].size(); j++) {
arr[index++] = buckets[i][j];
}
}
}
int main() {
float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
bucketSort(arr, n);
cout << "\nSorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}9. Write a program to perform Counting Sort.
C++
#include <iostream>
using namespace std;
void countingSort(int arr[], int n, int range) {
int count[range + 1] = {0};
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
for (int i = 1; i <= range; i++) {
count[i] += count[i - 1];
}
int output[n];
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
int main() {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int range = 8;
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
countingSort(arr, n, range);
cout << "\nSorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}10. Implement Shell Sort in a given language.
C++
#include <iostream>
using namespace std;
void shellSort(int arr[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr
[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
int main() {
int arr[] = {12, 34, 54, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
shellSort(arr, n);
cout << "\nSorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}11. Write a program that uses a Stable Sort.
C++
#include <iostream>
#include <algorithm>
using namespace std;
struct Student {
int roll;
string name;
};
bool compare(const Student& s1, const Student& s2) {
return s1.roll < s2.roll;
}
int main() {
Student students[] = {{101, "John"}, {105, "Alice"}, {103, "Bob"}, {102, "Jane"}, {104, "Charlie"}};
int n = sizeof(students) / sizeof(students[0]);
cout << "Original order: ";
for (int i = 0; i < n; i++) {
cout << students[i].name << " ";
}
stable_sort(students, students + n, compare);
cout << "\nSorted order: ";
for (int i = 0; i < n; i++) {
cout << students[i].name << " ";
}
return 0;
}12. Implement an External Sorting algorithm in a given language.
C++
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int BUFFER_SIZE = 1000; // Define the size of the buffer
void mergeSortedChunks(const vector<string>& chunkFiles, const string& outputFile) {
vector<ifstream> chunkReaders;
// Open readers for each chunk file
for (const auto& chunkFile : chunkFiles) {
ifstream reader(chunkFile);
chunkReaders.push_back(move(reader));
}
// Open writer for the final output file
ofstream writer(outputFile);
// Create a min-heap to store the current smallest element from each chunk
vector<pair<string, int>> minHeap;
for (int i = 0; i < chunkReaders.size(); i++) {
string value;
if (getline(chunkReaders[i], value)) {
minHeap.emplace_back(value, i);
}
}
make_heap(minHeap.begin(), minHeap.end(), greater<>());
// Merge the sorted chunks
while (!minHeap.empty()) {
// Extract the smallest element from the min-heap
pop_heap(minHeap.begin(), minHeap.end(), greater<>());
string smallest = minHeap.back().first;
int chunkIndex = minHeap.back().second;
minHeap.pop_back();
// Write the smallest element to the output file
writer << smallest << "\n";
// Read the next element from the corresponding chunk
string nextValue;
if (getline(chunkReaders[chunkIndex], nextValue)) {
minHeap.emplace_back(nextValue, chunkIndex);
push_heap(minHeap.begin(), minHeap.end(), greater<>());
}
}
// Close the chunk readers and output writer
for (auto& reader : chunkReaders) {
reader.close();
}
writer.close();
}
void externalSort(const string& inputFile, const string& outputFile) {
ifstream reader(inputFile);
vector<string> buffer;
string value;
int chunkCount = 0;
// Read the input file and store elements in the buffer
while (getline(reader, value)) {
buffer.push_back(value);
// If the buffer is full, sort and write the contents to a new chunk file
if (buffer.size() >= BUFFER_SIZE) {
sort(buffer.begin(), buffer.end());
string chunkFile = "chunk_" + to_string(chunkCount) + ".txt";
ofstream writer(chunkFile);
for (const auto& item : buffer) {
writer << item << "\n";
}
writer.close();
buffer.clear();
chunkCount++;
}
}
// Sort and write the remaining elements in the buffer to a new chunk file
sort(buffer.begin(), buffer.end());
string chunkFile = "chunk_" + to_string(chunkCount) + ".txt";
ofstream writer(chunkFile);
for (const auto& item : buffer) {
writer << item << "\n";
}
writer.close();
buffer.clear();
chunkCount++;
// Merge the sorted chunk files
vector<string> chunkFiles;
for (int i = 0; i < chunkCount; i++) {
chunkFiles.push_back("chunk_" + to_string(i) + ".txt");
}
mergeSortedChunks(chunkFiles, outputFile);
// Delete the temporary chunk files
for (const auto& chunkFile : chunkFiles) {
remove(chunkFile.c_str());
}
reader.close();
}
int main() {
string inputFile = "
input.txt"; // Replace with your input file path
string outputFile = "output.txt"; // Replace with your output file path
externalSort(inputFile, outputFile);
cout << "External sorting completed." << endl;
return 0;
}13. Write a program to sort a binary array in linear time.
C++
#include <iostream>
using namespace std;
void sortBinaryArray(int arr[], int n) {
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == 0) {
count++;
}
}
for (int i = 0; i < count; i++) {
arr[i] = 0;
}
for (int i = count; i < n; i++) {
arr[i] = 1;
}
}
int main() {
int arr[] = {1, 0, 1, 0, 0, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
sortBinaryArray(arr, n);
cout << "\nSorted array: ";
for (int i
= 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}14. Implement a program to sort an array according to the order defined by another array.
C++
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
void sortArrayByOrder(int arr1[], int n1, int arr2[], int n2) {
unordered_map<int, int> countMap;
vector<int> result;
for (int i = 0; i < n1; i++) {
countMap[arr1[i]]++;
}
for (int i = 0; i < n2; i++) {
if (countMap.find(arr2[i]) != countMap.end()) {
int count = countMap[arr2[i]];
while (count > 0) {
result.push_back(arr2[i]);
count--;
}
countMap.erase(arr2[i]);
}
}
for (auto& pair : countMap) {
int count = pair.second;
while (count > 0) {
result.push_back(pair.first);
count--;
}
}
for (int i = 0; i < n1; i++) {
if (countMap.find(arr1[i]) != countMap.end()) {
int count = countMap[arr1[i]];
while (count > 0) {
result.push_back(arr1[i]);
count--;
}
countMap.erase(arr1[i]);
}
}
for (int i = 0; i < n1; i++) {
arr1[i] = result[i];
}
}
int main() {
int arr1[] = {2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int arr2[] = {2, 1, 8, 3};
int n2 = sizeof(arr2) / sizeof(arr2[0]);
cout << "Original array: ";
for (int i = 0; i < n1; i++) {
cout << arr1[i] << " ";
}
sortArrayByOrder(arr1, n1, arr2, n2);
cout << "\nSorted array: ";
for (int i = 0; i < n1; i++) {
cout << arr1[i] << " ";
}
return 0;
}15. Write a program to sort a nearly sorted array.
C++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void sortNearlySortedArray(int arr[], int n, int k) {
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int i = 0; i < n; i++) {
minHeap.push(arr[i]);
if (minHeap.size() > k) {
arr[i - k] = minHeap.top();
minHeap.pop();
}
}
int index = n - k;
while (!minHeap.empty()) {
arr[index++] = minHeap.top();
minHeap.pop();
}
}
int main() {
int arr[] = {6, 5, 3, 2, 8, 10, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
sortNearlySortedArray(arr, n, k);
cout << "\nSorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}16. Implement a program to sort a stack.
C++
#include <iostream>
#include <stack>
using namespace std;
void sortedInsert(stack<int>& s, int element) {
if (s.empty() || element > s.top()) {
s.push(element);
} else {
int temp = s.top();
s.pop();
sortedInsert(s, element);
s.push(temp);
}
}
void sortStack(stack<int>& s) {
if (!s.empty()) {
int temp = s.top();
s.pop();
sortStack(s);
sortedInsert(s, temp);
}
}
int main() {
stack<int> s;
s.push(5);
s.push(2);
s.push(8);
s.push(1);
s.push(4);
cout << "Original stack: ";
stack<int> temp = s;
while (!temp.empty()) {
cout << temp.top() << " ";
temp.pop();
}
sortStack(s);
cout << "\nSorted stack: ";
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
return 0;
}17. Write a program to sort elements by frequency.
C++
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(const pair<int, int>& p1, const pair<int, int>& p2) {
if (p1.second != p2.second) {
return p1.second > p2.second;
} else {
return p1.first < p2.first;
}
}
void sortByFrequency(int arr[], int n) {
unordered_map<int, int> frequencyMap;
vector<pair<int, int>> frequencyPairs;
for (int i = 0; i < n; i++) {
frequencyMap[arr[i]]++;
}
for (auto& pair : frequencyMap) {
frequencyPairs.push_back(pair);
}
sort(frequencyPairs.begin(), frequencyPairs.end(), compare);
int index = 0;
for (auto& pair : frequencyPairs) {
int element = pair.first;
int frequency = pair.second;
for (int i = 0; i < frequency; i++) {
arr[index++] = element;
}
}
}
int main() {
int arr[] = {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
sortByFrequency(arr, n);
cout << "\nSorted array by frequency: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}18. Implement a program to sort a linked list.
C++
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int value) {
data = value;
next = nullptr;
}
};
Node* merge(Node* head1, Node* head2) {
if (head1 == nullptr) {
return head2;
}
if (head2 == nullptr) {
return head1;
}
Node* result = nullptr;
if (head1->data <= head2->data) {
result = head1;
result->next = merge(head1->next, head2);
} else {
result = head2;
result->next = merge(head1, head2->next);
}
return result;
}
void split(Node* source, Node** front, Node** back) {
Node* slow = source;
Node* fast = source->next;
while (fast != nullptr) {
fast = fast->next;
if (fast != nullptr) {
slow = slow->next;
fast = fast->next;
}
}
*front = source;
*back = slow->next;
slow->next = nullptr;
}
void mergeSort(Node** head) {
Node* temp = *head;
Node* front = nullptr;
Node* back = nullptr;
if (temp == nullptr || temp->next == nullptr) {
return;
}
split(temp, &front, &back);
mergeSort(&front);
mergeSort(&back);
*head = merge(front, back);
}
void insert(Node** head, int value) {
Node* newNode = new Node(value);
if (*head == nullptr) {
*head = newNode;
} else {
Node* temp = *head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
}
void printList(Node* head) {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
int main() {
Node* head = nullptr;
insert(&head, 5);
insert(&head, 2);
insert(&head, 8);
insert(&head, 1);
insert(&head, 4);
cout << "Original list: ";
printList(head);
mergeSort(&head);
cout << "Sorted list: ";
printList(head);
return 0;
}19. Write a program to sort a k sorted array.
C++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void sortKSortedArray(int arr[], int n, int k) {
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int i = 0; i <= k; i++) {
minHeap.push(arr[i]);
}
int index = 0;
for (int i = k + 1; i < n; i++) {
arr[index++] = minHeap.top();
minHeap.pop();
minHeap.push(arr[i]);
}
while (!minHeap.empty()) {
arr[index++] = minHeap.top();
minHeap.pop();
}
}
int main() {
int arr[] = {6, 5, 3, 2, 8, 10, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i]
<< " ";
}
sortKSortedArray(arr, n, k);
cout << "\nSorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}20. Implement a program to sort a large set of floating point numbers which are in the range from 0.0 to 1.0 and are uniformly distributed across the range.
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void sortFloatingPointNumbers(vector<float>& numbers) {
sort(numbers.begin(), numbers.end());
}
int main() {
vector<float> numbers = {0.87, 0.12, 0.54, 0.31, 0.99, 0.45, 0.73, 0.28, 0.62};
cout << "Original numbers: ";
for (const auto& num : numbers) {
cout << num << " ";
}
sortFloatingPointNumbers(numbers);
cout << "\nSorted numbers: ";
for (const auto& num : numbers) {
cout << num << " ";
}
return 0;
}21. Write a program to sort numbers of an array using an algorithm whose run-time complexity is O(n).
C++
#include <iostream>
#include <vector>
using namespace std;
void sortNumbersLinearTime(vector<int>& arr) {
int n = arr.size();
int minNum = arr[0];
int maxNum = arr[0];
for (int i = 1; i < n; i++) {
minNum = min(minNum, arr[i]);
maxNum = max(maxNum, arr[i]);
}
int range = maxNum - minNum + 1;
vector<int> count(range, 0);
for (int i = 0; i < n; i++) {
count[arr[i] - minNum]++;
}
int index = 0;
for (int i = 0; i < range; i++) {
while (count[i] > 0) {
arr[index++] = i + minNum;
count[i]--;
}
}
}
int main() {
vector<int> arr = {7, 2, 4, 1, 8, 3, 5};
cout << "Original array: ";
for (const auto& num : arr) {
cout << num << " ";
}
sortNumbersLinearTime(arr);
cout << "\nSorted array: ";
for (const auto& num : arr) {
cout << num << " ";
}
return 0;
}22. Implement a program to sort a wave-like array.
C++
#include <iostream>
#include <algorithm>
using namespace std;
void sortWaveArray(int arr[], int n) {
sort(arr, arr + n);
for (int i = 0; i < n - 1; i += 2) {
swap(arr[i], arr[i + 1]);
}
}
int main() {
int arr[] = {4, 7, 3, 9, 1, 6, 2, 8, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
sortWaveArray(arr, n);
cout << "\nWave-like sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}23. Write a program to check whether an array is sorted and rotated.
C++
#include <iostream>
using namespace std;
bool isSortedAndRotated(int arr[], int n) {
int minIndex = 0;
for (int i = 1; i < n; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
}
}
if (minIndex == 0) {
return false;
}
for (int i = 1; i < n; i++) {
int currentIndex = (minIndex + i) % n;
int previousIndex = (minIndex + i - 1) % n;
if (arr[currentIndex] < arr[previousIndex]) {
return false;
}
}
return true;
}
int main() {
int arr1[] = {5, 6, 7, 1, 2, 3, 4};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int arr2[] = {1, 2, 3, 4, 5, 6, 7};
int n2 = sizeof(arr2) / sizeof(arr2[0]);
cout << "Array 1 is " << (isSortedAndRotated(arr1, n1) ? "sorted and rotated." : "not sorted and rotated.") << endl;
cout << "Array 2 is " << (isSortedAndRotated(arr2, n2) ? "sorted and rotated." : "not sorted and rotated.") << endl;
return 0;
}24. Implement a program to sort a matrix diagonally.
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void sortMatrixDiagonally(vector<vector<int>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
for (int k = 0; k < rows; k++) {
for (int i = 0, j = k; i < rows && j < cols; i++, j++) {
for (int p = i + 1, q = j + 1; p < rows && q < cols; p++, q++) {
if (matrix[i][j] > matrix[p][q]) {
swap(matrix[i][j], matrix[p][q]);
}
}
}
}
for (int k = 1; k < cols; k++) {
for (int i = k, j = 0; i < rows && j < cols; i++, j++) {
for (int p = i + 1, q = j + 1; p < rows && q < cols; p++, q++) {
if (matrix[i][j] > matrix[p][q]) {
swap(matrix[i][j], matrix[p][q]);
}
}
}
}
}
void printMatrix(const vector<vector<int>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
}
int main() {
vector<vector<int>> matrix = {{5, 8, 1, 2},
{4, 7, 3, 9},
{6, 12, 11, 10}};
cout << "Original matrix:\n";
printMatrix(matrix);
sortMatrixDiagonally(matrix);
cout << "\nSorted matrix diagonally:\n";
printMatrix(matrix);
return 0;
}25. Write a program to sort an array of strings based on string lengths.
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(const string& s1, const string& s2) {
return s1.length() < s2.length();
}
void sortArrayByStringLength(vector<string>& arr) {
sort(arr.begin(), arr.end(), compare);
}
int main() {
vector<string> arr = {"apple", "banana", "cat", "dog", "elephant"};
cout << "Original array: ";
for (const auto& str : arr) {
cout << str << " ";
}
sortArrayByStringLength(arr);
cout << "\nSorted array by string length: ";
for (const auto& str : arr) {
cout << str << " ";
}
return 0;
}26. Implement a program to sort a list of dates in ascending order.
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Date {
int day;
int month;
int year;
Date(int d, int m, int y) {
day = d;
month = m;
year = y;
}
};
bool compare(const Date& d1, const Date& d2) {
if (d1.year != d2.year) {
return d1.year < d2.year;
} else if (d1.month != d2.month) {
return d1.month < d2.month;
} else {
return d1.day < d2.day;
}
}
void sortDates(vector<Date>& dates) {
sort(dates.begin(), dates.end(), compare);
}
int main() {
vector<Date> dates = {Date(10, 12, 2022), Date(5, 6, 2021), Date(8, 3, 2023), Date(15, 9, 2022)};
cout << "Original dates: ";
for (const auto& date : dates) {
cout << date.day << "/" << date.month << "/" << date.year << " ";
}
sortDates(dates);
cout << "\nSorted dates: ";
for (const auto& date : dates) {
cout << date.day << "/" << date.month << "/" << date.year << " ";
}
return 0;
}27. Write a program to sort an array containing 0s, 1s, and 2s.
C++
#include <iostream>
using namespace std;
void sortZeroOneTwo(int arr[], int n) {
int low = 0;
int mid = 0;
int high = n - 1;
while (mid <= high) {
switch (arr[mid]) {
case 0:
swap(arr[low], arr[mid]);
low++;
mid++;
break;
case 1:
mid++;
break;
case 2:
swap(arr[mid], arr[high]);
high--;
break;
}
}
}
int main() {
int arr[] = {0, 1, 2, 1, 0, 1, 2, 2, 0};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
sortZeroOneTwo(arr, n);
cout << "\nSorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}28. Implement a program to perform Topological Sort on a given graph.
C++
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;
class Graph {
private:
unordered_map<int, vector<int>> adjList;
void topologicalSortUtil(int vertex, vector<bool>& visited, stack<int>& result) {
visited[vertex] = true;
for (const auto& neighbor : adjList[vertex]) {
if (!visited[neighbor]) {
topologicalSortUtil(neighbor, visited, result);
}
}
result.push(vertex);
}
public:
void addEdge(int source, int destination) {
adjList[source].push_back(destination);
}
vector<int> topologicalSort() {
vector<bool> visited(adjList.size(), false);
stack<int> result;
for (const auto& pair : adjList) {
int vertex = pair.first;
if (!visited[vertex]) {
topologicalSortUtil(vertex, visited, result);
}
}
vector<int> sorted;
while (!result.empty()) {
sorted.push_back(result.top());
result.pop();
}
return sorted;
}
};
int main() {
Graph g;
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(3, 4);
g.addEdge(3, 5);
g.addEdge(4, 6);
g.addEdge(5, 6);
vector<int> sorted = g.topologicalSort();
cout << "Topological order: ";
for (const auto& vertex : sorted) {
cout << vertex << " ";
}
return 0;
}29. Write a program to sort an array in ascending order but respect the relative order of odd and even numbers.
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool isEven(int num) {
return num % 2 == 0;
}
bool compare(int a, int b) {
if (isEven(a) && isEven(b)) {
return a < b;
} else if (!isEven(a) && !isEven(b)) {
return a < b;
} else {
return isEven(a);
}
}
void sortArrayWithRelativeOrder(vector<int>& arr) {
sort(arr.begin(), arr.end(), compare);
}
int main() {
vector<int> arr = {2, 4, 5, 7, 8, 9, 10};
cout << "Original array: ";
for (const auto& num : arr) {
cout << num << " ";
}
sortArrayWithRelativeOrder(arr);
cout << "\nSorted array with relative order: ";
for (const auto& num : arr) {
cout << num << " ";
}
return 0;
}30. Implement a program to sort a linked list that is sorted alternating ascending and descending orders.
C++
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int value) {
data = value;
next = nullptr;
}
};
Node* reverse(Node* head) {
Node* prev = nullptr;
Node* current = head;
Node* next = nullptr;
while (current != nullptr) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
Node* merge(Node* head1, Node* head2) {
if (head1 == nullptr) {
return head2;
}
if (head2 == nullptr) {
return head1;
}
Node* result = nullptr;
if (head1->data <= head2->data) {
result = head1;
result->next = merge(head1->next, head2);
} else {
result = head2;
result->next = merge(head1, head2->next);
}
return result;
}
void sortLinkedList(Node** head) {
Node* slow = *head;
Node* fast = (*head)->next;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
Node* head1 = *head;
Node* head2 = slow->next;
slow->next = nullptr;
head2 = reverse(head2);
*head = merge(head1, head2);
}
void insert(Node** head, int value) {
Node* newNode = new Node(value);
if (*head == nullptr) {
*head = newNode;
} else {
Node* temp = *head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
}
void printList(Node* head) {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
int main() {
Node* head = nullptr;
insert(&head, 1);
insert(&head, 6);
insert(&head, 2);
insert(&head, 9);
insert(&head, 4);
insert(&head, 7);
insert(&head, 3);
cout << "Original list: ";
printList(head);
sortLinkedList(&head);
cout << "Sorted list: ";
printList(head);
return 0;
}MCQ Questions
1. Which sorting algorithm has the best average-case time complexity?
- (a) QuickSort
- (b) MergeSort
- (c) Insertion Sort
- (d) Bubble Sort
Answer: (b) MergeSort
2. Which sorting algorithm has the worst-case time complexity of O(n^2)?
- (a) MergeSort
- (b) QuickSort
- (c) HeapSort
- (d) Selection Sort
Answer: (d) Selection Sort
3. Which sorting algorithm is based on the divide-and-conquer technique?
- (a) QuickSort
- (b) Bubble Sort
- (c) Insertion Sort
- (d) Selection Sort
Answer: (a) QuickSort
4. Which sorting algorithm is not an in-place sorting algorithm?
- (a) QuickSort
- (b) HeapSort
- (c) Bubble Sort
- (d) Insertion Sort
Answer: (b) HeapSort
5. Which sorting algorithm is best suited for large datasets or external sorting?
- (a) QuickSort
- (b) MergeSort
- (c) Insertion Sort
- (d) Bubble Sort
Answer: (b) MergeSort
6. Which sorting algorithm has a worst-case time complexity of O(n log n)?
- (a) QuickSort
- (b) Bubble Sort
- (c) Insertion Sort
- (d) Selection Sort
Answer: (a) QuickSort
7. Which sorting algorithm is most efficient for small datasets or partially sorted arrays?
- (a) QuickSort
- (b) MergeSort
- (c) Insertion Sort
- (d) Bubble Sort
Answer: (c) Insertion Sort
8. Which sorting algorithm is stable, meaning it maintains the relative order of elements with equal keys?
- (a) QuickSort
- (b) Bubble Sort
- (c) Insertion Sort
- (d) MergeSort
Answer: (d) MergeSort
9. Which sorting algorithm works by repeatedly swapping adjacent elements if they are in the wrong order?
- (a) QuickSort
- (b) Bubble Sort
- (c) Insertion Sort
- (d) Selection Sort
Answer: (b) Bubble Sort
10. Which sorting algorithm is commonly used in Java’s Arrays.sort() method?
- (a) QuickSort
- (b) MergeSort
- (c) HeapSort
- (d) Insertion Sort
Answer: (a) QuickSort
11. Which sorting algorithm is an in-place comparison-based sorting algorithm?
- (a) QuickSort
- (b) MergeSort
- (c) Bubble Sort
- (d) Selection Sort
Answer: (a) QuickSort
12. Which sorting algorithm has a time complexity of O(n^2) on average, but O(n) in the best case?
- (a) QuickSort
- (b) Bubble Sort
- (c) Insertion Sort
- (d) Selection Sort
Answer: (c) Insertion Sort
13. Which sorting algorithm is based on the idea of repeatedly finding the minimum element from the unsorted part of the array and placing it at the beginning?
- (a) QuickSort
- (b) Bubble Sort
- (c) Insertion Sort
- (d) Selection Sort
Answer: (d) Selection Sort
14. Which sorting algorithm has a worst-case time complexity of O(n log n) and uses a binary heap data structure?
- (a) QuickSort
- (b) Bubble Sort
- (c) HeapSort
- (d) Insertion Sort
Answer: (c) HeapSort
15. Which sorting algorithm is based on the idea of partitioning the array into two subarrays, then recursively sorting each subarray?
- (a) QuickSort
- (b) MergeSort
- (c) Bubble Sort
- (d) Insertion Sort
Answer: (a) QuickSort
16. Which sorting algorithm has the best worst-case time complexity?
- (a) QuickSort
- (b) Bubble Sort
- (c) MergeSort
- (d) Insertion Sort
Answer: (c) MergeSort
17. Which sorting algorithm works by repeatedly selecting the minimum element from the unsorted part of the array and swapping it with the element at the beginning of the unsorted part?
- (a) QuickSort
- (b) Bubble Sort
- (c) Insertion Sort
- (d) Selection Sort
Answer: (d) Selection Sort
18. Which sorting algorithm is based on the idea of merging two sorted subarrays into a single sorted array?
- (a) QuickSort
- (b) Bubble Sort
- (c) MergeSort
- (d) Insertion Sort
Answer: (c) MergeSort
19. Which sorting algorithm has a worst-case time complexity of O(n^2) and works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order?
- (a) QuickSort
- (b) Bubble Sort
- (c) Insertion Sort
- (d) Selection Sort
Answer: (b) Bubble Sort
20. Which sorting algorithm is known for its simplicity and ease of implementation, but has a worst-case time complexity of O(n^2)?
- (a) QuickSort
- (b) Bubble Sort
- (c) Insertion Sort
- (d) Selection Sort
Answer: (b) Bubble Sort
21. Which sorting algorithm is efficient for sorting small arrays or nearly sorted arrays?
- (a) QuickSort
- (b) MergeSort
- (c) Insertion Sort
- (d) HeapSort
Answer: (c) Insertion Sort
22. Which sorting algorithm has a time complexity of O(n log n) on average and worst-case?
- (a) QuickSort
- (b) Bubble Sort
- (c) Insertion Sort
- (d) Selection Sort
Answer: (a) QuickSort
23. Which sorting algorithm is commonly used for sorting linked lists?
- (a) QuickSort
- (b) MergeSort
- (c) Bubble Sort
- (d) Selection Sort
Answer: (b) MergeSort
24. Which sorting algorithm has the best space complexity?
- (a) QuickSort
- (b) MergeSort
- (c) Bubble Sort
- (d) Selection Sort
Answer: (d) Selection Sort
25. Which sorting algorithm is a stable sorting algorithm that uses a divide-and-conquer approach?
- (a) QuickSort
- (b) Bubble Sort
- (c) Insertion Sort
- (d) MergeSort
Answer: (d) MergeSort
26. Which sorting algorithm works by repeatedly partitioning the array into smaller subarrays and sorting them?
- (a) QuickSort
- (b) Bubble Sort
- (c) Insertion Sort
- (d) Selection Sort
Answer: (a) QuickSort
27. Which sorting algorithm has the best time complexity for already sorted or partially sorted arrays?
- (a) QuickSort
- (b) Bubble Sort
- (c) Insertion Sort
- (d) MergeSort
Answer: (c) Insertion Sort
28. Which sorting algorithm is not a comparison-based sorting algorithm?
- (a) QuickSort
- (b) Radix Sort
- (c) Bubble Sort
- (d) MergeSort
Answer: (b) Radix Sort
29. Which sorting algorithm works by repeatedly selecting the maximum element from the unsorted part of the array and placing it at the end?
- (a) QuickSort
- (b) Bubble Sort
- (c) Insertion Sort
- (d) Selection Sort
Answer: (b) Bubble Sort
30. Which sorting algorithm is best suited for sorting small arrays with a limited range of integer values?
- (a) QuickSort
- (b) Bucket Sort
- (c) Insertion Sort
- (d) Selection Sort
Answer: (b) Bucket Sort