Week4: (Chapter 4)
SORTING TECHNIQUES
Given a set (container) of n elements
– E.g. array, set of words, etc.
Suppose there is an order relation that can be set
across the elements
Goal Arrange the elements in ascending order
– Start 1 23 2 56 9 8 10 100
– End 1 2 8 9 10 23 56 100
Week4: (Chapter 4)
SORTING TECHNIQUES
Bubble sort, Insertion sort, Selection sort,
Quick sort, Heap sort, Merge sort, Exchange
sort …
Focus on
– Bubble sort
– Insertion sort
– Selection sort
– Exchange sort
– Quick sort
1.Bubble sort: idea
arrange the elements of the list by forming
pairs of adjacent elements.
The pair of the ith and (i+1)th element.
If the order is ascending, we interchange the
elements of the pair
This will bring the highest value from among
the remaining (n−1) values to the (n−1)th
position.
1.Bubble sort: idea
Why it is called Bubble?
3 7 5 2 4 compare 3 and 7 ; 7 is > 3 so advance
3 5 7 2 4 compare 7 and 5, 7 > 5 so swap them
3 5 2 7 4 compare 7 and 2, 7 >4 so swap them
3 5 2 4 7 compare 7 and 4, 7 >4 so swap them
End of pass 1; notice that 7 is in the right place
2.Bubble sort: idea
Simplest sorting algorithm
Idea:
– 1. Set flag = false
– 2. Traverse the array and compare pairs of two
elements
1.1 If E1 ≤ E2 - OK
1.2 If E1 > E2 then Switch(E1, E2) and set flag = true
– 3. If flag = true goto 1.
What happens?
1.Bubble sort:algorithm idea
void bubbleSort (Array S, length n) {
boolean isSorted = false;
while(!isSorted)
{
isSorted = true;
for(i = 0; i<n; i++)
if(S[i] > S[i+1])
{
swap(S[i],S[i+1];)
isSorted = false;
}
}
1.Bubble sort: implement
void bsort(int list[], int n)
{
int count,j;
for(count=0;count<n-1;count++)
for(j=0;j<n-1-count;j++)
if(list[j] > list[j+1])
swap(list[j],list[j+1]);
} DEMO
2. Exchange Sorting
Method : make n-1 passes across the data,
on each pass compare adjacent items,
swapping as necessary (n-1 compares)
O(n2)
2. Exchange Sorting
void Exchange_sort(int arr[], int n)
{
int i,j;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(arr[i] > arr[j])
swap(arr[i],arr[j]);
} DEMO
2. Exchange Sorting
Notes:
– on each successive pass, do one less compare,
because the last item from that pass is in place
– if you ever make a pass in which no swap occurs,
the sort is complete
– There are some algorithms to improve
performance but Big O will remain O(n2)
3. Insertion Sort
Strategy: divide the collection into two lists,
one listed with one element (sorted) and the
other with the remaining elements.
On successive passes take an item from the
unsorted list and insert it into the sorted list
so the the sorted list is always sorted
Do this until the unsorted list is empty
3. Insertion Sort
sorted unsorted
3 7 5 2 4
take an item from the unsorted list (7) and
insert into the sorted list
sorted unsorted
3 7 5 2 4
take next item from the unsorted list (5) and
sorted unsorted insert into the sorted list
3 5 7 2 4
take next item from the unsorted list (2)
sorted unsorted and insert into the sorted list
2 3 5 7 4
take next item from the unsorted list (4)
sorted unsorted and insert into the sorted list
2 3 4 5 7
3. Insertion Sort
void insertionSort(int arr[], int n){
int j, key;
for(int i = 1; i < n; i++){
key = arr[i];
j = i - 1;
while(j >= 0 && arr[j] > key)
{ arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
3. Insertion Sort
Note that each insertion could be O(n-1) and
there are n-1 insertions being done therefore
Big O is O(n2)
This is very much like building an ordered
linked list except there is more data
movement
4. Selection Sort
Strategy: make a pass across the data
looking for the largest item, swap the largest
with the last item in the array.
On successive passes (n-1) assume the
array is one smaller (the last item is in the
correct place) and repeat previous step
biggest last
3 7 5 2 4
4. Selection Sort
3 4 5 2 7
biggest last
3 4 5 2 7
3 4 2 5 7
biggest last
3 4 2 5 7
3 2 4 5 7
3 2 4 5 7
2 3 4 5 7
4. Selection Sort
void selection_sort(int arr[], int n)
{int i, j, min;
for (i = 0; i < n - 1; i++)
{
min = i;
for (j = i+1; j < n; j++)
{ if (list[j] < list[min]) min = j; }
swap(arr[i],arr[min]);
}
}
4. Selection Sort
Notice that in selection sort, there is the least
possible data movement
There are still n-1 compares on sublists that
become one item smaller on each pass so,
Big O is still O(n2)
This method has the best overall
performance of the O(n2) algorithms because
of the limited amount of data movement
5. Quick Sort
This sorting method by far outshines all of the others
for flat out speed
Big O is log2n
there are problems, worst case performance is when
data is already in sorted order or is almost in sorted
order (we’ll analyze this separately)
and there are solutions to the problems
and there is an improvement to make it faster still
5. Quick Sort
Sorting algorithms that rely on the “DIVIDE
AND CONQUER” paradigm
– One of the most widely used paradigms
– Divide a problem into smaller sub problems, solve
the sub problems, and combine the solutions
– Learned from real life ways of solving problems
5. Quick Sort
Another divide-and-conquer sorting algorihm
To understand quick-sort, let’s look at a high-level description of
the algorithm
1) Divide : If the sequence S has 2 or more elements, select an
element x from S to be your pivot. Any arbitrary element, like
the last, will do. Remove all the elements of S and divide them
into 3 sequences:
L, holds S’s elements less than x
E, holds S’s elements equal to x
G, holds S’s elements greater than x
2) Recurse: Recursively sort L and G
3) Conquer: Finally, to put elements back into S in order, first
inserts the elements of L, then those of E, and those of G.
The image cannot be display ed. Your computer may not hav e enough memory to open the image, or the image may hav e been corrupted. Restart y our computer, and then open the file again. If the red x still appears, y ou may hav e to delete the image and then insert it again.
5. Quick Sort: idea
1) Select: pick an element
2) Divide: rearrange
elements so that x goes to its
final position E
3) Recurse and Conquer:
recursively sort
Quick Sort
Pick the leftmost element as the pivot (23). Now , start two cursors (one at either end) going towards the middle
and swap values that are > pivot (found with left cursor) with values < pivot (found with right cursor)
23 17 5 12 19 24 4 43 34 11 3 33 14 26 8 27
swap
23 17 5 12 19 8 4 43 34 11 3 33 14 26 24 27
swap
23 17 5 12 19 8 4 14 34 11 3 33 43 26 24 27
swap
23 17 5 12 19 8 4 14 3 11 34 33 43 26 24 27
swap
Finally, swap the pivot and the value where the cursors passed each other
11 17 5 12 19 8 4 14 3 23 34 33 43 26 24 27
Note : 23 is now in the right place and everything to its left is < 23
and everything to its right is > 23
Quick Sort (worst case)
If the data is already sorted watch what happens to the partitions
3 4 5 8 11 12 14 17 19 23 24 26 27 33 34 43
There is nothing to swap
4 5 8 11 12 14 17 19 23 24 26 27 33 34 43
Again, nothing to swap…..
The partitions are always the maximum size and the performance
degrades to O(n2)
Quick Sort
void quickSort(int Arr[], int lower, int upper)
{
int x = Arr[(lower + upper) / 2];
int i = lower; int j = upper;
do{
while(Arr[i] < x) i ++;
while (Arr[j] > x) j --;
if (i <= j)
{
swap(Arr[i], Arr[j]);
i ++; j --; }
}while(i <= j);
if (j > lower)
quickSort(Arr, lower, j);
if (i < upper)
quickSort(Arr, i, upper);
}
