Sorting algorithms: bubble, insertion and merge sort

Aprenda jogando

Responda a estas perguntas para ganhar energia, depois pesque e explore. Sem precisar de conta.

Para educadores: slides de aula, resumos de revisão prontos para usar de Sorting algorithms: bubble, insertion and merge sort (Computer Science, Algorithms) — use na sua aula ou rode o tópico como atividade interativa de turma que seus aprendizes jogam como um jogo ao vivo.

Notas de aula Slides Questões de prática

Notas de aula

Why sort?

Sorted data is easier to search (binary search) and to display. Sorting algorithms put items in order (ascending or descending).

Bubble sort

Repeatedly compare adjacent pairs and swap them if they are in the wrong order. After each pass the largest unsorted item "bubbles" to the end. Stop when a complete pass makes no swaps.
Example: 5, 2, 4 → compare 5 and 2, swap: 2, 5, 4 → compare 5 and 4, swap: 2, 4, 5. A further pass has no swaps, so it stops.
Simple but slow for large lists.

Bubble sort

Insertion sort

Treat the first item as sorted. Take the next item and insert it into the correct position among the sorted items by shifting larger items right. Repeat until all items are sorted.
Efficient for small or nearly sorted lists.

Insertion sort

Merge sort

A divide and conquer algorithm: split the list into halves repeatedly until each part has one item, then merge the parts back together in order.
Much faster for large lists but uses more memory, and it is more complex.

Merge sort

Comparing

Bubble: simple, slow. Insertion: good for small lists. Merge: fast, memory-hungry.

Slides

Step through every slide for this topic — plus flashcards and revision notes — with a free account.

CADASTRE-SE — GRÁTIS ENTRAR

Questões de prática

Prévia grátis — 8 de 33 perguntas. Cadastre-se para ver todas.

1.What is a sorting algorithm?
Easy
- Aone that puts data into order
- Bone that finds data
- Cone that deletes data
- Done that copies data
2.What does bubble sort compare?
Easy
- Aadjacent items
- Bfirst and last
- Crandom items
- Dmiddle items
3.What happens if two adjacent items are in the wrong order in bubble sort?
Easy
- Athey are swapped
- Bthey are deleted
- Cthey are merged
- Dthey are ignored
4.What does insertion sort do with each new item?
Easy
- Ainserts it into the correct place in the sorted part
- Bswaps it with the last
- Cdeletes it
- Dmerges it
5.What is merge sort based on?
Easy
- Adivide and conquer
- Bswapping neighbours
- Csearching
- Dhashing
6.One left-to-right pass of ascending bubble sort on 4, 2, 5, 1 gives:
Easy
- A2, 4, 1, 5
- B1, 2, 4, 5
- C4, 2, 5, 1
- D5, 4, 2, 1
7.Which value reaches its final position after the first left-to-right pass of ascending bubble sort?
Easy
- Athe largest
- Bthe smallest
- Cthe middle
- Dthe first
8.What is a 'pass'?
Easy
- Aone complete run through the list
- Bone swap
- Cone comparison
- Done item

Mais perguntas

9.What is a disadvantage of conventional array-based merge sort compared with in-place bubble sort?
Easy
- Ait uses more memory
- Bit is slow
- Cit cannot sort numbers
- Dit needs no data
10.What is an advantage of insertion sort?
Easy
- Ait works well on small or nearly sorted lists
- Bit is the fastest for huge lists
- Cit uses lots of memory
- Dit is hard to write
11.What is a swap?
Easy
- Aexchanging the positions of two items
- Bdeleting an item
- Ccopying an item
- Dsearching
12.How many comparisons are in the first pass of bubble sort for 6 items?
Medium
- A5
- B6
- C3
- D1
13.Insertion sort on 3, 1, 2: after inserting 1, the list is:
Medium
- A1, 3, 2
- B3, 1, 2
- C1, 2, 3
- D2, 1, 3
14.In merge sort, what is the base case?
Medium
- Aa list of one item
- Ban empty list only
- Ca sorted list of ten
- Dthe original list
15.Merge two sorted lists 2, 6 and 3, 4. The result is:
Medium
- A2, 3, 4, 6
- B2, 6, 3, 4
- C3, 4, 2, 6
- D6, 4, 3, 2
16.Why is bubble sort inefficient for large lists?
Medium
- Amany passes and comparisons are needed
- Bit uses lots of memory
- Cit is complex
- Dit needs sorted data
17.Among these choices, which is generally suitable for sorting a very large arbitrary list?
Medium
- Amerge sort
- Bbubble sort
- Clinear search
- Dnone
18.A bubble sort pass makes no swaps. What does that tell you?
Medium
- Athe list is already sorted
- Bthe list is empty
- Cthe algorithm failed
- Dthe list is reversed
19.Why might merge sort be unsuitable for a device with very little memory?
Medium
- Ait needs extra space to merge
- Bit cannot compare
- Cit is too simple
- Dit is too slow
20.What is the first item in the sorted section for insertion sort?
Medium
- Athe first item of the list
- Bthe last item
- Cthe smallest
- Dthe median
21.For a small already-sorted list, which listed implementation typically avoids repeated whole-list passes?
Medium
- Ainsertion sort
- Bmerge sort
- Cbubble sort without a flag
- Dnone
22.What does 'ascending order' mean?
Easy
- Asmallest to largest
- Blargest to smallest
- Crandom
- Dalphabetical only
23.What does 'descending order' mean?
Easy
- Alargest to smallest
- Bsmallest to largest
- Crandom
- Dnone
24.What does 'divide and conquer' mean?
Medium
- Abreak a problem into smaller parts and combine solutions
- Bdelete part of a problem
- Cignore it
- Dcopy it
25.Which algorithm repeatedly swaps out-of-order adjacent pairs until the list is sorted?
Medium
- Abubble sort
- Bmerge sort
- Cquicksort
- Dheap sort
26.Bubble sort compares adjacent items.
Easy
True or false?
27.Merge sort uses divide and conquer.
Easy
True or false?
28.Insertion sort is the fastest sort for very large lists.
Easy
True or false?
29.A bubble sort can stop when a pass has no swaps.
Easy
True or false?
30.Conventional array-based merge sort uses less auxiliary memory than an in-place bubble sort.
Medium
True or false?
31.Which are sorting algorithms?
Medium
- Abubble sort
- Binsertion sort
- Cmerge sort
- Dquick sort
- Ebinary search
32.Which describe conventional array-based merge sort?
Medium
- Auses divide and conquer
- Bhas good comparison growth for large arbitrary lists
- Cuses temporary merge storage
- Ddivides lists into halves
- Eis always the simplest algorithm to understand
33.Show the first pass of a bubble sort on the list 4, 3, 2, 1 (ascending).
Medium

Unlock all 33 questions & more

Crie uma conta grátis para ver todas as perguntas, os slides, flashcards e resumos de revisão deste tópico.

CADASTRE-SE — GRÁTIS ENTRAR

Provas anteriores

A prática com provas anteriores deste tópico chega em breve.

Em breve