CODEBHAVYA • DATA STRUCTURES

🔄 Sorting

Learn important sorting techniques in C, understand how data moves during execution, and practice sorting step by step.

SORTING

📖 Introduction to Sorting

Sorting is the process of arranging data in a particular order, usually ascending or descending. A good sorting algorithm makes later operations such as searching, merging, and data analysis easier.

Different sorting algorithms use different strategies. Some repeatedly compare neighboring values, some select the smallest value, some insert elements into their proper positions, and advanced algorithms divide the data into smaller parts.

Important: While studying a sorting algorithm, observe not only the final sorted array but also the comparisons, swaps, passes, and extra memory used.
01 • SORTING ALGORITHM

🫧 Bubble Sort

Repeatedly compare adjacent elements and swap them when they are in the wrong order.

💡 Key Idea

Bubble Sort compares neighboring elements. If the left value is greater than the right value, the two values are swapped. After one complete pass, the largest unsorted value reaches its correct position at the end of the array.

🧠 Example

For [5, 1, 4, 2, 8]:
Compare 5 and 1 → swap → [1, 5, 4, 2, 8]
Compare 5 and 4 → swap → [1, 4, 5, 2, 8]
Compare 5 and 2 → swap → [1, 4, 2, 5, 8]
At the end of the first pass, the largest element is fixed at the end.

🔹 Step-by-Step Algorithm

  1. Start from the first element.
  2. Compare the current element with the next element.
  3. If the current element is greater, swap the two values.
  4. Continue until the end of the unsorted portion.
  5. After each pass, one largest value reaches its final position.
  6. Repeat until the entire array is sorted.
Interactive Algorithm Visualization
CodeBhavya logo CodeBhavya

🎬 Premium Bubble Sort Visualizer

See every adjacent comparison, swap, pass completion, and sorted suffix grow step by step.

850 ms

📦 Live Array

Ready
Press Next to begin.
Step 0 0%
🎉 Visualization completed successfully!

📊 Live Statistics

No operation yet.

🧠 Current Pass

Waiting to start.

🧾 Recent Actions

💻 C Program
#include <stdio.h>

