Java의 정렬(이진 검색, 순차 정렬, 선택 정렬, 버블 정렬 삽입 정렬, 퀵 정렬)에 대해서 알아보자.
🏹 이진 검색
어떤 데이터를 검색하는 알고리즘에는 여러가지 방법이 있다. 그 중 이진 검색에 대해 먼저 알아보자.
이진 검색 알고리즘은 오름차순으로 정렬되어 있는 경우에 사용하는 방법이다.
처음에 중간값을 임의로 선택하고, 그 값과 찾아야 하는 값(X)을 계속해서 비교한다.
X가 중간 값보다 작으면 중간 값을 기준으로 왼쪽의 데이터를, X가 중간값보다 크면 배열의 오른쪽을 대상으로 다시 탐색한다.
아래의 코드를 살펴보자.
public class Hello {
static void binarySearch(int key, int[] arr) {
int mid;
int left = 0;
int right = arr.length - 1;
while (right >= left) {
mid = (right + left) / 2;
System.out.println(right + " " + left + " " + mid);
if (key == arr[mid]) {
System.out.println(mid);
break;
}
if (key < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
public static void main(String[] args) {
// 이미 정렬 되어 있음
int[] ar = { 3, 4, 5, 6, 7, 8, 9, 10 };
binarySearch(7, ar);
}
}🏹 라이브러리를 활용한 이진 검색
위와 같이 구현한 이진 검색은 Arrays.binarySearch을 활용해서 구현할 수도 있다.
//ex12: 라이브러리를 활용한 이진 검색
public class Hello {
public static void main(String[] args) {
// 이미 정렬 되어 있음
int[] data = { 1, 2, 3, 4, 5, 6, 7, 8 };
int findData = 4;
int resultIndex = Arrays.binarySearch(data, findData);
if(resultIndex < 0) System.out.println("not found");
else System.out.println(resultIndex);
}
}🏹 순차 정렬
그렇다면 이제는 데이터가 오름차순으로 정렬되어 있지 않은 경우, 정렬하는 방법에 대해 알아보자.
배열에 8개의 데이터가 있다고 할 때,
ar[0]과 ar[1], ar[0]과 ar[2], ar[0]과 ar[3], ... , ar[0]과 ar[7]
위와 같이 비교하며 큰 값이 뒤로 가도록 데이터를 바꿔주어야 한다.
따라서 for문 2개를 활용하여 아래와 같이 구현할 수 있다.
public class Hello {
public static void main(String[] args) {
int[] ar = {9, 1, 6, 8, 4, 3, 2, 0};
for(int i : ar) {
System.out.print(i + " ");
} System.out.println();
for (int i = 0; i < ar.length; i++) {
for (int j = i + 1; j < ar.length; j++) {
// 0 1, 0 2, 0 3 , ... , 0 7과 같이 비교
// i=1일때 j=2, 1 3, 1 4, ..., 1 7과 같이 비
//System.out.print(i + "" + j + " ");
if(ar[i] > ar[j]) {
int t = ar[i];
ar[i] = ar[j];
ar[j] = t;
}
}//System.out.println();
}
for(int i : ar) {
System.out.print(i + " ");
} System.out.println();
}
}🏹 선택 정렬
위의 코드에서 조금 더 발전하면, 모든 값을 비교하는 것이 아니라
ar[0]과 ar[1] ~ a[7]중 min값,
ar[1]과 ar[2] ~ a[7]중 min값,
ar[2]과 ar[3] ~ a[7]중 min값, ...
위와 같이 비교하여 데이터를 바꾸어 줄 수도 있다.
아래의 코드를 살펴보자.
public class Hello {
public static void main(String[] args) {
int[] ar = { 9, 1, 6, 8, 4, 3, 2, 0 };
for (int i : ar) {
System.out.print(i + " ");
}
System.out.println();
System.out.println("---------------------");
for (int i = 0; i < ar.length; i++) {
int min = i;
for (int j = i + 1; j < ar.length; j++) {
if (ar[min] > ar[j]) {
min = j;
}
}
int t = ar[i];
ar[i] = ar[min];
ar[min] = t;
for (int data : ar) {
System.out.print(data + " ");
}
System.out.println();
}
}
}위 코드를 실행하면, 아래와 같이 결과가 나온다.
🏹 순차 정렬 vs 선택 정렬
두 가지 정렬방법을 비교해보자.
비교할 때는, 코드가 실행되는 시간을 측정하여 비교하면 된다.
아래의 코드처럼 10,000개의 int를 랜덤으로 생성하여 배열에 넣고 정렬 알고리즘을 실행하면 다음과 같은 결과가 나온다.
public class Hello {
static void sort1(int[] ar) {
for (int i = 0; i < ar.length; i++) {
for (int j = i + 1; j < ar.length; j++) {
if (ar[i] > ar[j]) {
int t = ar[i];
ar[i] = ar[j];
ar[j] = t;
}
}
}
}
static void sort2(int[] ar) {
for (int i = 0; i < ar.length; i++) {
int min = i;
for (int j = i + 1; j < ar.length; j++) {
if (ar[min] > ar[j]) {
min = j;
}
}
int t = ar[i];
ar[i] = ar[min];
ar[min] = t;
public static void main(String[] args) {
int num = 10000;
int[] ar = new int[10000];
for (int i = 0; i < num; i++) {
ar[i] = new Random().nextInt(1000);
}
for (int i : ar) {
System.out.print(i + " ");
} System.out.println();
System.out.println("sort1");
long start = System.nanoTime(); //시간 측정
sort1(ar);
long end = System.nanoTime(); //시간 측정
System.out.println(end - start);
System.out.println("sort2");
start = System.nanoTime(); //시간 측정
sort2(ar);
end = System.nanoTime(); //시간 측정
System.out.println(end - start);
}
}
위의 결과를 살펴보면 선택 정렬이 순차 정렬보다 훨씬 빠르것을 알 수 있다.
🏹 버블 정렬
5개의 int로 이루어진 배열이 있을때, 버블 정렬은 아래와 같이 진행된다. 각 숫자는 배열의 인덱스이다.
01 12 23 34
01 12 23
01 12
01버블 정렬은 순차 정렬과 논리와 반복 횟수가 비슷하다. 그러나 버블 정렬에서는 계속해서 숫자가 더 큰 값을 뒤로 보낸다는 차이점이 있다.
public class Hello {
public static void main(String[] args) {
// 01 12 23 34
// 01 12 23
// 01 12
// 01
int[] ar = { 9, 1, 6, 8, 4, 3, 2, 0 };
int count = 0; // swap 횟수 측정
for (int i = 0; i < ar.length - 1; i++) {
for (int j = 0; j < ar.length - i - 1; j++) {
// System.out.print(1 + " ");
System.out.print(j + "" + (j + 1) + " ");
if (ar[j] > ar[j + 1]) {
count++;
int t = ar[j];
ar[j] = ar[j + 1];
ar[j + 1] = t;
}
}
System.out.println();
}
for (int i : ar) {
System.out.print(i + " ");
}
System.out.println();
System.out.println("ct1: " + count);
System.out.println();
int count2 = 0;
int[] br = { 9, 1, 6, 8, 4, 3, 2, 0 };
for (int i = 0; i < br.length; i++) {
for (int j = i + 1; j < ar.length; j++) {
System.out.print(i + "" + j + " ");
if (br[i] > br[j]) {
count2++;
int t = br[i];
br[i] = br[j];
br[j] = t;
}
}
System.out.println();
}
System.out.println("ct2: " + count);
}
}🏹 삽입 정렬
삽입 정렬은, 새로운 값을 기존의 값 사이에 삽입하는 것이다.
두 번째 원소부터 시작하여 위치를 지정하며, 삽입된 값 이후의 값들을 하나씩 뒤로 밀린다.
이 때, 삽입 위치는 앞의 값 < 새로운 값 < 뒤의 값을 만족하여야 한다.
예를 들어 2 3 6 7 8 4 5 6 7으로 구성된 배열이 있을 때, 아래와 같이 진행된다.
원본: 2 3 6 7 8 4 5 6 7
1회전: 2 3 4 6 7 8 5 6 7 (4가 3과 6사이로 이동됨 )
2회전: 2 3 4 5 6 7 8 6 7 (5가 4와 6사이로 이동됨 )
...public class Hello {
static void show(int[] ar) {
for (int i = 0; i < ar.length; i++) {
System.out.print(ar[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] ar = { 2, 3, 6, 7, 8, 4, 5, 6, 7 };
show(ar);
for (int i = 1; i < ar.length; i++) {
int aux = i - 1; // aux = 0
int temp = ar[i]; // temp = 3
while ((aux >= 0) && (ar[aux] > temp)) {
System.out.println("while: " + (aux + 1) + " " + (aux));
ar[aux + 1] = ar[aux];
aux--;
}
ar[aux + 1] = temp;
}
show(ar);
}
}🏹 퀵 정렬
여러가지 정렬 알고리즘 중에 동작 시간이 가장 빠른 것은 퀵 정렬이다.
퀵 정렬의 특징은 pivot이 존재한다는 것이다.
처음에 pivot은 중간 값으로 정한다.
만약 20 09 41 64 24 40 09 04 35와 같이 데이터 배열이 있고, 기준 pivot이 60이라고 한다면,
왼쪽부터 기준 pivot보다 큰 값을 탐색하는 동사에 오른쪽부터 기준 pivot보다 작은 값을 탐색한다. 이후에 이 둘의 위치를 교환한다.
20 09 41 64 24 40 09 04 35
1회차: i는 64, j는 35에서 걸림 -> 데이터 교환
20 09 41 35 24 40 09 04 64
2회차: i는 64, j는 04에서 걸림 -> 데이터 교환이 이루어지면 안되기 떄문에, i<=j일때만 데이터를 교환하도록 수정그런데 만약 2회차와 같이 탐색한 값 i가 j보다 작다면 데이터 교환이 이루어지면 안되기 때문에, i<=j 일때만 데이터를 교환하도록 코드를 작성해야 한다.
public class Hello {
// 재귀함수
static void show(int[] ar) {
for (int i = 0; i < ar.length; i++) {
System.out.printf("%02d ", i);
}
System.out.println();
for (int i = 0; i < ar.length; i++) {
System.out.printf("%02d ", ar[i]);
}
System.out.println();
}
static void qsortSort(int[] ar, int left, int right) {
int pivot = ar[(left + right) / 2];
int i = left; // left
int j = right; // right
while (i <= j) {
// left
while (ar[i] < pivot)
i++;
// right
while (ar[j] > pivot)
j--;
if (i <= j) {
int temp = ar[i];
ar[i] = ar[j];
ar[j] = temp;
i++;
j--;
}
}
if (left < j)
qsortSort(ar, left, j);
if (i < right)
qsortSort(ar, i, right);
}
public static void main(String[] args) {
int size = 20;
int[] ar = new int[size];
for (int i = 0; i < ar.length; i++) {
ar[i] = new Random().nextInt(100);
}
show(ar);
qsortSort(ar, 0, ar.length - 1);
show(ar);
System.out.println("end");
}
}