[go: up one dir, main page]

0% found this document useful (0 votes)
28 views17 pages

CMP 202 (Sorting)

Uploaded by

Akorede Bashir
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
28 views17 pages

CMP 202 (Sorting)

Uploaded by

Akorede Bashir
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 17

Usmanu Danfodiyo University, Sokoto

Department of Computer Science

CMP 202: Computer Programming II

SORTING

1
CONTENTS

❖ What is Sorting?

❖ Types of Sorting Algorithms


✓ Bubble Sort
✓ Selection Sort

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
}
}

❖ The algorithm will terminate because when the condition


i<n-1 at line is tested, it will be true.
❖ The remaining element “10” is in its correct position 15
Selection Sort (Java Implementation)
❖ The below code shows implementation of bubble sort in Java programming

public class SelectionSort{ public static void main (String[] args) {


public void printArray(int[] arr) { int[] arr = new int[] {5, 1, 2, 9, 10};
int n = arr.length; SelectionSort ss = newSelectionSort();
for (int i=0; i<n; i++) { ss.printArray(arr);
System.out.print(arr[i] + " "); ss.sort(arr);
} ss.printArray(arr);
System.out.println(); }
} }

public void sort(int[] arr){


int n = arr.length;
for(int i=0; i<n-1; i++){
int min = i;
for(int j=i+1; i<n; j++){ Output:
if arr[j] < arr[min]{
min = j;
} 5 1 2 9 10
} 1 2 5 9 10
int temp = arr[min];
arr[min] = arr[i]
arr[i] = temp;
}
}

16
END OF SORTING

17

You might also like