int main() {
    int n;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

5
5 1 4 2 8

Sample Output

1 2 4 5 8

⚡ Complexity

Best: O(n²) The basic version still performs all comparisons even if the array is already sorted.
Average: O(n²) Nested loops compare adjacent pairs over multiple passes.
Worst: O(n²) A reverse-sorted array requires many comparisons and swaps.

Space: O(1) because Bubble Sort works in place.

Interview note: Bubble Sort is stable. An optimized version can stop early when a complete pass performs no swaps.
02 • SORTING ALGORITHM

🎯 Selection Sort

Repeatedly find the smallest element in the unsorted portion and place it at the beginning.

💡 Key Idea

Selection Sort divides the array into a sorted part and an unsorted part. For each position, it scans the remaining unsorted elements, finds the smallest value, and swaps that value into the current position.

🧠 Example

For [64, 25, 12, 22, 11]:
Pass 1 → minimum is 11 → swap with 64 → [11, 25, 12, 22, 64]
Pass 2 → minimum is 12 → swap with 25 → [11, 12, 25, 22, 64]
Pass 3 → minimum is 22 → swap with 25 → [11, 12, 22, 25, 64]
The remaining elements are already in correct order.

🔹 Step-by-Step Algorithm

  1. Start at index 0 and assume it contains the minimum value.
  2. Scan all elements to its right.
  3. If a smaller value is found, update the minimum index.
  4. After the scan finishes, swap the minimum value with the current position.
  5. The current position is now fixed in sorted order.
  6. Move to the next position and repeat.
Interactive Algorithm Visualization
CodeBhavya logo CodeBhavya

🎬 Premium Selection Sort Visualizer

Watch the current minimum move as each candidate is checked, then see one final swap complete each pass.

850 ms

📦 Live Array

Ready
Press Next to begin.
Step 0 0%
🎉 Visualization completed successfully!

📊 Live Statistics

No operation yet.

🧠 Minimum / Candidate

Waiting to start.

🧾 Recent Actions

💻 C Program
#include <stdio.h>

int main() {
    int n;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;

        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }

        if (minIndex != i) {
            int temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

5
64 25 12 22 11

Sample Output

11 12 22 25 64

⚡ Complexity

Best: O(n²) Selection Sort still scans the unsorted portion even when the array is already sorted.
Average: O(n²) Finding the minimum repeatedly requires nested scanning.
Worst: O(n²) The same number of comparisons is made for reverse or random order.

Space: O(1) because Selection Sort works in place.

Interview note: Selection Sort usually performs fewer swaps than Bubble Sort, but the standard implementation is not stable.
03 • SORTING ALGORITHM

🃏 Insertion Sort

Build the sorted portion one element at a time by inserting each new value into its correct position.

💡 Key Idea

Insertion Sort treats the left part of the array as already sorted. It takes the next element as the key, shifts larger sorted elements one position to the right, and inserts the key into the empty position that remains.

🧠 Example

For [5, 2, 4, 6, 1, 3]:
Insert 2 → [2, 5, 4, 6, 1, 3]
Insert 4 → [2, 4, 5, 6, 1, 3]
Insert 6 → [2, 4, 5, 6, 1, 3]
Insert 1 → [1, 2, 4, 5, 6, 3]
Insert 3 → [1, 2, 3, 4, 5, 6]

🔹 Step-by-Step Algorithm

  1. Assume the first element is already sorted.
  2. Take the next element as key.
  3. Compare the key with elements to its left.
  4. Shift every larger element one position to the right.
  5. Insert the key into the correct position.
  6. Repeat for all remaining elements.
Interactive Algorithm Visualization
CodeBhavya logo CodeBhavya

🎬 Premium Insertion Sort Visualizer

Follow the key, each comparison, each right shift, and the exact insertion point as the sorted prefix grows.

850 ms

📦 Live Array

Ready
Press Next to begin.
Step 0 0%
🎉 Visualization completed successfully!

📊 Live Statistics

No operation yet.

🧠 Key / Sorted Prefix

Waiting to start.

🧾 Recent Actions

💻 C Program
#include <stdio.h>

int main() {
    int n;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;

        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }

        a[j + 1] = key;
    }

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

6
5 2 4 6 1 3

Sample Output

1 2 3 4 5 6

⚡ Complexity

Best: O(n) When the array is already sorted, every key needs only one comparison.
Average: O(n²) Elements may need to move through part of the sorted prefix.
Worst: O(n²) A reverse-sorted array causes the maximum number of shifts.

Space: O(1) because Insertion Sort works in place.

Interview note: Insertion Sort is stable and performs very well on small or nearly sorted data. It is also commonly used as a helper inside more advanced hybrid sorting algorithms.
04 • SORTING ALGORITHM

🧩 Merge Sort

Divide the array into smaller parts, sort them recursively, and merge the sorted parts back together.

💡 Key Idea

Merge Sort follows the divide-and-conquer strategy. It repeatedly divides an array into two halves until each part contains one element. Then it merges those small sorted parts back together in the correct order.

🧠 Example

For [38, 27, 43, 3, 9, 82]:
Divide → [38, 27, 43] and [3, 9, 82]
Divide again until single-element parts are reached.
Merge sorted parts → [27, 38], then [27, 38, 43]
Merge the right side → [3, 9, 82]
Final merge → [3, 9, 27, 38, 43, 82]

🔹 Step-by-Step Algorithm

  1. Find the middle of the current array range.
  2. Recursively sort the left half.
  3. Recursively sort the right half.
  4. Compare values from both sorted halves.
  5. Copy the smaller value into a temporary array.
  6. Copy any remaining values from either half.
  7. Copy the merged temporary values back into the original array.
Interactive Algorithm Visualization
CodeBhavya logo CodeBhavya

🎬 Premium Merge Sort Visualizer

See divide-and-conquer happen visually: active subarrays split, values are compared into temporary storage, and merged ranges become sorted.

850 ms

📦 Live Array

Ready
Press Next to begin.
Step 0 0%
🎉 Visualization completed successfully!

📊 Live Statistics

No operation yet.

🧠 Active Merge

Waiting to start.

🧾 Recent Actions

💻 C Program
#include <stdio.h>

void merge(int a[], int low, int mid, int high) {
    int i = low;
    int j = mid + 1;
    int k = 0;
    int temp[high - low + 1];

    while (i <= mid && j <= high) {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }

    while (i <= mid)
        temp[k++] = a[i++];

    while (j <= high)
        temp[k++] = a[j++];

    for (i = 0; i < k; i++)
        a[low + i] = temp[i];
}

void mergeSort(int a[], int low, int high) {
    if (low >= high)
        return;

    int mid = low + (high - low) / 2;

    mergeSort(a, low, mid);
    mergeSort(a, mid + 1, high);
    merge(a, low, mid, high);
}

int main() {
    int n;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    mergeSort(a, 0, n - 1);

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

6
38 27 43 3 9 82

Sample Output

3 9 27 38 43 82

⚡ Complexity

Best: O(n log n) The array is always divided and merged through the same number of levels.
Average: O(n log n) Every level processes all n elements during merging.
Worst: O(n log n) Its running time remains predictable even for reverse-sorted data.

Space: O(n) because temporary storage is required while merging.

Interview note: Merge Sort is stable and guarantees O(n log n) time. It is especially useful for linked lists, external sorting, and situations where predictable performance is important.
05 • SORTING ALGORITHM

⚡ Quick Sort

Choose a pivot, partition the array around it, and recursively sort the left and right parts.

💡 Key Idea

Quick Sort is a divide-and-conquer algorithm. A pivot is selected, the array is rearranged so that smaller values come before the pivot and larger values come after it, and then the two sides are sorted recursively.

🧠 Example

For [10, 7, 8, 9, 1, 5]:
Pivot = 5 → partition → [1, 5, 8, 9, 10, 7]
The pivot 5 is now fixed at index 1.
Recursively sort the right part [8, 9, 10, 7].
After further partitioning, the final array becomes [1, 5, 7, 8, 9, 10].

🔹 Step-by-Step Algorithm

  1. Select a pivot. In this program, the last element is used as the pivot.
  2. Keep an index i for the end of the smaller-or-equal region.
  3. Scan the partition using j.
  4. If a[j] <= pivot, move that value into the smaller region.
  5. After scanning, place the pivot between the two regions.
  6. Recursively Quick Sort the left and right subarrays.
Interactive Algorithm Visualization
CodeBhavya logo CodeBhavya

🎬 Premium Quick Sort Visualizer

Track the pivot, j scan, i boundary, partition swaps, pivot placement, and recursive subarray processing.

850 ms

📦 Live Array

Ready
Press Next to begin.
Step 0 0%
🎉 Visualization completed successfully!

📊 Live Statistics

No operation yet.

🧠 Partition State

Waiting to start.

🧾 Recent Actions

💻 C Program
#include <stdio.h>

int partition(int a[], int low, int high) {
    int pivot = a[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (a[j] <= pivot) {
            i++;

            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

    int temp = a[i + 1];
    a[i + 1] = a[high];
    a[high] = temp;

    return i + 1;
}

void quickSort(int a[], int low, int high) {
    if (low < high) {
        int p = partition(a, low, high);

        quickSort(a, low, p - 1);
        quickSort(a, p + 1, high);
    }
}

int main() {
    int n;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    quickSort(a, 0, n - 1);

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

6
10 7 8 9 1 5

Sample Output

1 5 7 8 9 10

⚡ Complexity

Best: O(n log n) The pivot divides the array into balanced parts.
Average: O(n log n) Good partitions keep the recursion depth near log n.
Worst: O(n²) Very unbalanced partitions can occur repeatedly, such as with a poor pivot choice.

Space: O(log n) on average for the recursion stack, but it can grow to O(n) in the worst case.

Interview note: Quick Sort is usually very fast in practice and sorts in place, but the standard implementation is not stable and its worst case is O(n²).
06 • SORTING ALGORITHM

🌳 Heap Sort

Build a max heap, repeatedly move the largest element to the end, and restore the heap.

💡 Key Idea

Heap Sort first rearranges the array into a max heap, where the largest value is at the root. It then swaps that root with the last unsorted element, reduces the heap size, and calls heapify() to restore the max-heap property.

🧠 Example

For [12, 11, 13, 5, 6, 7]:
Build max heap → [13, 11, 12, 5, 6, 7]
Move 13 to the end and heapify the remaining part.
Then move the next largest values one by one to the sorted suffix.
Final array → [5, 6, 7, 11, 12, 13]

🔹 Step-by-Step Algorithm

  1. Start from the last non-leaf node and build a max heap.
  2. In heapify(), compare a node with its left and right children.
  3. If a child is larger, swap the node with the largest child.
  4. Continue heapifying from the changed child position.
  5. Swap the root (largest value) with the last unsorted element.
  6. Reduce the heap size and heapify the root again.
  7. Repeat until the array is fully sorted.
Interactive Algorithm Visualization
CodeBhavya logo CodeBhavya

🎬 Premium Heap Sort Visualizer

Watch max-heap construction, parent-child comparisons, heapify swaps, extraction of the root, and the sorted suffix grow.

850 ms

📦 Live Array

Ready
Press Next to begin.
Step 0 0%
🎉 Visualization completed successfully!

📊 Live Statistics

No operation yet.

🧠 Heap State

Waiting to start.

🧾 Recent Actions

💻 C Program
#include <stdio.h>

void heapify(int a[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && a[left] > a[largest])
        largest = left;

    if (right < n && a[right] > a[largest])
        largest = right;

    if (largest != i) {
        int temp = a[i];
        a[i] = a[largest];
        a[largest] = temp;

        heapify(a, n, largest);
    }
}

void heapSort(int a[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(a, n, i);

    for (int i = n - 1; i > 0; i--) {
        int temp = a[0];
        a[0] = a[i];
        a[i] = temp;

        heapify(a, i, 0);
    }
}

int main() {
    int n;

    scanf("%d", &n);

    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    heapSort(a, n);

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

6
12 11 13 5 6 7

Sample Output

5 6 7 11 12 13

⚡ Complexity

Best: O(n log n) Heap construction and repeated extraction still dominate the running time.
Average: O(n log n) Each extraction may require heapifying through the heap height.
Worst: O(n log n) Heap Sort guarantees O(n log n) even for unfavorable input order.

Space: O(log n) for this recursive heapify() implementation because of the call stack. An iterative heapify version can use O(1) auxiliary space.

Interview note: Heap Sort guarantees O(n log n) worst-case time and sorts in place, but the standard algorithm is not stable and is often less cache-friendly than Quick Sort.
QUICK REVISION

📊 Sorting Algorithm Comparison

This table will grow as we add each sorting algorithm.

AlgorithmBestAverageWorstSpaceStable?
Bubble SortO(n²)*O(n²)O(n²)O(1)Yes
Selection SortO(n²)O(n²)O(n²)O(1)No
Insertion SortO(n)O(n²)O(n²)O(1)Yes
Merge SortO(n log n)O(n log n)O(n log n)O(n)Yes
Quick SortO(n log n)O(n log n)O(n²)O(log n)*No
Heap SortO(n log n)O(n log n)O(n log n)O(log n)*No

* For the basic program shown above. Optimized Bubble Sort can achieve O(n) best-case time.

* Quick Sort uses O(log n) recursion space on average and O(n) in the worst case.

* This Heap Sort program uses recursive heapify and therefore O(log n) call-stack space; iterative heapify can reduce auxiliary space to O(1).

INTERVIEW PREPARATION

📝 Sorting Interview Points

  • Bubble Sort compares adjacent elements.
  • After each pass, the largest remaining element reaches its final position.
  • Average and worst-case time complexity are O(n²).
  • It uses O(1) auxiliary space.
  • Bubble Sort is stable.
  • An optimized version can stop early if a pass performs no swaps.

🎯 Selection Sort

  • Selection Sort repeatedly finds the minimum element from the unsorted portion.
  • After each pass, one smallest element is placed in its final position at the beginning.
  • Best, average, and worst-case time complexity are all O(n²).
  • It uses O(1) auxiliary space.
  • The standard Selection Sort is not stable.
  • It usually performs fewer swaps than Bubble Sort.

🃏 Insertion Sort

  • Insertion Sort builds a sorted prefix one element at a time.
  • The current key is inserted into the correct position by shifting larger elements right.
  • Best-case time complexity is O(n) for already sorted data.
  • Average and worst-case time complexity are O(n²).
  • It uses O(1) auxiliary space.
  • Insertion Sort is stable and performs well on small or nearly sorted arrays.

🧩 Merge Sort

  • Merge Sort uses the divide-and-conquer technique.
  • It recursively divides the array and then merges sorted subarrays.
  • Best, average, and worst-case time complexity are all O(n log n).
  • Array-based Merge Sort requires O(n) auxiliary space.
  • Merge Sort is stable.
  • Its predictable O(n log n) performance makes it useful for large datasets and external sorting.

⚡ Quick Sort

  • Quick Sort uses divide-and-conquer with a pivot-based partition.
  • After partitioning, the pivot is in its final sorted position.
  • Best and average-case time complexity are O(n log n).
  • Worst-case time complexity is O(n²).
  • It usually needs only recursion-stack space and works in place.
  • The standard Quick Sort is not stable.

🌳 Heap Sort

  • Heap Sort first builds a max heap.
  • The root of a max heap contains the largest remaining value.
  • Each extraction moves that largest value to the sorted suffix.
  • Best, average, and worst-case time complexity are all O(n log n).
  • The standard Heap Sort is not stable.
  • An iterative heapify implementation can sort in place with O(1) auxiliary space.
COMMON QUESTIONS

❓ Common Interview Questions

Think about each question first. Open the answer only when you want to verify your understanding.

1. Why is Bubble Sort called “Bubble Sort”?

During each pass, larger values repeatedly move toward the end through adjacent swaps, similar to large bubbles rising to the top.

Interview answer: Large elements gradually “bubble” to the end of the array through adjacent swaps.
2. What is the main difference between Bubble Sort and Selection Sort?

Bubble Sort repeatedly swaps adjacent out-of-order elements. Selection Sort scans the unsorted portion to find the minimum and usually performs only one swap per pass.

Interview answer: Bubble Sort uses many adjacent swaps; Selection Sort selects the minimum and usually makes one swap per pass.
3. Why can optimized Bubble Sort have O(n) best-case time?

If a complete pass performs no swaps, the array is already sorted. The optimized version detects this and stops after one linear scan.

Interview answer: With a swapped flag, an already sorted array is recognized after one pass, giving O(n) best-case time.
4. Why is Insertion Sort good for nearly sorted data?

When most elements are already close to their correct positions, only a small number of shifts are needed for each key.

Interview answer: Insertion Sort is efficient on nearly sorted data because each key usually moves only a short distance.
5. Which of the six sorting algorithms on this page are stable?

The standard versions of Bubble Sort, Insertion Sort, and Merge Sort are stable. Standard Selection Sort, Quick Sort, and Heap Sort are not stable.

Interview answer: Stable here: Bubble, Insertion, Merge. Not stable: Selection, Quick, Heap.
6. Why does Merge Sort require extra memory for arrays?

During merging, values from the two sorted halves are copied into temporary storage before being copied back to the original array.

Interview answer: Array-based Merge Sort needs temporary storage during the merge step, so its auxiliary space is O(n).
7. When does Quick Sort reach O(n²) time?

Quick Sort reaches its worst case when partitioning repeatedly produces very unbalanced subarrays, such as one side containing almost all remaining elements.

Interview answer: Repeatedly poor pivots create highly unbalanced partitions, causing O(n²) time.
8. How can Quick Sort pivot selection be improved?

Common approaches include choosing a random pivot or using a median-of-three strategy. These reduce the chance of consistently poor partitions.

Interview answer: Randomized or median-of-three pivots reduce the probability of repeatedly unbalanced partitions.
9. Why does Heap Sort guarantee O(n log n) worst-case time?

After building the heap, each of the n removals restores the heap along a path whose height is O(log n).

Interview answer: Heap extraction costs O(log n), and repeating it for n elements gives O(n log n) worst-case time.
10. When would you choose Merge Sort instead of Quick Sort?

Merge Sort is attractive when stable sorting is required, predictable O(n log n) worst-case time matters, or data is stored in linked lists or external files. Quick Sort is often faster in-place for arrays.

Interview answer: Choose Merge Sort for stability and guaranteed O(n log n); Quick Sort is often preferred for fast in-place array sorting.
PRACTICE

🎯 20 Sorting Practice Problems

Try each problem yourself first. Use 💻 Solve It Yourself to write and test your C program. Use Hint only when needed, and Show Program if you want to study the complete solution.

📈 Sorting Practice Progress
Solved0 / 20
Completed with Solution0
Total Score0 / 2000
Completion0%
A problem counts as Solved when all tests pass without opening the full solution. Problems completed after viewing the solution are tracked separately.
1. Bubble Sort — Ascending

Sort the array in ascending order using Bubble Sort.

Input: n followed by n integers.

Output: the sorted array in ascending order.

Compare adjacent elements and swap when the left value is greater.
💻 Solve It Yourself — Bubble Sort — Ascending

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

5
5 1 4 2 8

Sample Output

1 2 4 5 8
2. Bubble Sort — Descending

Sort the array in descending order using Bubble Sort.

Input: n followed by n integers.

Output: the sorted array in descending order.

Reverse the Bubble Sort comparison so larger values move toward the beginning.
💻 Solve It Yourself — Bubble Sort — Descending

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] < a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

5
5 1 4 2 8

Sample Output

8 5 4 2 1
3. Count Bubble Sort Swaps

Perform ascending Bubble Sort and print how many swaps occur.

Input: n followed by n integers.

Output: total number of swaps.

Increment a counter every time two adjacent values are swapped.
💻 Solve It Yourself — Count Bubble Sort Swaps

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, swaps = 0;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
                swaps++;
            }

    printf("%d\n", swaps);
    return 0;
}

Sample Input

5
5 1 4 2 8

Sample Output

4
4. Optimized Bubble Sort — Count Passes

Use the swapped-flag optimization and print how many passes are actually executed.

Input: n followed by n integers.

Output: number of executed Bubble Sort passes.

After each pass, stop if no swap occurred.
💻 Solve It Yourself — Optimized Bubble Sort — Count Passes

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, passes = 0;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        passes++;

        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
                swapped = 1;
            }
        }

        if (!swapped)
            break;
    }

    printf("%d\n", passes);
    return 0;
}

