버블정렬 (오름차순 정렬)
(버블 정렬, 선택정렬, 삽입정렬, 퀵솔트)
알고리즘 - 컴퓨터가 따라 할 수 있도록 문제를 해결하는 절차나 방법을 설명하는 과정
컴퓨터를 활용하는 일련의 방법 또는 절차, 문제해결 방법을 순서대로, 절차대로 나열한 것
서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환
1회전 ⇒ 4바퀴 | 2회전 ⇒ 3바퀴 | 3회전 ⇒ 2바퀴 | 4회전 ⇒ 1바퀴 |
(5, 8, 2, 4, 3) | (5, 2, 4, 3, 8) | (2, 4, 3, 5, 8) | (2, 3, 4, 5, 8) |
① 5, 8 비교 (변화없음)
② 8, 2 비교 (5, 2, 8, 4, 3) ③ 8, 4 비교 (5, 2, 4, 8, 3)
④ 8, 3 비교 (5, 2, 4, 3, 8) | ① 5, 2 비교 (2, 5, 4, 3, 8) ② 5, 4 비교 (2, 4, 5, 3, 8) ③ 5, 3 비교 (2, 4, 3, 5, 8) | ① 2, 4 비교 (변화 없음) ② 4, 3 비교 (2, 3, 4, 5, 8) | ① 2, 3 비교 (변화 없음) |
N = 변수의 개수
회전수 ⇒ N - 1 |
1회전의 비교 횟수 : N - 1
2회전의 비교 횟수 : N - 2
3회전의 비교 횟수 : N - 3 |
Swap code
int temp;
temp = arr[0];
arr[0] = arr[1];
arr[1] = temp;public class BubbleTest04 {
public static void main(String[] args) {
int[] arr = {5, 8, 2, 4, 3};
final int N = arr.length;
int temp;
if (arr[0] > arr[1]) {
temp = arr[0];
arr[0] = arr[1];
arr[1] = temp;
}
if (arr[1] > arr[2]) {
temp = arr[1];
arr[1] = arr[2];
arr[2] = temp;
}
if (arr[2] > arr[3]) {
temp = arr[2];
arr[2] = arr[3];
arr[3] = temp;
}
if (arr[3] > arr[4]) {
temp = arr[3];
arr[3] = arr[4];
arr[4] = temp;
}
for (int i = 0; i < 5; i++) {
System.out.println(arr[i]);
}
}
}public class BubbleTest05 {
public static void main(String[] args) {
int[] arr = {5, 8, 2, 4, 3};
final int N = arr.length;
int temp;
for (int j = 0; j < N - 1; j++) {
for (int i = 0; i < N - 1; i++) {
if (arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
for (int i = 0; i < 5; i++) {
System.out.print(arr[i] + " ");
}
}
}선택정렬
최소값과 자리를 바꾸며 정렬
(5, 8, 2, 4, 3)
앞의 수가 작을 때 p가 변함
1회전 | ㅤ | ㅤ | 2회전 | ㅤ |
기준점 final i = 0 (해당 위치 변경) | 기준점 p = 0 (교환 인덱스 위치) | ㅤ | final i = 1 | p = 1 |
5, 8 | (0, 1) | ㅤ | 8, 5 | (1, 2) p = 2 |
5, 2 | (0, 2) p = 2 | ㅤ | 5, 4 | (2, 3) p = 3 |
2, 4 | (2, 3) | ㅤ | 4, 3 | (3, 4) p = 4 |
2, 3 | (3, 4) | ㅤ | ㅤ | ㅤ |
ㅤ | (p, for문에서 증가하는 값) | ㅤ | ㅤ | ㅤ |
if(i!=p) (i, p 교환) | (2, 8, 5, 4, 3) | ㅤ | if(i!=p) (i, p 교환) | (2, 3, 5, 4, 8) |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |
3회전 | ㅤ | ㅤ | 4회전 | ㅤ |
final i = 2 | p = 2 | ㅤ | final i = 3 | p = 3 |
5, 4 | (2, 3) p = 3 | ㅤ | 5, 8 | (3, 4) |
4, 8 | (3, 4) | ㅤ | ㅤ | ㅤ |
if(i!=p) (i, p 교환) | (2, 3, 4, 5, 8) | ㅤ | if(i!=p) (i, p 교환) | 변화없음 |
public class SelectedEx01 {
public static void main(String[] args) {
int[] arr = {5, 8, 2, 4, 3};
final int N = arr.length;
final int rep = 0;
int min = rep;
if (arr[0] > arr[1]){
min = 1;
} //5, 8, 2, 4, 3
if (arr[0] > arr[2]){
min = 2;
} //5, 8, 2, 4, 3 -> min = 2
if (arr[2]> arr[3]) {
min = 3;
} //5, 8, 2, 4, 3 -> min = 2
if (arr[2]>arr[4]){
min = 4;
}
if (rep !=min){
int temp = arr[rep]; // temp = 5
arr[rep] = arr[min];
arr[min] = temp;
}
}
}public class SelectedEx02 {
public static void main(String[] args) {
int[] arr = {5, 8, 2, 4, 3};
final int N = arr.length;
final int rep = 0;
int i = rep;
int min = rep;
i++; //1
if (arr[min] > arr[i]){
min = i;
}
i++; //2
if (arr[min] > arr[i]){
min = i; //2
}
i++; //3
if (arr[min]> arr[i]) {
min = i;
}
i++; //4
if (arr[min]>arr[i]){
min = i;
}
if (rep !=min){
int temp = arr[rep];
arr[rep] = arr[min];
arr[min] = temp;
}
}
}public class SelectedEx03 {
public static void main(String[] args) {
int[] arr = {5, 8, 2, 4, 3};
final int N = arr.length;
final int rep = 0;
int min = rep;
for (int i = rep+1; i < N; i++) {
if (arr[min] > arr[i]){
min = i;
}
}
if (rep !=min){
int temp = arr[rep];
arr[rep] = arr[min];
arr[min] = temp;
}
}
}public class SelectedEx04 {
public static void main(String[] args) {
int[] arr = {5, 8, 2, 4, 3};
final int N = arr.length;
int rep;
int min;
for (int j = 0; j < 4; j++) {
}
//1회전
rep = 0;
min = rep;
for (int i = rep+1; i < N; i++) {
if (arr[min] > arr[i]){
min = i;
}
}
if (rep !=min){
int temp = arr[rep];
arr[rep] = arr[min];
arr[min] = temp;
}
//2회전
rep = 1;
min = rep;
for (int i = rep+1; i < N; i++) {
if (arr[min] > arr[i]){
min = i;
}
}
if (rep !=min){
int temp = arr[rep];
arr[rep] = arr[min];
arr[min] = temp;
}
}
}public class SelectedEx05 {
public static void main(String[] args) {
int[] arr = {5, 8, 2, 4, 3};
final int N = arr.length;
int rep;
int min;
for (int j = 0; j < 4; j++) {
rep = j;
min = rep;
for (int i = rep+1; i < N; i++) {
if (arr[min] > arr[i]){
min = i;
}
}
if (rep !=min){
int temp = arr[rep];
arr[rep] = arr[min];
arr[min] = temp;
}
}
for (int v:arr){
System.out.print(v+" ");
}
}
}Share article