Sorting Algorithms

College of Computer Engineering

Requirements
for the
Performance Innovative Task BSCPE-2C

Submitted by:
Christian M. Salvaña

October 2021
Selection Sort

Description:
The Selection Sort algorithm is a very simple sorting
algorithm. The algorithm is used to sort a sequence of
numbers and it works by using a linear search to locate the
smallest value out of the bunch. When the smallest value is
detected, that value is then switched with the leftmost
number and is considered sorted. The same process is
repeated until all of the numbers are fully sorted.

Pseudocode:
pseudocode selection sort
list : array of items
n : size of list

for i = 1 to n - 1
/* set current element as minimum*/
min = i

/* check the element to be minimum */

for j = i+1 to n
if list[j] < list[min] then
min = j;
end if
end for

/* swap the minimum element with the current element*/

if indexMin != i then
swap list[min] and list[i]
end if
end for

end procedure
Implementation:
class SelectionSortImplementation
{
void sort(int arr[])
{
int n = arr.length;
for (int i = 0; i < n-1; i++)
{
int min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
} public static void main(String args[])
{
SelectionSortImplementation ob = new
SelectionSortImplementation();
int arr[] = {64,25,12,22,11};
ob.sort(arr);
System.out.println("Sorted array: ");
ob.printArray(arr);
}
}
Bubble Sort

Description:
The Bubble Sort algorithm is one of the simplest and noob
friendly sorting algorithms out of the bunch. The algorithm is
used to sort a sequence of numbers and it works by starting at
the right end of the sequence with essentially a scale and
compares numbers on the left and right sides of the scale. If the
number on the right is smaller than the one on the left, the
numbers get swapped. The scale moves one index to the left and
repeats the same steps. When the scale reaches the left end of
the array, it will move back to the right end and repeat the
whole process again until the sequence of numbers is considered
sorted.

Pseudocode:
procedure bubbleSort( list : array of items )

loop = list.count;

for i = 0 to loop-1 do:

swapped = false

for j = 0 to loop-1 do:

/* compare the adjacent elements */

if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true
end if

end for

/*if no number was swapped that means

array is sorted now, break the loop.*/

if(not swapped) then

break
end if

end for

end procedure return list

Implementation:
public class BubbleSortImplementation {
static void bubbleSort(int[] arr) {
int n = arr.length;
int temp = 0;
for(int i=0; i < n; i++){
for(int j=1; j < (n-i); j++){
if(arr[j-1] > arr[j]){
//swap elements
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}
public static void main(String[] args) {
int arr[] ={3,60,35,2,45,320,5};

System.out.println();

bubbleSort(arr);

System.out.println("Bubble Sort: ");

for(int i=0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}

}
}
Insertion Sort

Description:
Insertion Sort is an algorithm that adds one item at a time to
the sorted part of the list. You start with an unsorted list. You
can say the first item is sorted, since it's just one item. So
you have a sorted list on the left, and the unsorted items on the
right. You take the next unsorted item and compare it to each
item of the sorted list, starting from the last one, and stopping
when you find a smaller item (or when you're at the beginning of
the list). You insert the new item right after that smaller item
(or at the beginning of the list). This guarantees that the new
item is in the right place. Now your sorted list is one item
longer, and there's one less unsorted item. Repeat the previous
step with the next unsorted item. Eventually, you don't have any
more unsorted items and the list is sorted.

Pseudocode:
for i=1 to n-1 {
int current = A[i];
j = i ;

// insertion and comparison

while(j> 0) and A[j-1] > current{

swap(A[j-1], A[j]);

j = j -1;

}
Implementation:
import java.util.Arrays;

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

int[] unsorted = { 32, 23, 45, 87, 92, 31, 19 };

insertionSort(unsorted);

System.out.println("Insertion Sort: " +

Arrays.toString(unsorted));
}

public static void insertionSort(int[] unsorted) {

for (int i = 1; i < unsorted.length; i++) {
int current = unsorted[i];
int j = i;

while (j > 0 && unsorted[j - 1] > current) {

unsorted[j] = unsorted[j - 1];

j--;
}

unsorted[j] = current;
}
}
}
Merge Sort

Description:
Merge sort is very much efficient than the simple sorting
algorithms like the bubble sort, selection sort, and
insertion sort. the only drawback is that it requires an
additional array along with the input array that is sorted.
Merge sort is usually working on the concept of merging two
sorted arrays to create another array which is also sorted.

Pseudocode:
PROCEDURE function mergeSort
   FOR each element of the master list indexed by i
 
       if ( i <= 1 ) return a
 
       var left = a[0] to a[i/2]
       var right = a[i/2+1] to a[i]
 
       left = mergeSort( left )
       right = mergeSort( right )
 
       return merge( left,right )
 
   END FOR
END PROCEDURE
 
PROCEDURE function mergeSort
    WHILE length(left) > 0 and length(right) > 0
        if first(left) ≤ first(right)
            append first(left) to result
            left = rest(left)
        else
            append first(right) to result
            right = rest(right)
 
    IF length(left) > 0
        append left to result
    END IF
 
    IF length(right) > 0
        append right to result
    END IF
 
    return result
END PROCEDURE
Implementation:
public class MergeSortImplementation {
public static void main(String[] args) {
int[] inputArr = {54,26,93,17,77,31,44,55};

mergeSort(inputArr, 0, inputArr.length-1);

System.out.println("Merge Sort:");

for(int element : inputArr){

System.out.print(element + " ");
}
}

private static void mergeSort(int[] intArr, int start, int end)

{

if (start == end){
return;
}else{

int middle = (start + end)/2;

mergeSort(intArr, start, middle);

mergeSort(intArr, middle+1, end);

mergeSubArrays(intArr, start, middle, end);

}
}

private static void mergeSubArrays(int[] arr, int start, int

middle, int end){
int subArrayFirstLength = middle - start + 1;
int subArraySecondLength = end - middle;
int[] temp1 = new int[subArrayFirstLength];
int[] temp2 = new int[subArraySecondLength];
for(int i = 0; i < subArrayFirstLength; i++){
temp1[i] = arr[start + i];
 }
for(int j = 0; j < subArraySecondLength; j++){
temp2[j] = arr[middle + 1 + j];
}
int i =0;
int j = 0;
while((i < subArrayFirstLength) && (j <
subArraySecondLength)){
if(temp1[i] < temp2[j]){
arr[start] = temp1[i++];
}else{
arr[start] = temp2[j++];
}
start++;
}
while(i < subArrayFirstLength){
arr[start++] = temp1[i++];
}
while(j < subArraySecondLength){
arr[start++] = temp2[j++];
}
}
}
Quick Sort

Description:
Quick sort is one of the most famous sorting algorithms
based on divide and conquers strategy which results in an
O(n log n) complexity. So, the algorithm starts by picking a
single item which is called pivot and moving all smaller
items before it, while all greater elements in the later
portion of the list. This is the main quick sort operation
named as a partition, recursively repeated on lesser and
greater sublists until their size is one or zero - in which
case the list is wholly sorted.

Pseudocode:
procedure quickSort(left, right)

if right-left <= 0
return
else
pivot = A[right]
partition = partitionFunc(left, right, pivot)
quickSort(left,partition-1)
quickSort(partition+1,right)
end if

end procedure
Implementation:

class QuickSortImplementation
{

int partition(int arr[], int low, int high)

{
int pivot = arr[high];
int i = (low-1);
for (int j=low; j< high; j++)
{

if (arr[j] <= pivot)

{
i++;

int temp = arr[i];

arr[i] = arr[j];
arr[j] = temp;
}
}

int temp = arr[i+1];

arr[i+1] = arr[high];
arr[high] = temp;

return i+1;
}

void sort(int arr[], int low, int high)

{
if (low < high)
{
 int pi = partition(arr, low, high);

sort(arr, low, pi-1);

sort(arr, pi+1, high);
}
}

static void printArray(int arr[])

{
int n = arr.length;
for (int i=0; i< n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}

public static void main(String args[])

{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = arr.length;

QuickSortImplementation ob = new QuickSortImplementation();

ob.sort(arr, 0, n-1);

System.out.println("Quick Sort: ");

printArray(arr);
}
}