Sample Input

5
5 1 4 2 8

Sample Output

3
5. Selection Sort — Ascending

Sort the array in ascending order using Selection Sort.

Input: n followed by n integers.

Output: sorted array.

For each position, find the smallest value in the remaining suffix.
💻 Solve It Yourself — Selection Sort — Ascending

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;

        for (int j = i + 1; j < n; j++)
            if (a[j] < a[minIndex])
                minIndex = j;

        if (minIndex != i) {
            int t = a[i];
            a[i] = a[minIndex];
            a[minIndex] = t;
        }
    }

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

5
64 25 12 22 11

Sample Output

11 12 22 25 64
6. Selection Sort — Descending

Sort the array in descending order using Selection Sort.

Input: n followed by n integers.

Output: sorted array in descending order.

Select the maximum value from the unsorted suffix for each position.
💻 Solve It Yourself — Selection Sort — Descending

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = 0; i < n - 1; i++) {
        int maxIndex = i;

        for (int j = i + 1; j < n; j++)
            if (a[j] > a[maxIndex])
                maxIndex = j;

        if (maxIndex != i) {
            int t = a[i];
            a[i] = a[maxIndex];
            a[maxIndex] = t;
        }
    }

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

5
64 25 12 22 11

Sample Output

64 25 22 12 11
7. Count Selection Sort Swaps

