Sorting
Algorithms
By Dr. AJK
Sorting 01 Agenda
Understand what sorting is
Style
Bubble Sorting 01
Algorithm and code
Selection Sorting 01
Algorithm and code
Conclusion 01
Slight change in conclusion
Sorting
A sorting algorithm is used to arrange Algorithms
elements of an array/list in a specific order.
For example,
Rearranging an collection (array)
in ascending or descending
order.
• Bubble sort is a sorting algorithm that compares two
adjacent elements and swaps them until they are in the Bubble
intended order.
• Just like the movement of air bubbles in the water that rise
up to the surface, each element of the array move to the
Sort
end in each iteration.
• Therefore, it is called a bubble sort.
• The details of the steps are:
1. First Iteration (Compare and Swap)
1. Starting from the first index, compare the first and the
second elements.
2. If the first element is greater than the second element, Rearranging an collection (array)
in ascending or descending
they are swapped. order.
3. Now, compare the second and the third elements.
Swap them if they are not in order.
[Link] above process goes on until the last
element. Sorting
Algorithms
Rearranging an collection (array)
in ascending or descending
order.
2. Remaining Iteration
1. The same process goes on for the remaining iterations. Bubble
2. After each iteration, the largest element among the
unsorted elements is placed at the end. Sort
• Bubble sort algorithm: Bubble
bubbleSort(array) Sort
for i <- 1 to sizeOfArray - 1
for j <- 1 to sizeOfArray - 1 - i
if leftElement > rightElement
Algorithm
swap leftElement and rightElement
end bubbleSort
Rearranging an collection (array)
in ascending or descending
order.
import [Link];
class Main {
// perform the bubble sort
static void bubbleSort(int array[]) {
int size = [Link];
// loop to access each array element
for (int i = 0; i < size - 1; i++)
// loop to compare array elements
for (int j = 0; j < size - i - 1; j++)
// change > to < to sort in descending order
if (array[j] > array[j + 1]) {
// are not in the intended order
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
public static void main(String args[]) {
int[] data = { -2, 45, 0, 11, -9 };
// call method using class name
[Link](data);
[Link]("Sorted Array in Ascending Order:");
[Link]([Link](data));
}
}
• Selection sort is a sorting algorithm that
selects the smallest element from an unsorted Selection
list in each iteration and places that element at
the beginning of the unsorted list. Sort
• Steps:
• Set the first element as minimum.
• Compare minimum with the second element. If
the second element is smaller than minimum,
assign the second element as minimum.
• Compare minimum with the third element.
• Again, if the third element is smaller, then assign Selection
minimum to the third element otherwise do nothing.
• The process goes on until the last element.
• After each iteration, minimum is placed in the front of
Sort
the unsorted list.
Rearranging an collection (array)
in ascending or descending
order.
• Selection Algorithm:
Selection
• selectionSort(array, size)
• for i from 0 to size - 1 do
Sort
• set i as the index of the current minimum
• for j from i + 1 to size - 1 do
• if array[j] < array[current minimum]
• set j as the new current minimum index
• if current minimum is not i
• swap array[i] with array[current minimum]
• end selectionSort
import [Link];
class SelectionSort {
void selectionSort(int array[]) {
int size = [Link];
for (int step = 0; step < size - 1; step++) {
int min_idx = step;
for (int i = step + 1; i < size; i++) {
// To sort in descending order, change > to < in this line.
// Select the minimum element in each loop.
if (array[i] < array[min_idx]) {
min_idx = i;
}
}
// put min at the correct position
int temp = array[step];
array[step] = array[min_idx];
array[min_idx] = temp;
}
}
// driver code
public static void main(String args[]) {
int[] data = { 20, 12, 10, 15, 2 };
SelectionSort ss = new SelectionSort();
[Link](data);
[Link]("Sorted Array in Ascending Order: ");
[Link]([Link](data));
}
}
THANK YOU