MAT3514 - Sorting Algorithms Assignment
26/09/2024
24
Min.
Sorting - Tran Ba Tuan - HUS - VNU
I, Intuition
- Students need to understand the mechanism and motivation behind common sorting algorithms such as Bubble Sort, Selection Sort, Insertion Sort, Merge Sort and Quick Sort.
- Have the ability to comprehend pseudo code.
- Knows what Sorting Algorithm to implement depending on certain situations.
II, Practice
Work 1. Write a program to evaluate sorting algorithms:
- a, With a small integer array from keyboard input.
- b, With \(N\) - size integer array in range \([1,10^5]\).
- c, Implement Bubble Sort, Selection Sort, Insertion Sort, Merge Sort and Quick Sort with the requirements above.
- d, Display the state of the array after each iteration to visualize said algorithms. Count comparative operations and swapping operations.
- e, Compare time taken of each algorithms with \(N = [100, 1000, 10000, 100000]\). Conclude the motivation behind choosing suitable sorting algorithms based on use case and the characteristics of the data.
import mysort.*;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Random;
import java.util.Scanner;
public class Work1 {
static Scanner sc = new Scanner(System.in);
static MySortingAlgorithm[] sortingAlgorithms = {new BubbleSort(), new SelectionSort(), new InsertionSort(), new MergeSort(), new QuickSort()};
static Sorter sorter = new Sorter();
public static void evaluateSortingAlgorithms(int[] arr) {
for (MySortingAlgorithm algorithm : sortingAlgorithms) {
int[] arrCopy = Arrays.copyOf(arr, arr.length);
sorter.setSortingAlgorithm(algorithm);
sorter.sort(arrCopy);
}
}
// Small array from keyboard input
public static void evaluateFromKeyboardInput() {
int n = 0;
System.out.println("Enter n for array size:");
while (n <= 0) {
try {
n = sc.nextInt();
if (n <= 0) System.out.println("Please enter a positive integer for n:");
} catch (InputMismatchException e) {
System.out.println("Please enter an integer n for array size n:");
sc.next();
}
}
int[] arr = new int[n];
System.out.println("Enter the elements of " + n + " size array:");
int i = 0;
while (i < n) {
try {
arr[i] = sc.nextInt();
i++;
} catch (InputMismatchException e) {
System.out.println("Invalid element, please add integer(s):");
sc.next();
}
}
System.out.println("Original: " + Arrays.toString(arr));
evaluateSortingAlgorithms(arr);
}
// For N-size array ranging from [1, 10^5]
public static void evaluateNsizeArray(int[] nValues) {
Random random = new Random();
for (int n : nValues) {
System.out.println("Evaluating sorting algorithms for size " + n + " array:\n");
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = random.nextInt((int) Math.pow(10, 5));
}
evaluateSortingAlgorithms(arr);
}
}
public static void main(String[] args) {
evaluateFromKeyboardInput();
int[] nValues = {100, 1000, 10000, 100000};
sorter.setPrintIterations(false);
evaluateNsizeArray(nValues);
}
}
Output:
Enter n for array size:
10
Enter the elements of 10 size array:
5 4 8 7 1 3 9 2 0 -5
Original: [5, 4, 8, 7, 1, 3, 9, 2, 0, -5]
Bubble Sort iteration 1: [4, 5, 7, 1, 3, 8, 2, 0, -5, 9]
Bubble Sort iteration 2: [4, 5, 1, 3, 7, 2, 0, -5, 8, 9]
Bubble Sort iteration 3: [4, 1, 3, 5, 2, 0, -5, 7, 8, 9]
Bubble Sort iteration 4: [1, 3, 4, 2, 0, -5, 5, 7, 8, 9]
Bubble Sort iteration 5: [1, 3, 2, 0, -5, 4, 5, 7, 8, 9]
Bubble Sort iteration 6: [1, 2, 0, -5, 3, 4, 5, 7, 8, 9]
Bubble Sort iteration 7: [1, 0, -5, 2, 3, 4, 5, 7, 8, 9]
Bubble Sort iteration 8: [0, -5, 1, 2, 3, 4, 5, 7, 8, 9]
Bubble Sort iteration 9: [-5, 0, 1, 2, 3, 4, 5, 7, 8, 9]
Bubble Sort: 0ms for 10 element(s)
Movements: 33; Comparisons: 45
Selection Sort iteration 1: [-5, 4, 8, 7, 1, 3, 9, 2, 0, 5]
Selection Sort iteration 2: [-5, 0, 8, 7, 1, 3, 9, 2, 4, 5]
Selection Sort iteration 3: [-5, 0, 1, 7, 8, 3, 9, 2, 4, 5]
Selection Sort iteration 4: [-5, 0, 1, 2, 8, 3, 9, 7, 4, 5]
Selection Sort iteration 5: [-5, 0, 1, 2, 3, 8, 9, 7, 4, 5]
Selection Sort iteration 6: [-5, 0, 1, 2, 3, 4, 9, 7, 8, 5]
Selection Sort iteration 7: [-5, 0, 1, 2, 3, 4, 5, 7, 8, 9]
Selection Sort iteration 8: [-5, 0, 1, 2, 3, 4, 5, 7, 8, 9]
Selection Sort iteration 9: [-5, 0, 1, 2, 3, 4, 5, 7, 8, 9]
Selection Sort: 0ms for 10 element(s)
Movements: 9; Comparisons: 45
Insertion Sort iteration 1: [4, 5, 8, 7, 1, 3, 9, 2, 0, -5]
Insertion Sort iteration 2: [4, 5, 8, 7, 1, 3, 9, 2, 0, -5]
Insertion Sort iteration 3: [4, 5, 7, 8, 1, 3, 9, 2, 0, -5]
Insertion Sort iteration 4: [1, 4, 5, 7, 8, 3, 9, 2, 0, -5]
Insertion Sort iteration 5: [1, 3, 4, 5, 7, 8, 9, 2, 0, -5]
Insertion Sort iteration 6: [1, 3, 4, 5, 7, 8, 9, 2, 0, -5]
Insertion Sort iteration 7: [1, 2, 3, 4, 5, 7, 8, 9, 0, -5]
Insertion Sort iteration 8: [0, 1, 2, 3, 4, 5, 7, 8, 9, -5]
Insertion Sort iteration 9: [-5, 0, 1, 2, 3, 4, 5, 7, 8, 9]
Insertion Sort: 0ms for 10 element(s)
Movements: 33; Comparisons: 33
Merge step: [4, 5, 8, 7, 1, 3, 9, 2, 0, -5]
Merge step: [4, 5, 8, 7, 1, 3, 9, 2, 0, -5]
Merge step: [4, 5, 8, 1, 7, 3, 9, 2, 0, -5]
Merge step: [1, 4, 5, 7, 8, 3, 9, 2, 0, -5]
Merge step: [1, 4, 5, 7, 8, 3, 9, 2, 0, -5]
Merge step: [1, 4, 5, 7, 8, 2, 3, 9, 0, -5]
Merge step: [1, 4, 5, 7, 8, 2, 3, 9, -5, 0]
Merge step: [1, 4, 5, 7, 8, -5, 0, 2, 3, 9]
Merge step: [-5, 0, 1, 2, 3, 4, 5, 7, 8, 9]
Merge Sort: 0ms for 10 element(s)
Movements: 34; Comparisons: 22
Partition step: [-5, 0, 1, 2, 3, 4, 5, 8, 7, 9]
Partition step: [-5, 0, 1, 2, 3, 4, 5, 8, 7, 9]
Partition step: [-5, 0, 1, 2, 3, 4, 5, 8, 7, 9]
Partition step: [-5, 0, 1, 2, 3, 4, 5, 7, 8, 9]
Partition step: [-5, 0, 1, 2, 3, 4, 5, 7, 8, 9]
Partition step: [-5, 0, 1, 2, 3, 4, 5, 7, 8, 9]
Partition step: [-5, 0, 1, 2, 3, 4, 5, 7, 8, 9]
Quick Sort: 0ms for 10 element(s)
Movements: 18; Comparisons: 29
Evaluating sorting algorithms for size 100 array:
Bubble Sort: 0ms for 100 element(s)
Movements: 2474; Comparisons: 4950
Selection Sort: 0ms for 100 element(s)
Movements: 99; Comparisons: 4950
Insertion Sort: 0ms for 100 element(s)
Movements: 2474; Comparisons: 2474
Merge Sort: 0ms for 100 element(s)
Movements: 672; Comparisons: 539
Quick Sort: 0ms for 100 element(s)
Movements: 392; Comparisons: 573
Evaluating sorting algorithms for size 1000 array:
Bubble Sort: 0ms for 1000 element(s)
Movements: 252098; Comparisons: 499500
Selection Sort: 0ms for 1000 element(s)
Movements: 999; Comparisons: 499500
Insertion Sort: 15ms for 1000 element(s)
Movements: 252098; Comparisons: 252098
Merge Sort: 0ms for 1000 element(s)
Movements: 9976; Comparisons: 8725
Quick Sort: 0ms for 1000 element(s)
Movements: 6777; Comparisons: 11240
Evaluating sorting algorithms for size 10000 array:
Bubble Sort: 67ms for 10000 element(s)
Movements: 25045625; Comparisons: 49995000
Selection Sort: 63ms for 10000 element(s)
Movements: 9999; Comparisons: 49995000
Insertion Sort: 15ms for 10000 element(s)
Movements: 25045625; Comparisons: 25045625
Merge Sort: 0ms for 10000 element(s)
Movements: 133616; Comparisons: 120484
Quick Sort: 0ms for 10000 element(s)
Movements: 89372; Comparisons: 161503
Evaluating sorting algorithms for size 100000 array:
Bubble Sort: 11569ms for 100000 element(s)
Movements: 2500400343; Comparisons: 4999950000
Selection Sort: 2188ms for 100000 element(s)
Movements: 99999; Comparisons: 4999950000
Insertion Sort: 1624ms for 100000 element(s)
Movements: 2500400343; Comparisons: 2500400343
Merge Sort: 16ms for 100000 element(s)
Movements: 1668928; Comparisons: 1536358
Quick Sort: 0ms for 100000 element(s)
Movements: 1024666; Comparisons: 1985279
Work 2.
- Generalize on Work 1. with data type
Comparable<T>.
import mygenericsort.*;
import java.util.Arrays;
import java.util.ArrayList;
public class Work2 {
public static class Student implements Comparable<Student>{
String name;
int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(Student o) {
return Integer.compare(this.age, o.age);
}
@Override
public String toString() {
return "[" + name + "; age: " + age + "]";
}
public static void printStudents(Student[] students) {
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < students.length; i++) {
sb.append(students[i]).append(i == students.length - 1 ? "]" : ", ");
}
System.out.println(sb);
}
}
static ArrayList<MySortingAlgorithm<Student>> sortingAlgorithms = new ArrayList<>();
static Sorter<Student> sorter = new Sorter<>();
public static void evaluateSortingAlgorithms(Student[] arr) {
for (MySortingAlgorithm<Student> algorithm : sortingAlgorithms) {
Student[] arrCopy = Arrays.copyOf(arr, arr.length);
sorter.setSortingAlgorithm(algorithm);
sorter.sort(arrCopy);
}
}
public static void main(String[] args) {
String[] names = {"Kisaki", "Ibuki", "Hare", "Hina", "Arona", "Plana", "Iroha"};
int[] ages = {17, 11, 16, 17, 12, 13, 16};
Student[] students = new Student[names.length];
for (int i = 0; i < names.length; i++) {
students[i] = new Student(names[i], ages[i]);
}
MySortingAlgorithm<Student> bubbleSort = new BubbleSort<>();
MySortingAlgorithm<Student> selectionSort = new SelectionSort<>();
MySortingAlgorithm<Student> insertionSort = new InsertionSort<>();
MySortingAlgorithm<Student> mergeSort = new MergeSort<>();
MySortingAlgorithm<Student> quickSort = new QuickSort<>();
sortingAlgorithms.add(bubbleSort);
sortingAlgorithms.add(selectionSort);
sortingAlgorithms.add(insertionSort);
sortingAlgorithms.add(mergeSort);
sortingAlgorithms.add(quickSort);
System.out.println("Original list:");
Student.printStudents(students);
evaluateSortingAlgorithms(students);
}
}
Output:
Original list:
[[Kisaki; age: 17], [Ibuki; age: 11], [Hare; age: 16], [Hina; age: 17], [Arona; age: 12], [Plana; age: 13], [Iroha; age: 16]]
Bubble Sort iteration 1: [[Ibuki; age: 11], [Hare; age: 16], [Kisaki; age: 17], [Arona; age: 12], [Plana; age: 13], [Iroha; age: 16], [Hina; age: 17]]
Bubble Sort iteration 2: [[Ibuki; age: 11], [Hare; age: 16], [Arona; age: 12], [Plana; age: 13], [Iroha; age: 16], [Kisaki; age: 17], [Hina; age: 17]]
Bubble Sort iteration 3: [[Ibuki; age: 11], [Arona; age: 12], [Plana; age: 13], [Hare; age: 16], [Iroha; age: 16], [Kisaki; age: 17], [Hina; age: 17]]
Bubble Sort iteration 4: [[Ibuki; age: 11], [Arona; age: 12], [Plana; age: 13], [Hare; age: 16], [Iroha; age: 16], [Kisaki; age: 17], [Hina; age: 17]]
Bubble Sort iteration 5: [[Ibuki; age: 11], [Arona; age: 12], [Plana; age: 13], [Hare; age: 16], [Iroha; age: 16], [Kisaki; age: 17], [Hina; age: 17]]
Bubble Sort iteration 6: [[Ibuki; age: 11], [Arona; age: 12], [Plana; age: 13], [Hare; age: 16], [Iroha; age: 16], [Kisaki; age: 17], [Hina; age: 17]]
Bubble Sort: 0ms for 7 element(s)
Movements: 10; Comparisons: 21
Selection Sort iteration 1: [[Ibuki; age: 11], [Kisaki; age: 17], [Hare; age: 16], [Hina; age: 17], [Arona; age: 12], [Plana; age: 13], [Iroha; age: 16]]
Selection Sort iteration 2: [[Ibuki; age: 11], [Arona; age: 12], [Hare; age: 16], [Hina; age: 17], [Kisaki; age: 17], [Plana; age: 13], [Iroha; age: 16]]
Selection Sort iteration 3: [[Ibuki; age: 11], [Arona; age: 12], [Plana; age: 13], [Hina; age: 17], [Kisaki; age: 17], [Hare; age: 16], [Iroha; age: 16]]
Selection Sort iteration 4: [[Ibuki; age: 11], [Arona; age: 12], [Plana; age: 13], [Hare; age: 16], [Kisaki; age: 17], [Hina; age: 17], [Iroha; age: 16]]
Selection Sort iteration 5: [[Ibuki; age: 11], [Arona; age: 12], [Plana; age: 13], [Hare; age: 16], [Iroha; age: 16], [Hina; age: 17], [Kisaki; age: 17]]
Selection Sort iteration 6: [[Ibuki; age: 11], [Arona; age: 12], [Plana; age: 13], [Hare; age: 16], [Iroha; age: 16], [Hina; age: 17], [Kisaki; age: 17]]
Selection Sort: 0ms for 7 element(s)
Movements: 6; Comparisons: 21
Insertion Sort iteration 1: [[Ibuki; age: 11], [Kisaki; age: 17], [Hare; age: 16], [Hina; age: 17], [Arona; age: 12], [Plana; age: 13], [Iroha; age: 16]]
Insertion Sort iteration 2: [[Ibuki; age: 11], [Hare; age: 16], [Kisaki; age: 17], [Hina; age: 17], [Arona; age: 12], [Plana; age: 13], [Iroha; age: 16]]
Insertion Sort iteration 3: [[Ibuki; age: 11], [Hare; age: 16], [Kisaki; age: 17], [Hina; age: 17], [Arona; age: 12], [Plana; age: 13], [Iroha; age: 16]]
Insertion Sort iteration 4: [[Ibuki; age: 11], [Arona; age: 12], [Hare; age: 16], [Kisaki; age: 17], [Hina; age: 17], [Plana; age: 13], [Iroha; age: 16]]
Insertion Sort iteration 5: [[Ibuki; age: 11], [Arona; age: 12], [Plana; age: 13], [Hare; age: 16], [Kisaki; age: 17], [Hina; age: 17], [Iroha; age: 16]]
Insertion Sort iteration 6: [[Ibuki; age: 11], [Arona; age: 12], [Plana; age: 13], [Hare; age: 16], [Iroha; age: 16], [Kisaki; age: 17], [Hina; age: 17]]
Insertion Sort: 0ms for 7 element(s)
Movements: 10; Comparisons: 10
Merge step: [[Ibuki; age: 11], [Kisaki; age: 17], [Hare; age: 16], [Hina; age: 17], [Arona; age: 12], [Plana; age: 13], [Iroha; age: 16]]
Merge step: [[Ibuki; age: 11], [Kisaki; age: 17], [Hare; age: 16], [Hina; age: 17], [Arona; age: 12], [Plana; age: 13], [Iroha; age: 16]]
Merge step: [[Ibuki; age: 11], [Hare; age: 16], [Kisaki; age: 17], [Hina; age: 17], [Arona; age: 12], [Plana; age: 13], [Iroha; age: 16]]
Merge step: [[Ibuki; age: 11], [Hare; age: 16], [Kisaki; age: 17], [Hina; age: 17], [Arona; age: 12], [Plana; age: 13], [Iroha; age: 16]]
Merge step: [[Ibuki; age: 11], [Hare; age: 16], [Kisaki; age: 17], [Hina; age: 17], [Arona; age: 12], [Plana; age: 13], [Iroha; age: 16]]
Merge step: [[Ibuki; age: 11], [Arona; age: 12], [Plana; age: 13], [Hare; age: 16], [Iroha; age: 16], [Kisaki; age: 17], [Hina; age: 17]]
Merge Sort: 0ms for 7 element(s)
Movements: 20; Comparisons: 13
Partition step: [[Ibuki; age: 11], [Arona; age: 12], [Plana; age: 13], [Iroha; age: 16], [Kisaki; age: 17], [Hare; age: 16], [Hina; age: 17]]
Partition step: [[Ibuki; age: 11], [Arona; age: 12], [Plana; age: 13], [Iroha; age: 16], [Kisaki; age: 17], [Hare; age: 16], [Hina; age: 17]]
Partition step: [[Ibuki; age: 11], [Arona; age: 12], [Plana; age: 13], [Iroha; age: 16], [Hare; age: 16], [Hina; age: 17], [Kisaki; age: 17]]
Partition step: [[Ibuki; age: 11], [Arona; age: 12], [Plana; age: 13], [Iroha; age: 16], [Hare; age: 16], [Hina; age: 17], [Kisaki; age: 17]]
Quick Sort: 0ms for 7 element(s)
Movements: 11; Comparisons: 11
Work 3.
- a, Design object
Cardwith 2 fields:rankandsuit. Initialize a deck with 52 cards. - b, Create instance object
comparecardwhich implementsComparator<Card>. Use the methodsort(T[] a, Comparator<? super T> c)in packageArraysof Java to sort the deck. - c, Configure the
Comparableinterface forCard, use methods in Work 2. to sort the deck.
import mygenericsort.*;
import java.util.*;
public class Work3 {
public static class Card implements Comparable<Card> {
char suit;
char rank;
public Card(int rank, int suit) {
initSuitAndRank(rank, suit);
}
private void initSuitAndRank(int rank, int suit) {
if (rank >= 2 && rank < 10) {
this.rank = Character.forDigit(rank, 10);
} else {
switch (rank) {
case 1:
this.rank = 'A'; // Ace
break;
case 10:
this.rank = '1'; // 10
break;
case 11:
this.rank = 'J'; // Jack
break;
case 12:
this.rank = 'Q'; // Queen
break;
case 13:
this.rank = 'K'; // King
break;
default:
throw new IllegalArgumentException("Invalid rank value: " + rank);
}
}
switch (suit) {
case 1:
this.suit = '♠'; // Spades
break;
case 2:
this.suit = '♡'; // Hearts
break;
case 3:
this.suit = '♢'; // Diamonds
break;
case 4:
this.suit = '♣'; // Clubs
break;
default:
throw new IllegalArgumentException("Invalid suit value: " + suit);
}
}
private int getRankValue() {
return switch (rank) {
case 'A' -> 1;
case '1' -> 10;
case 'J' -> 11;
case 'Q' -> 12;
case 'K' -> 13;
default -> rank - '0';
};
}
public static Card[] getDeck() {
Card[] deck = new Card[52];
// Suits: 1 to 4 (♠, ♥, ♦, ♣)
int index = 0;
for (int suit = 1; suit <= 4; suit++) {
// Ranks: 1 (Ace), 2-10, 11 (Jack), 12 (Queen), 13 (King)
for (int rank = 1; rank <= 13; rank++) {
deck[index++] = new Card(rank, suit);
}
}
return deck;
}
public static void shuffleDeck(Card[] deck) {
Random random = new Random();
for (int i = deck.length - 1; i > 0; i--) {
int j = random.nextInt(i + 1);
Card temp = deck[i];
deck[i] = deck[j];
deck[j] = temp;
}
}
public static void printDeck(Card[] deck) {
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < deck.length; i++) {
sb.append(deck[i]).append(i == deck.length - 1 ? "]" : ", ");
}
System.out.println(sb);
}
@Override
public int compareTo(Card o) {
if (this.suit == o.suit) {
return Integer.compare(this.getRankValue(), o.getRankValue());
} else return Integer.compare(this.suit, o.suit);
}
@Override
public String toString() {
String rankString;
if (rank == 'A' || rank == 'J' || rank == 'Q' || rank == 'K') {
rankString = String.valueOf(rank);
} else if (rank == '1') {
rankString = "10";
} else {
rankString = String.valueOf(rank);
}
return rankString + suit;
}
}
public static class CardComparator implements Comparator<Card> {
@Override
public int compare(Card o1, Card o2) {
return o1.compareTo(o2);
}
}
public static void evaluateSortingAlgorithms(Card[] deck, Sorter<Card> sorter, ArrayList<MySortingAlgorithm<Card>> sortingAlgorithms) {
for (MySortingAlgorithm<Card> algorithm : sortingAlgorithms) {
Card[] deckCopy = Arrays.copyOf(deck, deck.length);
sorter.setSortingAlgorithm(algorithm);
sorter.sort(deckCopy);
}
}
public static void main(String[] args) {
Card[] deck = Card.getDeck();
System.out.println("Standard 52 cards deck:");
Card.printDeck(deck);
System.out.println("Shuffled 52 cards deck:");
Card.shuffleDeck(deck);
Card.printDeck(deck);
CardComparator comparecard = new CardComparator();
// Using sort from package Arrays
Card[] sortedDeck = Arrays.copyOf(deck, deck.length);
Arrays.sort(sortedDeck, comparecard);
System.out.println("Sorted 52 cards deck:");
Card.printDeck(sortedDeck);
// Using methods from Work 2.
System.out.println("\nEvaluating sorting card deck with 5 sorting algorithms:");
ArrayList<MySortingAlgorithm<Card>> sortingAlgorithms = new ArrayList<>();
MySortingAlgorithm<Card> bubbleSort = new BubbleSort<>();
MySortingAlgorithm<Card> selectionSort = new SelectionSort<>();
MySortingAlgorithm<Card> insertionSort = new InsertionSort<>();
MySortingAlgorithm<Card> mergeSort = new MergeSort<>();
MySortingAlgorithm<Card> quickSort = new QuickSort<>();
sortingAlgorithms.add(bubbleSort);
sortingAlgorithms.add(selectionSort);
sortingAlgorithms.add(insertionSort);
sortingAlgorithms.add(mergeSort);
sortingAlgorithms.add(quickSort);
Sorter<Card> sorter = new Sorter<>();
sorter.setPrintIterations(false);
evaluateSortingAlgorithms(deck, sorter, sortingAlgorithms);
}
}
Output:
Standard 52 cards deck:
[A♠, 2♠, 3♠, 4♠, 5♠, 6♠, 7♠, 8♠, 9♠, 10♠, J♠, Q♠, K♠, A♡, 2♡, 3♡, 4♡, 5♡, 6♡, 7♡, 8♡, 9♡, 10♡, J♡, Q♡, K♡, A♢, 2♢, 3♢, 4♢, 5♢, 6♢, 7♢, 8♢, 9♢, 10♢, J♢, Q♢, K♢, A♣, 2♣, 3♣, 4♣, 5♣, 6♣, 7♣, 8♣, 9♣, 10♣, J♣, Q♣, K♣]
Shuffled 52 cards deck:
[10♢, 9♠, Q♡, A♣, 3♣, 4♢, 7♢, J♡, J♠, 3♠, 5♡, 8♡, 6♢, 9♣, A♡, J♣, A♢, 7♣, 5♠, 4♠, K♢, 5♣, 7♡, 5♢, 2♡, 8♣, 6♣, 2♣, 8♠, 7♠, 3♡, 10♣, 2♠, 6♠, 6♡, Q♠, K♡, 10♠, Q♢, 4♡, 2♢, 9♢, 8♢, A♠, K♠, 9♡, 4♣, 3♢, K♣, 10♡, Q♣, J♢]
Sorted 52 cards deck:
[A♠, 2♠, 3♠, 4♠, 5♠, 6♠, 7♠, 8♠, 9♠, 10♠, J♠, Q♠, K♠, A♡, 2♡, 3♡, 4♡, 5♡, 6♡, 7♡, 8♡, 9♡, 10♡, J♡, Q♡, K♡, A♢, 2♢, 3♢, 4♢, 5♢, 6♢, 7♢, 8♢, 9♢, 10♢, J♢, Q♢, K♢, A♣, 2♣, 3♣, 4♣, 5♣, 6♣, 7♣, 8♣, 9♣, 10♣, J♣, Q♣, K♣]
Evaluating sorting card deck with 5 sorting algorithms:
Bubble Sort: 0ms for 52 element(s)
Movements: 644; Comparisons: 1326
Selection Sort: 0ms for 52 element(s)
Movements: 51; Comparisons: 1326
Insertion Sort: 0ms for 52 element(s)
Movements: 644; Comparisons: 644
Merge Sort: 1ms for 52 element(s)
Movements: 300; Comparisons: 224
Quick Sort: 0ms for 52 element(s)
Movements: 187; Comparisons: 254
Work 4. Students are required to solve at least 4 problems on Sorting Algorithms at: codelearn.io.
Note: For this site, if you want to use Java then you’ll have to add the class, the main method to handle input and everything, its not like on LeetCode where you just need to finish the method. Example:
import java.util.*;
public class InsertionSort {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
System.out.println(insertionSort(arr));
}
public static String insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
return Arrays.toString(arr).replaceAll(",", "").replaceAll("\\[", "").replaceAll("]", " ");
}
}
Bubble Sort:
public static String 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]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return Arrays.toString(arr).replaceAll(",", "").replaceAll("\\[", "").replaceAll("]", " ");
}
Selection Sort:
public static String selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
return Arrays.toString(arr).replaceAll(",", "").replaceAll("\\[", "").replaceAll("]", " ");
}
Insertion Sort:
public static String insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
return Arrays.toString(arr).replaceAll(",", "").replaceAll("\\[", "").replaceAll("]", " ");
}
Merge Sort:
public static String mergeSort(int[] arr) {
mergeSort(arr, 0, arr.length - 1);
return Arrays.toString(arr).replaceAll(",", "").replaceAll("\\[", "").replaceAll("]", " ");
}
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];
System.arraycopy(arr, left, leftArray, 0, n1);
for (int j = 0; j < n2; ++j) {
rightArray[j] = arr[mid + 1 + j];
}
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++;
} else {
arr[k] = rightArray[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = leftArray[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArray[j];
j++;
k++;
}
}
Quick Sort:
public static String quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
return Arrays.toString(arr).replaceAll(",", "").replaceAll("\\[", "").replaceAll("]", " ");
}
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
private static 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;
}
Shell Sort:
public static String shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int key = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > key) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = key;
}
}
return Arrays.toString(arr).replaceAll(",", "").replaceAll("\\[", "").replaceAll("]", " ");
}
Find Smallest Int Not Present:
- Given n-size integer array, find the smallest integer that is not present in the array.
- Example: Input:
[1, 2, 3, 5], Output:4.
1) Sorting approach
public static int smallestMissingInt(int[] arr) {
// Use sorting algorithm of your choice
Arrays.sort(arr);
int smallestMissing = 0;
for (int num : arr) {
if (num < 0) {
continue;
}
if (num == smallestMissing) {
smallestMissing++;
}
}
return smallestMissing;
}
2) HashSet approach
public static int smallestMissingInt(int[] arr) {
// Use sorting algorithm of your choice, preferably O(nlogn)
HashSet<Integer> set = new HashSet<>();
for (int num : arr) {
set.add(num);
}
int smallestMissing = 0;
while (set.contains(smallestMissing)) {
smallestMissing++;
}
return smallestMissing;
}
Minimal Informants:
- Given n-size integer array and range k, find the minimal number of elements that can reach all other element within range k with given distance formula:
|a[i] - a[j]|. - Example: Input:
a = [1, 3, 2, 5, 10, 8], k = 2, Output:2.
public static int minInitialInformants(int[] a, int k) {
// Use sorting algorithm of your choice, preferably O(nlogn)
Arrays.sort(a);
int count = 0;
for (int i = 1; i < a.length; i++){
if (a[i] - a[i-1] > k){
count ++;
}
}
return count + 1;
}
Ascending Squares:
- Given n-size integer array, print out all unique perfect squares in ascending order, if none then output
NULL. - Example: Input:
[16, 1, 2, 1, 10, 8], Output:1 16.
1) Sorting and HashSet approach
public static String findPerfectSquares(int[] arr) {
Set<Integer> perfectSquares = new HashSet<>();
for (int num : arr) {
if (num >= 0) {
int sqrt = (int) Math.sqrt(num);
if (sqrt * sqrt == num) {
perfectSquares.add(num);
}
}
}
if (perfectSquares.isEmpty()) {
return "NULL";
} else {
List<Integer> sortedPerfectSquares = new ArrayList<>(perfectSquares);
Collections.sort(sortedPerfectSquares); // Sorting happens here
StringBuilder result = new StringBuilder();
for (int square : sortedPerfectSquares) {
result.append(square).append(" ");
}
return result.toString().replaceAll(",", "").replaceAll("\\[", "").replaceAll("]", " ");
}
}
2) TreeSet approach
public static String findAscendingPerfectSquares(int[] arr) {
Set<Integer> perfectSquares = new TreeSet<>();
for (int num : arr) {
if (num >= 0) {
int sqrt = (int) Math.sqrt(num);
if (sqrt * sqrt == num) {
perfectSquares.add(num);
}
}
}
if (perfectSquares.isEmpty()) {
return "NULL";
} else {
StringBuilder result = new StringBuilder();
for (int square : perfectSquares) {
result.append(square).append(" ");
}
return result.toString().replaceAll(",", "").replaceAll("\\[", "").replaceAll("]", " ");
}
}
Frequencies:
1) Sorting approach
public static String countFrequencies(int[] arr) {
// Use sorting algorithm of your choice, preferably O(nlogn)
Arrays.sort(arr);
StringBuilder result = new StringBuilder();
for (int i = 0; i < arr.length; ) {
int count = 0;
int currentNumber = arr[i];
while (i < arr.length && arr[i] == currentNumber) {
count++;
i++;
}
result.append(currentNumber).append(" ").append(count).append("; ");
}
return result.toString().replaceAll(",", "").replaceAll("\\[", "").replaceAll("]", " ");
}
2) HashMap approach
public static String countFrequencies(int[] arr) {
Map<Integer, Integer> frequencyMap = new HashMap<>();
for (int num : arr) {
frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
Integer[] uniqueNumbers = frequencyMap.keySet().toArray(new Integer[0]);
Arrays.sort(uniqueNumbers);
StringBuilder result = new StringBuilder();
for (int key : uniqueNumbers) {
result.append(key).append(" ").append(frequencyMap.get(key)).append("; ");
}
return result.toString().replaceAll(",", "").replaceAll("\\[", "").replaceAll("]", " ");
}
Positive Up, Negative Down:
- Given n-size integer array, if present then the position of 0 remains unchanged.
- Sort elements that are < 0 in descending order and elements that are > 0 in ascending order.
public static String positiveUpNegativeDown(int[] arr) {
List<Integer> negativeNumbers = new ArrayList<>();
List<Integer> positiveNumbers = new ArrayList<>();
for (int num : arr) {
if (num < 0) {
negativeNumbers.add(num);
} else if (num > 0) {
positiveNumbers.add(num);
}
}
Collections.sort(negativeNumbers, Collections.reverseOrder());
Collections.sort(positiveNumbers);
StringBuilder result = new StringBuilder();
int negIndex = 0, posIndex = 0;
for (int num : arr) {
if (num == 0) {
result.append("0 ");
} else if (num < 0) {
result.append(negativeNumbers.get(negIndex++)).append(" ");
} else {
result.append(positiveNumbers.get(posIndex++)).append(" ");
}
}
return result.toString().replaceAll(",", "").replaceAll("\\[", "").replaceAll("]", " ");
}
Work 5.
- Solve ascending sort: Ascending sort.
- Solve descending sort: Descending sort.
Work 6.
- K-smallest element: K-smallest element.
- K-largest element: K-largest element.
public static int findKthSmallest(int[] arr, int k) {
Arrays.sort(arr);
return arr[k - 1];
}
public static int findKthLargest(Integer[] arr, int k) {
Arrays.sort(arr, Collections.reverseOrder());
return arr[k - 1];
}
Work 7.
- Pair sum: Pair sum.
- Given n-size array, target x, print out all the possible pair of integers that sums up to x.
- Example: Input:
a = [1 2 4 3 4 5 3], x = 7, Output:4
public static int findPairs(int[] arr, int target) {
List<int[]> pairs = new ArrayList<>();
Map<Integer, Integer> complementMap = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
int complement = target - arr[i];
if (complementMap.containsKey(complement)) {
pairs.add(new int[]{complement, arr[i]});
}
complementMap.put(arr[i], i);
}
return pairs.size();
}
Work 8. String sorting
- Sort the digits in a given string in ascending order.
- Given the small range of digit values, choose an appropriate sorting algorithm.
- Iterate through the string to count the frequency of each digit.
- Use the frequency counts to construct the sorted string.
Work 9.
- Find new pos: Find new pos.
- Given n-size array, position of x as i, find the position of x after ascending sort.
- Example:
a = [8, 1, 7, 2], i = 1, so x = 8, Output:4;
public static int findNewPosition(int[] arr, int i) {
int x = arr[i];
int[] sortedArr = arr.clone();
Arrays.sort(sortedArr);
return binarySearch(sortedArr, x);
}
private static int binarySearch(int[] sortedArr, int x) {
int left = 0;
int right = sortedArr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (sortedArr[mid] == x) {
return mid + 1;
} else if (sortedArr[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}