Perform ascending Selection Sort and print the number of actual swaps.

Input: n followed by n integers.

Output: number of swaps.

Count a swap only when minIndex is different from i.
💻 Solve It Yourself — Count Selection Sort Swaps

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, swaps = 0;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;

        for (int j = i + 1; j < n; j++)
            if (a[j] < a[minIndex])
                minIndex = j;

        if (minIndex != i) {
            int t = a[i];
            a[i] = a[minIndex];
            a[minIndex] = t;
            swaps++;
        }
    }

    printf("%d\n", swaps);
    return 0;
}

Sample Input

5
64 25 12 22 11

Sample Output

3
8. Insertion Sort — Ascending

Sort the array in ascending order using Insertion Sort.

Input: n followed by n integers.

Output: sorted array.

Take each value as key and shift larger values right.
💻 Solve It Yourself — Insertion Sort — Ascending

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;

        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }

        a[j + 1] = key;
    }

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

6
5 2 4 6 1 3

Sample Output

1 2 3 4 5 6
9. Insertion Sort — Descending

Sort the array in descending order using Insertion Sort.

Input: n followed by n integers.

Output: sorted array in descending order.

Shift values that are smaller than the key.
💻 Solve It Yourself — Insertion Sort — Descending

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;

        while (j >= 0 && a[j] < key) {
            a[j + 1] = a[j];
            j--;
        }

        a[j + 1] = key;
    }

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

