개발자를 꿈꾸다.

[삽입정렬]

public void sort(int[] input){

public class Input {

public static void main(String[] args) {

int []input = {15,42,45,9,2,55,23,6};

for(int i = 1 ; i<input.length; i++) {

int side = i-1;

int standard = input[i];

while(side>=0 && standard <input[side]) {

input[side+1] = input[side];

side--;

}

input[side+1]= standard;

}

for(Integer br :input) {

System.out.println(br);

}

}

}

삽입정렬은 Θ(n^2) 시간 복잡도를 갖는다. 

그러나 이미 정렬이 되어 있는 경우는 한번씩 밖에 비교하지 않기 때문에 O(n) 이다.

삽입 정렬은 0번째부터가 아닌 1번째부터 이하로 데이터를 정렬한다. 

기준이 되는 수를 임시변수에 넣고 기준수와 -1해서 하나씩 비교한다. 

삽입되는 변수가 더 클경우 +1해서 데이터를 삽입한다.

package bubbleSort;

public class InputSort {

public static void main(String[] args) {

int i, j, temp;

int[] ar = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };

// 삽입정렬은 적절한 위치에 삽압하는 것입니다.

// 앞에 있는 원소들이 정렬이 되어있다는 가정을 가지고 있습니다.

for (i = 0; i < ar.length-1; i++) {

j = i;

while (ar[j] > ar[j + 1]) {

temp = ar[j];

ar[j] = ar[j + 1];

ar[j + 1] = temp;

j--;

}

}

for(int outView : ar) {

System.out.println(outView);

}

}

}

[나중에 찾아보기 위한 공부내용 ]

GCD (최대 공약수 )

유클리드 알고리즘 

1) v가 u보다 크다면 u와 v의 값을 바꾼다 

2) u= u-v

3) u가 0이면 v가 최대 공약수 

0이 아니면 (1)돌아갑니다. 

GCD (250, 30)

GCD (230, 30)

GCD (200, 30)

GCD (170, 30)

.........

GCD (10, 30)

GCD (30, 10)

GCD (20, 10)

GCD (0, 10)

GCD = 10 ;

[풀이 방법 ]

package algoridem;

public class Gcd {

public int get_gcd(int su, int su2) {

int t = 0 ; // 임시저장 변수 

//su가 0보다 크면 while문은 실행된다. 

while (su>0) {

// 만약 su2가 su보다 더 크다면 

// 두수의 자리를 체인지 해준다.

if (su<su2) {

t = su; su = su2; su2=t;

}

//su -su2를 통해 최대 공약수를 찾기 

su = su-su2;

}

return su2;

}

public static void main(String[] args) {

Gcd g = new Gcd();

System.out.println(g.get_gcd(280, 30));

}

}

[그러나]

[유클리드 알고리즘 개선 방법] 

뺄셈 기반 알고리즘의 문제는 너무 많은 뺄셈을 요구 하기 때문에 

나눗셈의 나머지를 구해 풀이를 해보자 

GCD (su, su2) = GCD(su%su2,v) =GCD(v,u%v)

- su%su2 < su2 

v가 0이 아니면 

su = su% su2 

su와 su2를 교환 

처음으로 돌아감 

su2가 0이면 su가 GCD(최대공약수)

[개선된 풀이 방법 ]

package algoridem;

public class Gcd {

public int get_gcd(int su, int su2) {

int t = 0; // 임시저장 변수

// su가 0보다 크면 while문은 실행된다.

while (su2 > 0) {

t = su % su2;

su = su2;

su2 = t;

}

return su;

}

public static void main(String[] args) {

Gcd g = new Gcd();

System.out.println(g.get_gcd(280, 30));

}

}

[재귀함수]

[생각하며 코딩을 정리 해보기 ]]

1.su가 0이면 su2 가 최대공약수 이기에 

2.0 이되면 최대공약수의 값이 나온것으로보고 

3.반복문을 멈추기 위해서 

4.while의 조건은 su>0을 만들어서 반복문을 돌리고 

5.su 가 작아지면 false를 만들어서 

6.앞의 조건의 su가 0임을 만들어낸다. 

7. if 만약 v가 u보다 크면 두 수의 자리를 바꾸고 

계산한다 

그러나 이러한 방식은 뺄셈을 통해 계속적으로 계산해서 

