CMP 202 (Sorting)
CMP 202 (Sorting)
SORTING
1
CONTENTS
❖ What is Sorting?
2
WHAT IS SORTING?
3
Introduction to Sorting
❖ While getting into the world of programming, many problems will include
working with multiple instances of similar types of data.
❖ Generally, these data will take the help of arrays for their storage.
❖ The bigger question is how to optimize the solution for a particular problem
to fit within a particular amount of time.
❖ The generalized answer is arranging the elements within the array in such a
way that an order is maintained.
❖ This is the process of sorting, used in many programming languages like
Java, Python, and other high-level programming languages.
4
Introduction to Sorting (Cont)…
❖ Sorting is a class of algorithms that are tasked with rearranging the positions of elements of
an array such that all of its elements are either in ascending or descending order.
❖ A good sorting algorithm also needs to ensure that elements having the same value don’t
change their locations in the sorted array.
❖ Sorting is necessary for getting a concrete understanding of data structures and
algorithms.
❖ There are different types of sorting algorithms which include:
✓ Bubble Sort
✓ Selection Sort
✓ Merge Sort
✓ Heap Sort
✓ Insertion Sort
5
BUBBLE SORT
6
Bubble Sort
❖ It is also called sinking sort
❖ While applying this sorting algorithm on an unsorted array, the largest element tends to sink
at the end of the array.
❖ It repeatedly compares a pair of adjacent elements and swaps them if they are in the
wrong order.
3 1 5 2 6 4
❖ First, compare 3 and 1, if the leftmost element is greater than the rightmost element, then
we swap the elements otherwise we will not swap.
❖ In this case, 3 is greater than 1, we then swap and the array will be:
1 3 5 2 6 4
7
Bubble Sort (Cont…)
❖ Then, we compare 3 and 5, if the leftmost element is greater than the rightmost element,
then we swap the elements otherwise we will not swap.
1 3 5 2 6 4
❖ The process will be repeated until we reach the end of 1st Pass and we have the array:
1 3 2 5 4 6
❖ Then we start the 2nd pass by comparing 1 and 3, then 3 and 2 ………
1 2 3 5 4 6
❖ Compare 3 and 5, there will be no swap…. Then compare 5 and 4, there will be a swap
1 2 3 4 5 6
❖ Then we move to the 3rd pass and compare 1 and 2, 2 and 3, 3 and 4 ………
❖ An array becomes sorted when no swap occurs in a given pass.
❖ In this case, after the second pass, we already have a sorted array because all elements
are in the correct position. 8
Bubble Sort (Cont…)
❖ Consider the array: 5 1 9 2 10 n = 5;
boolean isSwapped;
❖ isSwapped is a Boolean variable that keeps track to know if a
for (int i = 0; i < n-1; i++;
swap is done in a given iteration isSwapped = false;
for(int j=0; j<n-1-i; j++;
❖ j at line 4 will be 1 (index 1) at the first iteration.
if (arr[j] > arr[j+1]){
❖ After the first swap, it will be incremented to 2 (index 2). int temp = arr[j];
arr[j] = arr[j+1];
❖ j is incremented at the end of every iteration
arr[j+1] = temp;
❖ temp is used to store the element that will be moved from the isSwapped = true;
}
leftmost side, in this case, temp will hold 5 and after 1 has
}
been swapped into index 0, then the element in temp will be If (isSwapped == false)
break;
swapped to index 1
}
❖ The for loop exits when j=4 and that marks the end of 1st pass.
1 5 2 9 10
1 2 5 9 10
❖ Line 9 is true, meaning the array is not sorted.
❖ Once line 12 is true, then the array is sorted.
9
Bubble Sort (Java Implementation)
❖ The below code shows implementation of bubble sort in Java programming
public class Bubblesort{
public void printArray(int[] arr) { if (isSwapped ==false){
int n = arr.length; break;
for (int i=0; i<n; i++) { }
System.out.print(arr[i] + " "); }
} }
System.out.println();
} public static void main (String[] args) {
int[] arr = new int[] {5, 1, 2, 9, 10};
public void sort(int[] arr){ BubbleSort bs = newBubbleSort();
int n = arr.length; bs.printArray(arr);
boolean isSwapped; bs.sort(arr);
bs.printArray(arr);
for (i=0; i < n-1; i++){ }
isSwapped = false; }
for (int j=0; j < n-1-i; j++){
//compare adjacent elements
if (arr[j] > arr[j+1]){
//create a temp location to swap element at index j
int temp = arr[j]; Output:
arr[j] = arr[j+1];
arr[j+1] = temp;
5 1 2 9 10
isSwapped = true;
} 1 2 5 9 10
}
10
SELECTION SORT
11
Selection Sort
❖ In selection sort, we divide the given array into two parts – sorted and unsorted part.
❖ The algorithm sorts an array by repeatedly finding the minimum in an unsorted array and
making it part of the sorted array.
❖ From unsorted part, we pick minimum element and swap it with leftmost element of
unsorted part.
❖ After swap, the element now becomes part of the sorted array.
0 1 2 3 4
3 1 5 2 6
Sorted Unsorted
❖ It repeated till unsorted part is empty and all element are moved to the sorted part.
0
1 3 5 2 6
Sorted Unsorted
12
Selection Sort (Example)
❖ Lets use Selection sort to sort the below array
0 1 2 3 4 5 0 1 2 3 4 5
3 1 5 2 6 4 1 3 5 2 6 4
Sorted Unsorted
❖ After the 1st Pass, 1 is found to be the smallest element, then we swap and move 1 to the
unsorted part. 0
1 3 5 2 6 4
Sorted Unsorted
❖ Then, we move to the 2nd Pass, we found 2 to be the smallest, we swap it with the first
element in the unsorted part: 2 5 3 6 4
❖ We then move 2 to the sorted part of the array
0 1
1 2 5 3 6 4
Sorted Unsorted 13
Selection Sort (Example…)
❖ We move to the 3rd pass, we have the below after the pass
1 2 3 5 6 4
Sorted Unsorted
❖ Then we move to the 4th Pass, then we will have the below array
1 2 3 4 6 5
Sorted Unsorted
❖ At the end of the 5th Pass, we will have:
1 2 3 4 5 6
Sorted Unsorted
❖ Since, we only have one element left in the unsorted part, it means all elements are in their
correct position.
1 2 3 4 5 6
14
Selection Sort (Cont…)
❖ Consider the array: 5 1 10 2 9 n = 5;
Public void sort(int[]arr){
int n = arr.length;
❖ After 1st Pass 1 5 10 2 9
for(int i=0; i<n-1; i++){
int min = i;
for(int j=i+1; j<n; j++){
❖ After 2nd Pass 1 2 10 5 9 if(arr[j] < arr[min]){
min = j;
}
1 2 5 10 9 }
❖ After 3rd Pass
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
❖ After the 4th Pass 1 2 5 9 10
}
}
16
END OF SORTING
17