---
title: "Algorithm for an exchange sort"
subject: "Data Structure and Algorithm"
chapter: 7
key: "semester_4/data_structure_and_algorithm:exchange-sort-algorithm"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/exchange-sort-algorithm
site: BCT Engineering
---

# Algorithm for an exchange sort

Data Structure and Algorithm · Chapter 7: Sorting

- Asked in: 2068 Bhadra, 3 marks; 2068 Magh, 3 marks (asked 2 times)
- Video: [Exchange Sort Array Based](https://www.youtube.com/watch?v=WAghvb7yJiU) — C343 Videos
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/exchange-sort-algorithm
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-7

## Question

Write an algorithm for any one of the exchange sort (any sorting algorithm of your choice).

## Short answer

Bubble sort repeatedly scans the array, comparing adjacent elements and swapping them if out of order. After each pass the largest unsorted element bubbles to its correct end position. Complexity is O(n²) average/worst, O(n) best if early stop is used.

## Answer

**Bubble sort** is an exchange sort. It repeatedly compares adjacent elements and exchanges them if they are out of order. After each pass the largest remaining element "bubbles" to the end.

#### Algorithm
```text
BubbleSort(a[0..n-1])
1. for pass = 1 to n-1
2.     swapped = 0
3.     for i = 0 to n-pass-1
4.         if a[i] > a[i+1]: swap a[i], a[i+1]; swapped = 1
5.     if swapped = 0: stop     (already sorted)
```

#### C code
```c
void bubble_sort(int a[], int n) {
    int pass, i, t, swapped;
    for (pass = 1; pass < n; pass++) {
        swapped = 0;
        for (i = 0; i < n - pass; i++) {
            if (a[i] > a[i + 1]) {          /* exchange */
                t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;
                swapped = 1;
            }
        }
        if (!swapped) break;                /* no exchange: sorted */
    }
}
```

#### Trace for 5 3 8 1
| Pass | Array after pass |
|---|---|
| 0 | 5 3 8 1 |
| 1 | 3 5 1 8 |
| 2 | 3 1 5 8 |
| 3 | 1 3 5 8 |

Complexity: worst and average O(n²), best O(n) (already sorted, with the `swapped` flag). It is stable and in-place, using O(1) extra space.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does one pass of bubble sort do?
   A. Selects the smallest element and puts it first
   B. Compares adjacent elements, exchanging out-of-order pairs, so the largest remaining element moves to the end
   C. Splits the list into halves
   D. Distributes elements into buckets
   Answer: B. Adjacent exchanges carry the largest remaining element to the end of the unsorted part. (Key point: Bubble sort idea)

2. What is the purpose of the swapped flag?
   A. To count the number of swaps
   B. To stop early when a pass makes no exchange, since the list is already sorted
   C. To make the sort stable
   D. To reduce space use
   Answer: B. If no exchange occurs in a pass the list is sorted, giving best case O(n). (Key point: Swapped flag)

3. What is the bubble sort complexity with the flag?
   A. Best O(n), worst and average O(n^2)
   B. Always O(n log n)
   C. Best O(1), worst O(n)
   D. Always O(n^2)
   Answer: A. An already sorted list needs one pass (O(n)); otherwise O(n^2). It is stable and in-place. (Key point: Complexity)

## Related in Data Structure and Algorithm

- [Stable vs unstable sorting; heap](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astable-unstable-heap) — Data Structure and Algorithm, chapter 7
- [Radix sort definition and algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aradix-sort-algorithm) — Data Structure and Algorithm, chapter 7
- [Merge sort algorithm and trace](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-sort-algorithm-trace) — Data Structure and Algorithm, chapter 7
- [Heap sort with example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aheap-sort-example) — Data Structure and Algorithm, chapter 7
- [Merge and radix sort on 142, 523, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-radix-trace-142) — Data Structure and Algorithm, chapter 7
- [Radix sort on 25, 57, 48, 37, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aradix-sort-25-57-48) — Data Structure and Algorithm, chapter 7

## Related in other subjects

- [Remez exchange algorithm with flow chart](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Aremez-flowchart-explain) — Digital Signal Analysis and Processing, chapter 5, asked 4×
- [Need for non-uniform quantization; one algorithm](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Anonuniform-quantization-algorithm) — Communication Systems, chapter 4
- [Optimum filter; Remez exchange expression](https://www.bctengineer.com/question.md?key=semester_7%2Fdigital_signal_analysis_and_processing%3Aoptimum-filter-remez-expression) — Digital Signal Analysis and Processing, chapter 5, asked 5×
- [Nepal Airlines jet plane choice, 4 years and infinite](https://www.bctengineer.com/question.md?key=semester_6%2Fengineering_economics%3Anepal-airlines-jet-plane-4yr-infinite) — Engineering Economics, chapter 4