마지막의 값을 얻어내기 때문에 효과적이지 못하다 

[개선된 알고리즘]

이 연산에서 su-su2로 su가 0이 될때까지 계산하는 것이므로 

su2값이 공통되게 뺄셈이 되기 때문에 su%su2 계산을 하면 

더 빠르게 연산을 진행할 수 있다. 

1. su% su2의 나머지 값을 t에 저장하고 

su 에 su2의 값을 저장한다.

su2에 t의 값을 저장하고 

while su2가 false가 될때까지 계속 연산한다. 

false가 되면 while문을 빠져나가게 되고 결국에는 

su값을 리턴하면된다.

[재귀함수]

v==0 이되면 리턴 값은 su로한다 . 

재귀 함수를 통해 

v가 0이 아닐 때까지 리턴하는 방법으로 

매개변수의 값을 su2 값과 su%su2값을 매개변수로 넣어서 

먄약 su의 값이 280이고 su2값이 30이면 

public int gcd(int su, int su2){

// 생략 

else gcd ( su2, su%su2);

}

값을 교차해서 넣어서 su2의 매개변수값을 나머지로 만든다 

public int gcd(int su, int su2){

if 문을 이용해 su2 가 나머지를 구하는 방식이므로 

su2가 0이 되면, 

su의 값을 리턴하면된다. 

else gcd ( su2, su%su2);

}

선택 정렬 : 선택하여 정렬하는 알고리즘

선택 정렬은 마지막 순번은 확인해볼 필요가 없기 때문에 n-1 해줍니다. 

최소값을 선택하면 오름차순이 되고 

최대값을 선택하면 내리차순이 됩니다. 

선택정렬은 데이터가 적을 때는 좋지만,데이터100개 많은 수의 데이터를 정렬할 때는 좋지 않다. 

최소값선택 정렬 

1. 정렬되지 않은 숫자 중에 가장 첫번째 숫자와 자리를 바꾼다 

2. 모든 숫자를 옮길 때까지 2번을 반복한다.  

5 2 4 6 1 3

1 2 4 6 5 3

1 2 4 6 5 3 

1 2 3 6 5 4

1 2 3 6 5 4 

1 2 3 4 5 6

가장 작은 숫자를 찾는 방법은 모든 숫자를 비교 해보는 것이다. 

최대값선택 정렬 

5 2 4 6 1 3 

6 2 4 5 1 3 

6 5 4 2 1 3

6 5 4 3 1 2

6 5 4 3 2 1

ㅇ선택 정렬 

문제정의 : 정렬 

알고리즘 : 최소값을 찾아서 최소값을 맨 앞으로 보내는 방법 

1. 정렬되지 않는 숫자중에 가장 앞으로 보낸다 .

2. 선택한 숫자와 정렬되지 않는 숫자의 자리를 바꿔준다. 

모든 n-1개 까지의 숫자가 모두 비교될 때까지 1번과 2번을 계속수행한다.  

3.첫번째 선택한 숫자는 n개중에 가장 작은숫자 

두번째 숫자는 첫번째 숫자를 제외 하고 n개중에 두번째로 작은 숫자이다. 

세번째 첫번째 두번째 숫자를 제외하고 나머지 n개중에 세번째로 작은 숫자이다.  

4. 성능분석 

숫자들이 크고 작음을 비교를 몇번하느냐를 기준으로 확인한다.

(n제곱)

package java1226;

public class Array_max {

public static void main(String[] args) {

int[] ar = { 74, 23, 97, 67, 28 };

int size = ar.length;

int i = 0; // 0은 인덱스입니다.

int j = 0; // 최소값 인덱스 .

int count = 0;

int max = ar[0];

int min = ar[0];

int max_pos =0;

int pos = 0; // 작은 값의 위치를 저장할 변수

// 최대값

while (i < size) {

if (max < ar[i]) {

max = ar[i];

max_pos = i;

}

i = i + 1;

}

// 최소값

while (j < size) {

if (min > ar[j]) {

min = ar[j];

pos = j;// 최소값을 찾았을 때 그 위치를 저장

}

j = j + 1;

}

System.out.println(max);

System.out.println(min);

System.out.println("max : " + max_pos);

System.out.println("max : " + pos);

}

}