함수를 절차적 으로 나눠서 코딩 하는 것
ex)라면
1.라면 봉지를 뜯는다.
2.물을 500ml만큼 냄비에 넣고 끓인다.
3.물이 끓으면 라면을 넣는다.
4.라면을 넣고 또 물이 끓으면 계란을 넣는다
5.15초 뒤에 불을 끈다.
버블 정렬
서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
버블 정렬은 첫 번째 인덱스와 두 번째 인덱스를, 두번째 인덱스와 세 번째 인덱스를,
... 이런식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
1회전(값의 갯수 -1) 할때 가장 큰 수가 마지막 자리에 오게 끔 정렬 하는 것이다.
ex)
5, 8, 2, 4, 3
1회전 (4바퀴)
(1) 5, 8 비교하기 (변화 없음)
(2) 8, 2 비교 (5, 2, 8, 4, 3)
(3) 8, 4 비교 (5, 2, 4, 8, 3)
(4) 8, 3 비교 (5, 2, 4, 3, 8)
2회전(3바퀴)
(1) 5, 2 비교 (2, 5, 4, 3, 8)
(2) 5, 4, 비교(2, 4, 5, 3, 8)
(3) 5, 4, 비교(2, 4, 3, 5, 8)
3회전(2바퀴)
(1) 2, 4, 비교(2, 4, 3, 5, 8)
(2) 4, 3, 비교(2, 3, 4, 5, 8)
3, 4, 8, 2, 5
(1) 3, 4, 8, 2, 5
(2) 3, 4, 8, 2, 5
(3) 3, 4, 2, 8, 5
(4) 3, 4, 2, 5, 8
완성된 코드
package ex03;
/**
* 5, 8, 2, 4, 3 (N)
* 회전수 : N-1
* 1회전 비교 횟수 : N-1
* 2회전 비교 횟수 : N-2
* 3회전 비교 횟수 : N-3
* 4회전 비교 횟수 : N-4
* <p>
* 1회전 (4바퀴)
* (1) 5, 8 비교 (변화없음)
* (2) 8, 2 비교 (5,2,8,4,3)
* (3) 8, 4 비교 (5,2,4,8,3)
* (4) 8, 3 비교 (5,2,4,3,8)
* <p>
* 2회전 (3바퀴)
* (1) 5,2 비교 (2,5,4,3,8)
* (2) 5,4 비교 (2,4,5,3,8)
* (3) 5,3 비교 (2,4,3,5,8)
* <p>
* 3회전 (2바퀴) - 끝
* (1) 2,4 비교
* (2) 4,3 비교 (2,3,4,5,8)
* <p>
* 4회전 (1바퀴)
* (1) 2,3 비교
*/
public class BubbleEx01 {
static void bubble(int[] arr) {
final int N = arr.length;
int temp;
for (int loop = 1; loop < 5; loop++) {
for (int i = 0; i < N - loop; 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] + " ");
}
}
public static void main(String[] args) {
int[] arr = {5, 8, 2, 4, 3};
BubbleEx01.bubble(arr);
System.out.println();
int[] arr2 = {5, 8, 2, 4, 3, 10, 500, 7, 6};
BubbleEx01.bubble(arr2);
}
}정렬의 목적
정렬의 목적은
ex)5, 7, 9, 10, 15, 3, ….
이렇게 값이 있을 때
자료 구조의 검색에 초점이 맞춰져 있다.
효율적으로 원하는 데이터를 찾기 쉬워진다.
중복이 데이터가 있어도 멈추는 타이밍을 알 수 있게 된다.
-클러스터링(Clustering)
:중심점을 기준으로 가까운 데이터들을 할당하고, 그룹화를 반복적으로 수행 한다.
선택 정렬
0번째 인덱스 값과 첫 번째 인덱스 값부터 마지막 인덱스 값까지 차례대로 비교하며 가장 작은 값을 찾아 0번째에 놓고,
1번째 인덱스 값을 2번째 인덱스 값부터 마지막 인덱스 값까지 비교하여 그 중 가장 작은 값을 찾아 1번째 인덱스 값에 놓는 과정을 반복하며 정렬을 수행 한다.
제자리 정렬 P=PLACE
5, 8, 2, 4, 3
final i = 0 (해당 위치 변경), P=0(교환 인덱스)
5, 8 (0, 1)
5, 2 (0, 2)(P = 2)
2, 4 (2, 3)
2, 3 (2,4)
if( i ! =p )
(1) 2, 8, 5, 4,. 3 (i, p 교환)
final i = 1 (해당 위치 변경), P=1(교환 인덱스)
8, 5 (1, 2) p = 2
5, 4 (2, 3) p =3
4, 3 (3. 4) p = 4
if( i! = p)
2, 3, 5, 4, 8
final i = 2 (해당 위치 변경), P=2(교환 인덱스)
5, 4 (2, 3) p =3
4, 8 (3, 4)
if( i! = p)
2, 3, 4, 5, 8
final i = 3 (해당 위치 변경), P=3(교환 인덱스)
5, 8 (3, 4)
if( i! = p) x
p값은 (교환해야 될 인덱스) +1 씩 증가한다.
for which문은 전체를 순환해서 전체 출력 할 때 사용
(완성된 코드 내부 for (int v : arr) {
System.out.print(v + " ");
})
package ex03;
public class SlectedEx01 {
public static void main(String[] args) {
int[] arr = {5, 8, 2, 4, 3};
final int N = arr.length;
// 변경 해야될 위치 5 -> replace -> rep
// 변경 해야될 위치 8 -> min -> min
final int rep = 0;
int i = rep;
int min = rep;
}
i=i+1; // 1
if(arr[min] > arr[i]){ // 5, 8, 2, 4, 3
min = i;
}
i=i+1; // 2
if (arr[min] > arr[i]){// 5, 8, 2, 4, 3 -> min = 2
min = i;
}
i=i+1; //3
if (arr[min] > arr[i]){ // 5, 8, 2, 4, 3 -> min = 2
min = i;
}
i=i+1; //4
if (arr[min] > arr[i]){ // 5, 8, 2, 4, 3 -> min = 2
min = i;
}
if (rep != min){
int temp = arr[rep]; // temp = 5
arr[rep] = arr[min];
arr[min] = temp;
}
}
}package ex03;
public class SlectedEx01 {
public static void main(String[] args) {
int[] arr = {5, 8, 2, 4, 3};
final int N = arr.length;
// 변경 해야될 위치 5 -> replace -> rep
// 변경 해야될 위치 8 -> min -> min
final int rep = 0;
int min = rep;
for (int i = rep + 1; i < N; i++) {
if(arr[min] > arr[i]){ // 5, 8, 2, 4, 3
min = i;
}
if (rep != min){
int temp = arr[rep]; // temp = 5
arr[rep] = arr[min];
arr[min] = temp;
}
}
}package ex03; //완성된 코드
public class SlectedEx01 {
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 < N - 1; j++) {
rep = j;
min = rep;
for (int i = rep + 1; i < N; i++) {
if (arr[min] > arr[i]) { // 5, 8, 2, 4, 3
min = i;
}
if (rep != min) {
int temp = arr[rep]; // temp = 5
arr[rep] = arr[min];
arr[min] = temp;
}
}
for (int v : arr) {
System.out.print(v + " ");
}
}
}
}Share article
