COMP 202 Lecture 7: COMP 202 - Lecture 7
8 Jun 2018
School
Department
Course
Professor
COMP 202: Foundations Of Programming
Lecture 7: Sorting
Sorting: one of the important applications of programming – takes an unordered collection and makes it an
ordered one.
- Given an array of numbers, arranging them according to some rule (ascending or descending order)
Many algorithms exist to sort a given list:
- Bubble sort
- Insertion sort
- Merge sort
Bubble Sort:
Bubble sort is the algorithm that is closest to human thought
Let the array length be N, and assume we are sorting the array in ascending order.
We will go through the array N time:
- We keep swapping adjacent elements of the array that are in the wrong order
- Gradually, all the largest elements will end up at the end of the array
After at most (N-1) passes through the array, it will be sorted
→ Referred to as a bubble because larger bubbles rise to the top in a carbonated drink
What we’re doing is “bubbling” the largest value to the end of the array using pair-wise comparisons and
swapping, while traversing a collection of elements.
The “Bubble Up” Algorithm:
In the first line, only the largest element is correctly placed, so we need to repeat this process. We repeat the
“bubble up” process N – 1 times (where N = number of elements). The assumption is that every time we bubble
up an element, we end up correctly placing it, guaranteeing that we’ll correctly place N elements.
find more resources at oneclass.com
find more resources at oneclass.com
100
COMP 202 Full Course Notes
Verified Note
100 documents
Document Summary
Sorting: one of the important applications of programming takes an unordered collection and makes it an ordered one. Given an array of numbers, arranging them according to some rule (ascending or descending order) Many algorithms exist to sort a given list: Bubble sort is the algorithm that is closest to human thought. Let the array length be n, and assume we are sorting the array in ascending order. We will go through the array n time: We keep swapping adjacent elements of the array that are in the wrong order. Gradually, all the largest elements will end up at the end of the array. After at most (n-1) passes through the array, it will be sorted. Referred to as a bubble because larger bubbles rise to the top in a carbonated drink. What we"re doing is bubbling the largest value to the end of the array using pair-wise comparisons and swapping, while traversing a collection of elements.