6
5 2 4 6 1 3

Sample Output

6 5 4 3 2 1
10. Count Insertion Sort Shifts

Perform ascending Insertion Sort and count how many right shifts occur.

Input: n followed by n integers.

Output: total number of shifts.

Increment the counter whenever a[j] is copied to a[j+1].
💻 Solve It Yourself — Count Insertion Sort Shifts

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, shifts = 0;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;

        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            shifts++;
            j--;
        }

        a[j + 1] = key;
    }

    printf("%d\n", shifts);
    return 0;
}

Sample Input

6
5 2 4 6 1 3

Sample Output

9
11. Merge Sort — Ascending

Sort the array in ascending order using Merge Sort.

Input: n followed by n integers.

Output: sorted array.

Recursively divide, then merge the two sorted halves.
💻 Solve It Yourself — Merge Sort — Ascending

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

void merge(int a[], int l, int m, int r) {
    int n = r - l + 1;
    int t[n];
    int i = l, j = m + 1, k = 0;

    while (i <= m && j <= r)
        t[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];

    while (i <= m) t[k++] = a[i++];
    while (j <= r) t[k++] = a[j++];

    for (i = 0; i < k; i++)
        a[l + i] = t[i];
}

void mergeSort(int a[], int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    mergeSort(a, l, m);
    mergeSort(a, m + 1, r);
    merge(a, l, m, r);
}

