7. Sorting

Bubble, selection, insertion

0 of 5 activities0%

Reading 1

Three classics

Open

Bubble sort: swap adjacent out-of-order pairs repeatedly. Selection sort: repeatedly select the minimum for the next slot. Insertion sort: grow a sorted prefix by inserting the next element.

All O(n^2) typical. Insertion is fast on nearly sorted data.

// selection sort sketch
for (int i=0;i<n;i++){
  int m=i;
  for(int j=i+1;j<n;j++) if(a[j]<a[m]) m=j;
  swap(a[i],a[m]);
}

Check 2

Nearly sorted

Open

Often best among elementary sorts on nearly sorted arrays:

Fill in 3

Adjacent

Open

Try it 4

Selection sort

Open

Sort 4 ints.

main.cpp

Loading editor…

Program input (stdin)

Output will appear here.

Assignment 5

Sort ascending

Open

Read n and n ints. Print them sorted ascending (any correct sort).

main.cpp

Loading editor…

Binary search variants Merge sort