forked from JCarlosR/Sorting-Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathInsertionOpt.java
More file actions
121 lines (107 loc) · 3.04 KB
/
InsertionOpt.java
File metadata and controls
121 lines (107 loc) · 3.04 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
/**
* this is the Optimized insertion sort.
* Sorts a sequence of standard input using an optimized
* version of insertion sort that uses half exchanges instead of
* full exchanges to reduce data movement.
*/
import java.util.Scanner;
/**
* Class for insertion x.
*/
public class InsertionOpt {
/**
* Constructs the object.
*/
private InsertionOpt() {
//unused Constructor.
}
/**
* The given array is arranged ihn ascending order.
* Time complexity of this function is O(N)
*
* @param a This is the Array that is to be sorted.
*/
public static void sort(Comparable[] a) {
int n = a.length;
/**
* the smallest element is choosen so that it acts as the Guard and
* makes sure the index doesnt go beyond.
*/
int exchanges = 0;
for (int i = n - 1; i > 0; i--) {
if (less(a[i], a[i - 1])) {
swap(a, i, i - 1);
exchanges++;
}
}
if (exchanges == 0) return;
/**
* the insertion sort is done with half number of exchanges.
*/
for (int i = 2; i < n; i++) {
Comparable v = a[i];
int j = i;
while (less(v, a[j - 1])) {
a[j] = a[j - 1];
j--;
}
a[j] = v;
}
assert isSorted(a);
}
/**
* this is the helper funciton for the code.
*
* @param v object 1 to be compared.
* @param w object 2 to be compared.
*
* @return returns true if v is smaller to w
* and false if v is greater to w.
*/
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
/**
* This function is used to swap two elements.
*
*
* @param a Object array
* @param i index of element1.
* @param j index of element2.
*/
private static void swap(Object[] a, int i, int j) {
Object swp = a[i];
a[i] = a[j];
a[j] = swp;
}
/**
* this function is used to check if the Array is Sorted or not.
*
*
* @param a this is the array that we need to check
* whether the array is sorted or not
*
* @return True if sorted, False otherwise.
*/
private static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i - 1])) return false;
return true;
}
/**
* this is to print the Array.
*
* @param a this is the array that we wish to print.
*/
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String[] a = scan.nextLine().split(" ");
InsertionOpt.sort(a);
show(a);
}
}