Sorting Algorithms

There are different approaches to sorting an array or numbers in a list.
Each has their own pros

and cons so it is wise to choose according to your requirements.
Bubble sort
Bubble Sort utilizes 2 nested for loops to sort. During the nth pass of the first for loop,
the second for loop iterates through the indexes where the adjacent elements are
swapped if necessary. Thus, the reason why it is called bubble sort is because the way
the elements are swapped. This code is the best code to write for beginners as it is very
simple to write. The Logic can easily be thought of as the programmer writes the
iteration cycles on a sheet of paper.
Example code:
Official code in Geeks For Geek:
// Java program for implementation of Bubble Sort

import java.util.*;
class BubbleSort {
void bubbleSort(int arr[])
{
int n = arr.length;
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1]) {
// swap arr[j+1] and arr[j]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
/* Prints the array */

void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver method to test above

public static void main(String args[])
{
BubbleSort ob = new BubbleSort();
int arr[] = { 5, 1, 4, 2, 8 };
ob.bubbleSort(arr);
System.out.println("Sorted array");
ob.printArray(arr);
}
}
/* This code is contributed by Rajat Mishra */
Selection sort
Selection sort uses 2 nested for loops too. However, Instead of behaving like bubble sort, it
actually compares the number that the 1st for loop points to the numbers above that index.
Thus, Selection sort is very versatile for applications where lots of work is needed. It is only a
pinch complex than bubble sort and its time complexity is always 0(N^2).
Example code:
// Java program for implementation of Selection Sort
import java.io.*;
public class SelectionSort
{
void sort(int arr[])
{
int n = arr.length;
// One by one move boundary of unsorted subarray
for (int i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
int min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first

// element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
// Prints the array

void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
}
// Driver code to test above

public static void main(String args[])
{
SelectionSort ob = new SelectionSort();
int arr[] = {64,25,12,22,11};
ob.sort(arr);
System.out.println("Sorted array");
ob.printArray(arr);
}
}
/* This code is contributed by Rajat Mishra*/
Insertion Sort
Similar to how you insert files between a date when you are sorting time stamped files, insertion
sort works the same. Even though it may seem like bubble sort for how it swaps the indexes of
an array, it is not. It is on the complex side but it can be versatile. In addition, you can either use
a nested for loop or a for and while loop.
Example code:

void sort(int arr[])
{
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
/* Move elements of arr[0..i-1], that are

greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
Quick Sort
Quick sort is quick and versatile especially when lots of work is required. It does rely on a pivot
value to partition the array which can be complicated for some people. Thus, you never begin
with quick sort as your first sorting algorithm. It may even require recursion to work properly.
Example code:
In GFG:
// Java implementation of QuickSort
import java.io.*;
https://www.geeksforgeeks.org/quick-sort/
class GFG {
// A utility function to swap two elements

static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/* This function takes last element as pivot, places

the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
static int partition(int[] arr, int low, int high)
{
// pivot
int pivot = arr[high];
// Index of smaller element and

// indicates the right position
// of pivot found so far
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
// If current element is smaller

// than the pivot
if (arr[j] < pivot) {
// Increment index of
// smaller element
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
/* The main function that implements QuickSort

arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index
*/
static void quickSort(int[] arr, int low, int high)
{
if (low < high) {
// pi is partitioning index, arr[p]

// is now at right place
int pi = partition(arr, low, high);
// Separately sort elements before

// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print an array

static void printArray(int[] arr, int size)
{
for (int i = 0; i < size; i++)
System.out.print(arr[i] + " ");
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 10, 7, 8, 9, 1, 5 };
int n = arr.length;
quickSort(arr, 0, n - 1);
System.out.println("Sorted array: ");
printArray(arr, n);
}
}
// This code is contributed by Ayush Choudhary
Merge Sort
Merge sort is the most complex code. It splits arrays into subarrays which then gets merged
together. In the merge function (or any lines of code that you will use to merge arrays), it
assigns value from subarrays to the main array in an efficient way. As the subarrays itself is
sorted, you can merge by comparing the values of subarrays from the left first to decide how to
insert the elements. When one subarray is completed, you can simply insert elements from the
next element to the rightmost element (--> direction).
https://textbooks.cs.ksu.edu/cc310/7-searching-and-sorting/16-merge-sort-pseudocode/
https://drive.google.com/file/d/1IrJkRFBEw4GU80ukWO4P0Sh7gC-Zu7wn/view?usp=share_link

Sorting Algorithms

Uploaded by

Copyright:

Available Formats

Sorting Algorithms

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Sorting Algorithms

Uploaded by

Copyright:

Available Formats

There are different approaches to sorting an array or numbers in a list.

Each has their own pros

// Java program for implementation of Bubble Sort

/* Prints the array */

// Driver method to test above

// Swap the found minimum element with the first

// Prints the array

// Driver code to test above

Official code in Geeks For Geek:

/* Move elements of arr[0..i-1], that are

// A utility function to swap two elements

/* This function takes last element as pivot, places

// Index of smaller element and

for (int j = low; j <= high - 1; j++) {

// If current element is smaller

/* The main function that implements QuickSort

// pi is partitioning index, arr[p]

// Separately sort elements before

// Function to print an array

// This code is contributed by Ayush Choudhary

You might also like