int main() {
    int n;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    mergeSort(a, 0, n - 1);

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

6
38 27 43 3 9 82

Sample Output

3 9 27 38 43 82
12. Merge Sort — Descending

Sort the array in descending order using Merge Sort.

Input: n followed by n integers.

Output: sorted array in descending order.

During merge, copy the larger of the two current values first.
💻 Solve It Yourself — Merge Sort — Descending

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

void merge(int a[], int l, int m, int r) {
    int n = r - l + 1;
    int t[n];
    int i = l, j = m + 1, k = 0;

    while (i <= m && j <= r)
        t[k++] = (a[i] >= a[j]) ? a[i++] : a[j++];

    while (i <= m) t[k++] = a[i++];
    while (j <= r) t[k++] = a[j++];

    for (i = 0; i < k; i++)
        a[l + i] = t[i];
}

void mergeSort(int a[], int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    mergeSort(a, l, m);
    mergeSort(a, m + 1, r);
    merge(a, l, m, r);
}

int main() {
    int n;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    mergeSort(a, 0, n - 1);

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

6
38 27 43 3 9 82

Sample Output

82 43 38 27 9 3
13. Merge Two Sorted Arrays

Merge two already sorted arrays into one sorted sequence.

Input: n, first sorted array, m, second sorted array.

Output: merged sorted sequence.

Use two pointers, one for each array.
💻 Solve It Yourself — Merge Two Sorted Arrays

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n, m;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &m);
    int b[m];

    for (int i = 0; i < m; i++)
        scanf("%d", &b[i]);

    int i = 0, j = 0;

    while (i < n && j < m) {
        if (a[i] <= b[j])
            printf("%d ", a[i++]);
        else
            printf("%d ", b[j++]);
    }

    while (i < n) printf("%d ", a[i++]);
    while (j < m) printf("%d ", b[j++]);

    return 0;
}

