[JAVA] Sort(정렬)
선택 정렬 (Selection Sort) ?
선택 정렬은 이름에 맞게 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다.
시간 복잡도는 O(n^2)으로 상당히 느리다.
기본 알고리즘
1. 정렬되지 않은 인덱스의 맨 앞에서 부터, 이를 포함한 그 이후의 배열 값 중 가장 작은 값을 찾아간다.
2. 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.
3. 다음 인덱스에서 위 과정을 반복해 준다.
-> 이 정렬 알고리즘은 n-1, n-2, ... 1개씩 비교를 반복한다. "비교횟수 : n(n-1)/2"
|
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
|
package ex0730;
public class Selectsort_Asc {
public static void main(String[] args) {
//선택정렬
//처음수를 기준으로 다음 수~끝 모두 탐색하며 가장 작은거 선택
//그다음 수 기준 다음다음의 수~끝 모두 탐색하며 가장 작은거 선택...반복
int[] a = new int[] { 30, 27, 15, 60, 7, 21 };
int t;
System.out.print("Source data : ");
for (int n : a)
System.out.print(n + " ");
System.out.println();
//Selection Sort
for (int i = 0; i < a.length - 1; i++) {
for (int j = i + 1; j < a.length; j++) {
if (a[i] > a[j]) {
t = a[i]; a[i] = a[j]; a[j] = t;
}
}
}
System.out.print("Sort data : ");
for(int n : a)
System.out.print(n+" ");
System.out.println();
}
}
|
cs |
버블 정렬 (Bubble Sort) ?
버블 정렬은 인접한 두 수를 비교하여 큰 수를 뒤로 보내는 간단한 정렬 알고리즘으로 코드가 단순함
원소의 이동이 거품이 수면으로 올라오는 듯 한 모습을 보이기 때문에 Bubble Sort라는 이름을 가지게 됨
시간 복잡도는 O(n^2)이고 공간 복잡도는 하나의 배열만 사용하여 정렬을 진행하기 때문에 O(n)이다.
기본 알고리즘
1. 인접한 두 인덱스를 비교해서 정렬이 되어있지 않을 경우 정렬.
2. 리스트 처음부터 마지막 원소까지 반복하여 정렬을 하고 나면 제일 마지막 리스트에는 제일 큰 값(또는 작은 값)이 저장된다.
3. 다다시 처음 리스트부터 마지막 리스트 이전 리스트까지 서로 이웃한 인덱스를 비교해가며 정렬.
-> 이 정렬 알고리즘은 n-1, n-2, ... 1개씩 비교를 반복한다. "비교횟수 : n(n-1)/2"
1. 이중 For문을 이용한 버블정렬
|
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
|
package ex0730;
public class Bubblesort_Asc {
public static void main(String[] args) {
//버블정렬
//인접한거를 정렬하므로 가장 뒤 부터 정렬된 수가 저장.
int[] a = new int[] { 30, 27, 15, 60, 7, 21 };
int t;
System.out.print("Source data : ");
for (int n : a)
System.out.print(n + " ");
System.out.println();
//Bubble Sort
for(int i = 1; i<a.length; i++)
{
for(int j = 0; j<a.length-i; j++){
if(a[j]>a[j+1]) {
t = a[j+1];
a[j+1] = a[j];
a[j] = t;
}
}
for(int n : a)
System.out.print(n+" ");
System.out.println();
}
System.out.print("Sort data : ");
for(int n : a)
System.out.print(n+" ");
System.out.println();
}
}
|
cs |
2. Optimized Bubble Sort (불필요한 비교를 없앤 Sort) -->1번 버블정렬보다 속도가 빠름
|
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
|
package ex0730;
public class OptimizedBubblesort_Asc {
public static void main(String[] args) {
//버블정렬
//인접한거를 정렬하므로 가장 뒤 부터 정렬된 수가 저장.
int[] a = new int[] { 30, 27, 15, 60, 7, 21 };
int t,pass;
boolean flag;
System.out.print("Source data : ");
for (int n : a)
System.out.print(n + " ");
System.out.println();
/*
//Optimize Bubble Sort (내가 짠거)
for(int i = 1; i<a.length; i++)
{
for(int j = 0; j<a.length-i; j++){
if(a[j]>a[j+1]) {
flag = true;
t = a[j+1];
a[j+1] = a[j];
a[j] = t;
}
}
if(!flag) break;
else flag = false;
for(int n : a)
System.out.print(n+" ");
System.out.println();
}
*/
//선생님이 짠거
pass = 1;
do {
flag = false;
for(int i = 0; i<a.length-pass; i++) {
if(a[i]>a[i+1]) {
t = a[i]; a[i] = a[i+1]; a[i+1]=t;
flag = true;
}
}
pass++;
}while(flag);
System.out.print("Sort data : ");
for(int n : a)
System.out.print(n+" ");
System.out.println();
}
}
|
cs |