The Array class sort is really good, isn't it?
It sorts in ascending order without permission, and even in descending order.
However, I was afraid that I would get stuck if I didn't know the essence of sorting. How to not use the sort method.
public class Change {
public static void main(String[] args) {
ListManager data = new ListManager();
for (int i = 1; i < 100; i++) {
/*
The following values are returned depending on the value passed to signum.
If the argument is greater than zero ⇒ 1
When the argument is zero ⇒ 0
If the argument is less than zero ⇒-1
*/
int num1 = data.compare(i - 1, i);
switch (num1) {
case 1:
//Swap
data.exchange(i - 1, i);
//Replace from behind
for (int n = i; n > 0; n--) {
int num2 = data.compare(n - 1, n);
switch (num2) {
case 1:
data.exchange(n - 1, n);
default:
break;
}
}
default:
break;
}
}
data.checkResult();
}
}
public class ListManager {
private int[] dataList;
private int compareCount;
private int exchangeCount;
public ListManager() {
//Randomly create data
Random random = new Random();
dataList = new int[100];
for (int i = 0; i < dataList.length; i++) {
dataList[i] = random.nextInt(10000);
}
}
/**
*Compare two data
*
* @param index1
* @param index2
* @return -1:The data of index1 is small, 1:index2 data is small, 0:Same data
*/
public int compare(int index1, int index2) {
compareCount++;
return (int) Math.signum(dataList[index1] - dataList[index2]);
}
/**
*Swap two data
*
* @param index1
* @param index2
*/
public void exchange(int index1, int index2) {
exchangeCount++;
int tmp = dataList[index1];
dataList[index1] = dataList[index2];
dataList[index2] = tmp;
}
/**
*Sort check
*/
public void checkResult() {
int data = dataList[0];
for (int i = 1; i < dataList.length; i++) {
if (data > dataList[i]) {
throw new RuntimeException("Not sorted: [" + (i - 1) + "]=" + data + ", [" + i + "]=" + dataList[i]);
}
data = dataList[i];
}
System.out.println("Sort OK:Comparison=" + compareCount + ",Swap=" + exchangeCount);
}
I feel like I'm writing some useless code, so I'll fix it as soon as I understand it.
If the replacement does not occur on the first switch, it will be confirmed that the index is sorted correctly in ascending order before the index you are looking at at that time, but in the case of my code, the replacement will occur on the first switch. I don't think it will happen, but it's useless because I'm checking the sort before the index.
Is it enough to check the previous order only when the replacement occurs?
I'll try to make it shorter.
Recommended Posts