Sample Input

3
1 4 7
4
2 3 6 8

Sample Output

1 2 3 4 6 7 8
14. Count Inversions using Merge Sort

Count pairs (i, j) where i < j but a[i] > a[j].

Input: n followed by n integers.

Output: inversion count.

When a right-half value is chosen before a left-half value, add the number of remaining left values.
💻 Solve It Yourself — Count Inversions using Merge Sort

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

long long mergeCount(int a[], int l, int m, int r) {
    int n = r - l + 1;
    int t[n];
    int i = l, j = m + 1, k = 0;
    long long inv = 0;

    while (i <= m && j <= r) {
        if (a[i] <= a[j]) {
            t[k++] = a[i++];
        } else {
            t[k++] = a[j++];
            inv += m - i + 1;
        }
    }

    while (i <= m) t[k++] = a[i++];
    while (j <= r) t[k++] = a[j++];

    for (i = 0; i < k; i++)
        a[l + i] = t[i];

    return inv;
}

long long countInv(int a[], int l, int r) {
    if (l >= r) return 0;

    int m = l + (r - l) / 2;
    long long ans = 0;

    ans += countInv(a, l, m);
    ans += countInv(a, m + 1, r);
    ans += mergeCount(a, l, m, r);

    return ans;
}

int main() {
    int n;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    printf("%lld\n", countInv(a, 0, n - 1));
    return 0;
}

Sample Input

5
2 4 1 3 5

Sample Output

3
15. Quick Sort — Ascending

Sort the array in ascending order using Quick Sort with the last element as pivot.

Input: n followed by n integers.

Output: sorted array.

Partition using the last element, then recursively sort both sides.
💻 Solve It Yourself — Quick Sort — Ascending

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int partition(int a[], int l, int h) {
    int pivot = a[h];
    int i = l - 1;

    for (int j = l; j < h; j++) {
        if (a[j] <= pivot) {
            i++;
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    int t = a[i + 1];
    a[i + 1] = a[h];
    a[h] = t;
    return i + 1;
}

void quickSort(int a[], int l, int h) {
    if (l < h) {
        int p = partition(a, l, h);
        quickSort(a, l, p - 1);
        quickSort(a, p + 1, h);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    quickSort(a, 0, n - 1);

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

6
10 7 8 9 1 5

Sample Output

1 5 7 8 9 10
16. Quick Sort — Descending

Sort the array in descending order using Quick Sort.

Input: n followed by n integers.

Output: sorted array in descending order.

In partition, move values greater than or equal to the pivot to the left side.
💻 Solve It Yourself — Quick Sort — Descending

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int partition(int a[], int l, int h) {
    int pivot = a[h];
    int i = l - 1;

    for (int j = l; j < h; j++) {
        if (a[j] >= pivot) {
            i++;
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    int t = a[i + 1];
    a[i + 1] = a[h];
    a[h] = t;
    return i + 1;
}

void quickSort(int a[], int l, int h) {
    if (l < h) {
        int p = partition(a, l, h);
        quickSort(a, l, p - 1);
        quickSort(a, p + 1, h);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    quickSort(a, 0, n - 1);

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

6
10 7 8 9 1 5

Sample Output

10 9 8 7 5 1
17. Lomuto Partition Step

Perform only one Lomuto partition using the last element as pivot. Print the partitioned array and then the pivot index.

Input: n followed by n integers.

Output: partitioned array on the first line and pivot index on the second line.

Use i = -1 and scan j from 0 to n-2.
💻 Solve It Yourself — Lomuto Partition Step

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    int pivot = a[n - 1];
    int i = -1;

    for (int j = 0; j < n - 1; j++) {
        if (a[j] <= pivot) {
            i++;
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    int t = a[i + 1];
    a[i + 1] = a[n - 1];
    a[n - 1] = t;

    for (int k = 0; k < n; k++)
        printf("%d ", a[k]);

    printf("\n%d\n", i + 1);
    return 0;
}

Sample Input

6
10 7 8 9 1 5

Sample Output

1 5 8 9 10 7
1
18. Heap Sort — Ascending

Sort the array in ascending order using a max heap.

Input: n followed by n integers.

Output: sorted array.

Build a max heap, then repeatedly move the root to the end.
💻 Solve It Yourself — Heap Sort — Ascending

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

void heapify(int a[], int n, int i) {
    while (1) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        if (l < n && a[l] > a[largest]) largest = l;
        if (r < n && a[r] > a[largest]) largest = r;

        if (largest == i) break;

        int t = a[i];
        a[i] = a[largest];
        a[largest] = t;
        i = largest;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(a, n, i);

    for (int i = n - 1; i > 0; i--) {
        int t = a[0];
        a[0] = a[i];
        a[i] = t;
        heapify(a, i, 0);
    }

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

6
12 11 13 5 6 7

Sample Output

5 6 7 11 12 13
19. Heap Sort — Descending

Sort the array in descending order using a min heap.

Input: n followed by n integers.

Output: sorted array in descending order.

Build a min heap, then move the minimum to the end repeatedly.
💻 Solve It Yourself — Heap Sort — Descending

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

void heapify(int a[], int n, int i) {
    while (1) {
        int smallest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        if (l < n && a[l] < a[smallest]) smallest = l;
        if (r < n && a[r] < a[smallest]) smallest = r;

        if (smallest == i) break;

        int t = a[i];
        a[i] = a[smallest];
        a[smallest] = t;
        i = smallest;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(a, n, i);

    for (int i = n - 1; i > 0; i--) {
        int t = a[0];
        a[0] = a[i];
        a[i] = t;
        heapify(a, i, 0);
    }

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

Sample Input

6
12 11 13 5 6 7

Sample Output

13 12 11 7 6 5
20. Kth Largest Element using Heap

Find the kth largest element using a max heap.

Input: n, n integers, then k (1-based).

Output: kth largest value.

Build a max heap and extract the maximum k-1 times.
💻 Solve It Yourself — Kth Largest Element using Heap

C Code Editor

Sample Input

Program Output

Run your program to see the output.

Test Cases

No tests checked yet.—
Best Score0 / 100
Attempts0
StatusNot Solved
Write your C program and test it. You can do it! 💪
Scoring: up to 100 marks without help; up to 90 after viewing a hint. If the full solution is opened, the problem can still be marked Completed, but it is no longer counted as a competitive score.
#include <stdio.h>

void heapify(int a[], int n, int i) {
    while (1) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        if (l < n && a[l] > a[largest]) largest = l;
        if (r < n && a[r] > a[largest]) largest = r;

        if (largest == i) break;

        int t = a[i];
        a[i] = a[largest];
        a[largest] = t;
        i = largest;
    }
}

int main() {
    int n, k;
    scanf("%d", &n);
    int a[n];

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    scanf("%d", &k);

    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(a, n, i);

    int heapSize = n;

    for (int count = 1; count < k; count++) {
        int t = a[0];
        a[0] = a[heapSize - 1];
        a[heapSize - 1] = t;
        heapSize--;
        heapify(a, heapSize, 0);
    }

    printf("%d\n", a[0]);
    return 0;
}

Sample Input

6
12 3 5 7 19 1
3

Sample Output

7
← Previous Topic: Searching Next Topic: Linked-list →